分享者：唐博

編者按：?

這篇文章我想要寫已經(jīng)很久了，畢竟“端對(duì)端預(yù)測后優(yōu)化”（End-to-End Predict-then-Optimize）正是我讀博期間的主要研究方向，但我又一直遲遲沒能下筆。想說自己雜事纏身（實(shí)際是重度拖延癥晚期的緣故），更主要的原因恐怕是我對(duì)這一領(lǐng)域理解依然尚淺，尤其我希望以綜述的形式，為讀者提供詳盡的介紹。然而，這篇文章并不能稱為一篇綜述，原因有二：一方面，我雖然進(jìn)行相關(guān)的研究，但還無法自稱為專家；另一方面，"端對(duì)端預(yù)測后優(yōu)化"還處于起步階段，有很大的探索空間，尚有無窮可能。因此，此時(shí)編寫綜述可能為時(shí)尚早。因此，我選擇用這篇文章拋磚引玉，旨在引發(fā)關(guān)于這個(gè)領(lǐng)域的進(jìn)一步探討和思考。

1. 引言

運(yùn)籌學(xué)和統(tǒng)計(jì)學(xué)/數(shù)據(jù)科學(xué)/機(jī)器學(xué)習(xí)的緊密關(guān)系由來已久。機(jī)器學(xué)習(xí)通過挖掘數(shù)據(jù)，預(yù)測未知或不確定的信息，一旦得到預(yù)測結(jié)果，常常需要進(jìn)一步的決策行動(dòng)來獲取收益。而運(yùn)籌學(xué)作為建模求解最優(yōu)化問題的工具，盡管可以（相對(duì)）高效地找到最優(yōu)解，但一大限制是通常需要參數(shù)（無論是本身還是其分布）的確定性，無法充分利用數(shù)據(jù)。

本文就是要討論數(shù)據(jù)驅(qū)動(dòng)下，帶有不確定參數(shù)的優(yōu)化問題。這種問題通常通過“預(yù)測后優(yōu)化”的范式來解決。這一問題在現(xiàn)實(shí)生產(chǎn)生活中有著深遠(yuǎn)的意義。舉例來說，車輛路徑規(guī)劃中，由于交通狀況的不斷變化，在每段道路的行駛時(shí)間是不確定的；電網(wǎng)調(diào)度中，不同地區(qū)的電力負(fù)荷也會(huì)隨時(shí)間發(fā)生變化；投資組合中，金融資產(chǎn)的收益率會(huì)受到市場波動(dòng)的影響。以上這些情況都涉及到優(yōu)化模型參數(shù)的不確定性，但是，我們可以利用時(shí)間、天氣、金融因素等特征，預(yù)測這些不確定的參數(shù)，從而進(jìn)行最優(yōu)決策。

此外，本文也會(huì)介紹一個(gè)端對(duì)端預(yù)測后優(yōu)化的開源框架PyEPO (https://github.com/khalil-research/PyEPO)。PyEPO基于PyTorch， 主要針對(duì)（但不限于）線性規(guī)劃（LP）和整數(shù)線性規(guī)劃（ILP），集成了文中提到的多種算法，并提供了Gurobi、Pyomo等優(yōu)化建模工具的API。PyEPO可以作為PyTorch的autograd模塊進(jìn)行深度學(xué)習(xí)的訓(xùn)練和測試，使用起來簡潔明了。這個(gè)框架的設(shè)計(jì)目標(biāo)是為廣大學(xué)界和業(yè)界用戶提供便捷的工具，幫助大家更好地理解和應(yīng)用端對(duì)端預(yù)測后優(yōu)化方法。

2. 問題描述和符號(hào)

首先，請(qǐng)各位讀者放心，本文并不打算深入挖掘端對(duì)端預(yù)測后優(yōu)化背后的數(shù)學(xué)推導(dǎo)，而是致力于提供一些直觀的理解。

我們以一個(gè)簡單的線性優(yōu)化問題為例：
$$\begin{array}{rl}\underset{w_1,w_2}{\max }& c_1{w}_1+c_2{w}_2\\ s.t.& w_1+w_2\le 1\\ & w_1,w_2\ge 0\end{array}$$
在這里，$\mathbf{w}=(w_1,w_2)$代表的是決策變量， W = { w 1 + w 2 ≤ 1 ， w 1 , w 2 ≥ 0 } \mathbf{W} = \lbrace w_1 + w_2 ≤ 1，w_1, w_2 ≥ 0 \rbrace W={w1?+w2?≤1，w1?,w2?≥0}定義了可行域，而$\mathbf{c}=(c_1,c_2)$就是我們不確定的成本向量。

給定成本向量$\mathbf{c}$，由于退化問題的存在，優(yōu)化問題可能得到多個(gè)最優(yōu)解，但可以假定使用某種特定的求解器（如Gurobi）時(shí)，只返回唯一一個(gè)最優(yōu)解${\mathbf{w}}^{?}(\mathbf{c})$。

有一組數(shù)據(jù)$\mathbf{D}=\{({\mathbf{x}}^1,{\mathbf{c}}^1),({\mathbf{x}}^2,{\mathbf{c}}^2),?,({\mathbf{x}}^n,{\mathbf{c}}^n)\}$，其中$\mathbf{x}$為數(shù)據(jù)特征，我們可以利用機(jī)器學(xué)習(xí)模型$\mathbf{g}(\mathbf{x},\mathbf{\theta })$來最小化某個(gè)損失函數(shù)$l(\mathbf{g}(\mathbf{x},\mathbf{\theta }),\mathbf{c})$。其中，$\mathbf{\theta }$是模型$\mathbf{g}(\mathbf{x},\mathbf{\theta })$的參數(shù)，會(huì)在訓(xùn)練過程中不斷更新，而$\hat{\mathbf{c}}=\mathbf{g}(\mathbf{x},\mathbf{\theta })$則是成本向量$\mathbf{c}$的預(yù)測值。由此我們可以利用數(shù)據(jù)驅(qū)動(dòng)的方式來預(yù)測不確定的參數(shù)，幫助實(shí)現(xiàn)優(yōu)化決策。

3. 什么是端對(duì)端預(yù)測后優(yōu)化？

在回答這個(gè)問題之前，我們首先需要理解端對(duì)端學(xué)習(xí)（End-to-End Learning）的理念。端對(duì)端的這個(gè)“端”，指的是輸入端和輸出端。相比于傳統(tǒng)的分步驟方式，它并不依賴于中間過程的手動(dòng)特征工程或者人為設(shè)計(jì)的步驟，而直接構(gòu)建從輸入到輸出的映射，以一種更直接和自動(dòng)的方式解決問題。這種簡化不僅減輕了手動(dòng)特征工程的負(fù)擔(dān)，而且通過學(xué)習(xí)直接的映射，減少了對(duì)中間結(jié)果的依賴，有可能發(fā)現(xiàn)傳統(tǒng)方法難以發(fā)現(xiàn)的模式，從而提高整體的性能。端對(duì)端學(xué)習(xí)作為一個(gè)整體，使得整個(gè)系統(tǒng)變得更簡潔，有利于處理復(fù)雜和高維度的問題。
[圖片]
對(duì)于端對(duì)端預(yù)測后優(yōu)化，我們?cè)谟?xùn)練機(jī)器學(xué)習(xí)模型$\mathbf{g}(\mathbf{x},\mathbf{\theta })$的過程中，模型預(yù)測了成本向量$\hat{\mathbf{c}}=\mathbf{g}(\mathbf{x},\mathbf{\theta })$，然后通過求解器得到最優(yōu)解${\mathbf{w}}^{?}(\hat{\mathbf{c}})=\underset{\mathbf{w}\in \mathbf{W}}{\min }{\hat{\mathbf{c}}}^{?}\mathbf{w}$，并計(jì)算損失函數(shù)$l(\hat{\mathbf{c}},\mathbf{c})$來直接衡量決策損失。

借助鏈?zhǔn)椒▌t，我們能夠計(jì)算出模型參數(shù)$\mathbf{\theta }$相對(duì)于損失函數(shù)$l(\hat{\mathbf{c}},\mathbf{c})$的梯度，用于更新模型參數(shù)：
$$\begin{array}{rl}\frac{?l(\hat{\mathbf{c}},\mathbf{c})}{?\mathbf{\theta }}& =\frac{?l(\hat{\mathbf{c}},\mathbf{c})}{?\hat{\mathbf{c}}}\frac{?\hat{\mathbf{c}}}{?\mathbf{\theta }}\\ & =\frac{?l(\hat{\mathbf{c}},\mathbf{c})}{?{\mathbf{w}}^{?}(\hat{\mathbf{c}})}\frac{?{\mathbf{w}}^{?}(\hat{\mathbf{c}})}{?\hat{\mathbf{c}}}\frac{?\hat{\mathbf{c}}}{?\mathbf{\theta }}\end{array}$$

顯然，對(duì)于依賴于鏈?zhǔn)椒▌t進(jìn)行反向傳播的模型（如神經(jīng)網(wǎng)絡(luò)），關(guān)鍵部分是計(jì)算求解過程的梯度$\frac{?{\mathbf{w}}^{?}(\hat{\mathbf{c}})}{?\hat{\mathbf{c}}}$。端對(duì)端預(yù)測后優(yōu)化的各類算法幾乎都是在此基礎(chǔ)上展開的。然而，在此，我們先不深入討論這些算法，因?yàn)槲覀兾覀儽仨毾然卮鹨粋€(gè)更為重要，也是更致命的問題：

4. 為什么要使用端對(duì)端預(yù)測后優(yōu)化？

4.1 關(guān)于兩階段的預(yù)測后優(yōu)化

毫無疑問，采用兩階段的預(yù)測后優(yōu)化，即將機(jī)器學(xué)習(xí)預(yù)測模型$\mathbf{g}(\mathbf{x},\mathbf{\theta })$和優(yōu)化求解器${\mathbf{w}}^{?}(\mathbf{c})$獨(dú)立使用，看似是一個(gè)更為自然、直接的做法。此方法的預(yù)測任務(wù)中，我們最小化成本向量預(yù)測值$\hat{\mathbf{c}}=\mathbf{g}(\mathbf{x},\mathbf{\theta })$和真實(shí)值$\mathbf{c}$之間的預(yù)測誤差，如均方誤差$l_{\text{MSE}}(\hat{\mathbf{c}},\mathbf{c})={\Vert \hat{\mathbf{c}}?\mathbf{c}\Vert }^2$。熟悉機(jī)器學(xué)習(xí)的讀者可能會(huì)發(fā)現(xiàn)，這實(shí)際上是一項(xiàng)非常經(jīng)典的回歸任務(wù)，對(duì)應(yīng)的模型和算法已經(jīng)相當(dāng)成熟。而在決策任務(wù)中，一旦給定預(yù)測參數(shù)$\hat{\mathbf{c}}$，現(xiàn)代求解器可以將問題視作確定性優(yōu)化直接求解。既然預(yù)測任務(wù)和決策任務(wù)都有成熟的方案，那么為什么我們還要嘗試將它們結(jié)合在一起？

文獻(xiàn)中的解釋——“與直接考慮決策誤差相比，基于預(yù)測誤差訓(xùn)練預(yù)測模型會(huì)導(dǎo)致更糟糕的決策?！庇萌嗽拋碚f就是：像$l_{\text{MSE}}(\hat{\mathbf{c}},\mathbf{c})$這樣的預(yù)測誤差，不能準(zhǔn)確地衡量決策的質(zhì)量。

在日常生活中，人們只關(guān)心決策的好壞，而不是各項(xiàng)指標(biāo)預(yù)測的準(zhǔn)確度。正如我們驅(qū)車趕往目的地時(shí)，只關(guān)心自己是否選中捷徑，而無須精確預(yù)測每段可能經(jīng)過的路段所耗費(fèi)的時(shí)間。

讓我們回到前文提到的線性優(yōu)化問題：假設(shè)實(shí)際成本向量為$\mathbf{c}=(0,1)$，最優(yōu)解為${\mathbf{w}}^{?}(\mathbf{c})=(0,1)$。當(dāng)我們將成本向量預(yù)測為$\hat{\mathbf{c}}=(1,0)$，其最優(yōu)解為${\mathbf{w}}^{?}(\hat{\mathbf{c}})=(1,0)$，預(yù)測的均方誤差$l_{\text{MSE}}(\hat{\mathbf{c}},\mathbf{c})=2$；當(dāng)我們將成本向量預(yù)測為$\hat{\mathbf{c}}=(0,3)$，其最優(yōu)解為${\mathbf{w}}^{?}(\hat{\mathbf{c}})=(0,1)$，預(yù)測的均方誤差$l_{\text{MSE}}(\hat{\mathbf{c}},\mathbf{c})=4$。

這個(gè)例子揭示了一個(gè)有趣的現(xiàn)象：后者雖然在預(yù)測誤差上比前者大，但在決策上卻是最優(yōu)的。

因此，即使預(yù)測模型表現(xiàn)出了較大的誤差，但只要預(yù)測的成本向量能引導(dǎo)我們做出正確的決策，這個(gè)預(yù)測模型就是有效的。這就是為什么我們需要考慮端對(duì)端預(yù)測后優(yōu)化，我們希望訓(xùn)練出的模型能夠引導(dǎo)我們做出最優(yōu)的決策，而不必預(yù)測出精確的成本向量。

那么，如果預(yù)測模型的預(yù)測結(jié)果足夠精確，那是不是可以摒棄使用端對(duì)端方法了呢？答案是肯定的。然而，不要忘記統(tǒng)計(jì)學(xué)家George E.P. Box有句名言： “All models are wrong, but some are useful.”

4.2 關(guān)于模仿學(xué)習(xí)

既然端對(duì)端方法展現(xiàn)了足夠的優(yōu)勢，那我們?yōu)槭裁床环粮みM(jìn)一點(diǎn)，采用模仿學(xué)習(xí)（Imitation Learning），把（最優(yōu)）決策行為${\mathbf{w}}^{?}(\mathbf{c})$作為標(biāo)簽，省去了中間的求解過程，直接訓(xùn)練模型${\hat{\mathbf{w}}}^{?}=\mathbf{g}(\mathbf{x},\mathbf{\theta })$預(yù)測最優(yōu)解呢？

毫無疑問，模仿學(xué)習(xí)在計(jì)算效率上具有顯著優(yōu)勢，因?yàn)樗?guī)避了計(jì)算效率的主要瓶頸：優(yōu)化求解。

然而，其局限性也很明顯。盡管研究人員已經(jīng)做出了許多嘗試，比如Kervadec等人的“Constrained deep networks: Lagrangian optimization via log-barrier extensions” [8]，但目前的預(yù)測模型，無論是線性回歸、決策樹、還是神經(jīng)網(wǎng)絡(luò)，在處理帶有硬約束（Hard Constraints）的問題上仍存在難度。因此，模仿學(xué)習(xí)的預(yù)測結(jié)果常常面臨可行性問題，特別是對(duì)于高維度、有復(fù)雜約束的優(yōu)化問題。

5. 如何進(jìn)行端對(duì)端預(yù)測后優(yōu)化？

開篇名義，這個(gè)章節(jié)將會(huì)討論端對(duì)端預(yù)測后優(yōu)化的若干方法，這些方法適用的優(yōu)化問題有所差異，但主要集中在成本向量$\mathbf{c}$未知、有線性目標(biāo)函數(shù)的問題上。需要明確的是，這里強(qiáng)調(diào)的是目標(biāo)函數(shù)的線性，并不意味著約束條件也必須是線性的。例如，在SPO+的相關(guān)論文中 [1]，作者們探討了具有二次約束的投資組合均值-方差模型。此外，對(duì)比、排序方法和損失函數(shù)近似法甚至對(duì)優(yōu)化問題的形式幾乎沒有特定要求。

盡管也存在基于決策樹的模型SPO Tree [9]，大部分方法還是依賴梯度下降更新參數(shù)。之前提到，端對(duì)端學(xué)習(xí)的關(guān)鍵是計(jì)算求解過程的梯度$\frac{?{\mathbf{w}}^{?}(\hat{\mathbf{c}})}{?\hat{\mathbf{c}}}$。然而，傳統(tǒng)的優(yōu)化求解器和算法往往并未提供梯度信息。

更壞的消息是：線性規(guī)劃、整數(shù)線性規(guī)劃等具有線性目標(biāo)函數(shù)的問題，其最優(yōu)解${\mathbf{w}}^{?}(\mathbf{c})$作為成本向量$\mathbf{c}$的函數(shù)，是一個(gè)分片常數(shù)函數(shù)（Piecewise Constant Function），它的一階導(dǎo)數(shù)要么為0，要么不存在。熟悉線性規(guī)劃敏感性分析的話，就會(huì)知道成本向量系數(shù)$\mathbf{c}$的元素發(fā)生變化時(shí)，最優(yōu)解${\mathbf{w}}^{?}(\mathbf{c})$要么不發(fā)生改變，要么會(huì)從可行域的一個(gè)極點(diǎn)跳到另一個(gè)極點(diǎn)。我們依然以線性規(guī)劃 max ? w 1 , w 2 { c 1 w 1 + c 2 w 2 : w 1 + w 2 ≤ 1 ， w 1 , w 2 ≥ 0 } \underset{w_1,w_2}{\max} \lbrace c_1 w_1 + c_2 w_2: w_1 + w_2 ≤ 1，w_1, w_2 ≥ 0 \rbrace w1?,w2?max?{c1?w1?+c2?w2?:w1?+w2?≤1，w1?,w2?≥0}為例，如圖：

既然梯度幾乎處處為0，梯度下降法似乎無法實(shí)施。然而，科研的魅力正是將不可能變?yōu)榭赡?。面?duì)這一挑戰(zhàn)，研究者們提出了多種解決策略：一類是尋找替代的梯度信息，用以更新模型參數(shù)；另一類索性重新設(shè)計(jì)一個(gè)（有非0梯度的）替代損失函數(shù)。這兩類思路基本囊括了基于梯度的端對(duì)端預(yù)測后優(yōu)化算法：

5.1 基于KKT條件的隱函數(shù)求導(dǎo)

Amos和Kolter提出“OptNet” [10]，通過求解KKT條件的偏微分矩陣線性方程組來計(jì)算求解器反向傳播的梯度。為了克服線性規(guī)劃中無法得到非0梯度的問題，Wilder等人 [11] 在線性目標(biāo)函數(shù)中加入了一個(gè)微小的二次項(xiàng)?；谶@類方法，后續(xù)的研究者展開了多方面的探索。例如，引入割平面法（Cutting-Plane Method）以處理整數(shù)問題 [12]，或使用障礙函數(shù)來替代拉格朗日罰函數(shù) [13]。

值得一提的是，這類方法不僅能計(jì)算出目標(biāo)函數(shù)成本向量的梯度，而且能夠得到約束條件中參數(shù)的梯度信息。

5.2 SPO+

不同于KKT方法，Elmachtoub和Grigas [1] 為目標(biāo)函數(shù)是線性（${\mathbf{c}}^{?}\mathbf{w}$）的決策誤差找到了一個(gè)凸且可導(dǎo)的替代損失函數(shù)SPO+ Loss。

在這里，對(duì)于一個(gè)最小化問題$\underset{\mathbf{w}\in \mathbf{W}}{\min }{\mathbf{c}}^{?}\mathbf{w}$，我們先定義一個(gè)決策損失“遺憾”：$l_{\text{Regret}}(\hat{\mathbf{c}},\mathbf{c})={\mathbf{c}}^{?}{\mathbf{w}}^{?}(\hat{\mathbf{c}})?{\mathbf{c}}^{?}{\mathbf{w}}^{?}(\mathbf{c})$，衡量實(shí)際成本向量$\mathbf{c}$下，實(shí)際目標(biāo)值${\mathbf{c}}^{?}{\mathbf{w}}^{?}(\hat{\mathbf{c}})$與最優(yōu)目標(biāo)值${\mathbf{c}}^{?}{\mathbf{w}}^{?}(\mathbf{c})$之間的差距，也可以理解為優(yōu)化間隙（optimality gap）。

由于${\mathbf{w}}^{?}(\mathbf{c})$沒有非0導(dǎo)數(shù)，這個(gè)損失函數(shù)同樣也沒有非0導(dǎo)數(shù)。Elmachtoub和Grigas [1] 找到了這個(gè)函數(shù)的一個(gè)凸上界作為替代：：
$$l_{\text{SPO+}}(\hat{\mathbf{c}},\mathbf{c})=?\underset{\mathbf{w}\in \mathbf{W}}{\min }\{(2\hat{\mathbf{c}}?\mathbf{c}{)}^{?}\mathbf{w}\}+2{\hat{\mathbf{c}}}^{?}{\mathbf{w}}^{?}(\mathbf{c})?{\mathbf{c}}^{?}{\mathbf{w}}^{?}(\mathbf{c})$$

對(duì)于損失函數(shù)$l_{\text{SPO+}}(\hat{\mathbf{c}},\mathbf{c})$，有次梯度：
$$2{\mathbf{w}}^{?}(\mathbf{c})?2{\mathbf{w}}^{?}(2\hat{\mathbf{c}}?\mathbf{c})\in \frac{?l_{\text{SPO+}}(\hat{\mathbf{c}},\mathbf{c})}{?\hat{\mathbf{c}}}$$

5.3 擾動(dòng)方法

同樣是線性目標(biāo)函數(shù)，擾動(dòng)方法則是另辟蹊徑，引入隨機(jī)擾動(dòng)來處理成本向量的預(yù)測值$\hat{\mathbf{c}}$。

Berthet等人 [4] 用在高斯隨機(jī)擾動(dòng)$\mathbf{\xi }$下最優(yōu)決策的期望值${\mathbb{E}}^{\mathbf{\xi }}[{\mathbf{w}}^{?}(\hat{\mathbf{c}}+\sigma \mathbf{\xi })]$代替${\mathbf{w}}^{?}(\hat{\mathbf{c}})$。如圖所示，${\mathbf{w}}^{?}(\hat{\mathbf{c}}+\sigma \mathbf{\xi })$是可行域極點(diǎn)（基本可行解）的離散型隨機(jī)向量，決策的期望值${\mathbb{E}}^{\mathbf{\xi }}[{\mathbf{w}}^{?}(\hat{\mathbf{c}}+\sigma \mathbf{\xi })]$實(shí)際上可視為可行域極點(diǎn)???????的概率加權(quán)平均（凸組合）。與${\mathbf{w}}^{?}(\hat{\mathbf{c}})$不同，只要$\hat{\mathbf{c}}$在${\mathbb{E}}^{\mathbf{\xi }}[{\mathbf{w}}^{?}(\hat{\mathbf{c}}+\sigma \mathbf{\xi })]$中發(fā)生一些微小的變化，可行域極點(diǎn)權(quán)重（其發(fā)生的概率）就會(huì)相應(yīng)變化。本質(zhì)上，擾動(dòng)方法通過為離散的解向量引入概率分布實(shí)現(xiàn)平滑，這種方法與機(jī)器學(xué)習(xí)中SoftMax的思想有著異曲同工之處。

接下來，我們“只”需要通過概率密度函數(shù)$f(\mathbf{\xi })$的積分求期望${\mathbb{E}}^{\mathbf{\xi }}[{\mathbf{w}}^{?}(\hat{\mathbf{c}}+\sigma \mathbf{\xi })]=\int {\mathbf{w}}^{?}(\hat{\mathbf{c}}+\sigma \mathbf{\xi })f(\mathbf{\xi })d\mathbf{\xi }$，然后發(fā)現(xiàn)好像做不到。在實(shí)際操作中，我們用樣本量為$K$的蒙特卡洛采樣來近似期望：
$${\mathbb{E}}^{\mathbf{\xi }}[{\mathbf{w}}^{?}(\hat{\mathbf{c}}+\sigma \mathbf{\xi })]\approx \frac{1}{K}\sum _{\kappa }^K{\mathbf{w}}^{?}(\hat{\mathbf{c}}+\sigma {\mathbf{\xi }}_{\kappa })$$

由于$\frac{?{\mathbb{E}}^{\mathbf{\xi }}[{\mathbf{w}}^{?}(\hat{\mathbf{c}}+\sigma \mathbf{\xi })]}{?\hat{\mathbf{c}}}$存在且非0，梯度問題由此引刃而解。

除了加法擾動(dòng)，Dalle等人 [14] 進(jìn)一步提出了乘法擾動(dòng)，同樣引入高斯隨機(jī)擾動(dòng)$\mathbf{\xi }$，但讓預(yù)測成本向量$\hat{\mathbf{c}}$與$e^{\sigma \mathbf{\xi }?1/2{\sigma }^2}$對(duì)應(yīng)位元素相乘。乘法擾動(dòng)消除了加法擾動(dòng)可能引起的正負(fù)號(hào)變化問題。在一些特定的應(yīng)用中，例如Dijkstra算法等，對(duì)成本向量有非負(fù)性的要求，乘法擾動(dòng)就非常有用。

基于擾動(dòng)方法，Berthet等人 [4] 利用了Fenchel-Young對(duì)偶的性質(zhì)，進(jìn)一步構(gòu)造了一個(gè)新的損失函數(shù)，用來降低$F^{\mathbf{\xi }}(\hat{\mathbf{c}})={\mathbb{E}}^{\mathbf{\xi }}[\underset{\mathbf{w}\in \mathbf{W}}{\min }\{(\hat{\mathbf{c}}+\sigma \mathbf{\xi }{)}^{?}\mathbf{w}\}]$的對(duì)偶間隙。令$\Omega ({\mathbf{w}}^{?}(\mathbf{c}))$為$F^{\mathbf{\xi }}(\mathbf{c})$的對(duì)偶，則有：
$$l_{\text{PFY}}(\hat{\mathbf{c}},{\mathbf{w}}^{?}(\mathbf{c}))={\hat{\mathbf{c}}}^{?}{\mathbf{w}}^{?}(\mathbf{c})?F^{\mathbf{\xi }}(\hat{\mathbf{c}})?\Omega ({\mathbf{w}}^{?}(\mathbf{c}))$$

這個(gè)損失函數(shù)可能看起來有些復(fù)雜，它甚至包含一個(gè)神秘的對(duì)偶函數(shù)$\Omega ({\mathbf{w}}^{?}(\mathbf{c}))$。但是，當(dāng)我們對(duì)其進(jìn)行求導(dǎo)操作時(shí)，會(huì)發(fā)現(xiàn)$\Omega ({\mathbf{w}}^{?}(\mathbf{c}))$實(shí)際上是常數(shù)，因此，梯度表達(dá)式非常簡單：
$$\frac{?l_{\text{PFY}}(\hat{\mathbf{c}},{\mathbf{w}}^{?}(\mathbf{c}))}{?\hat{\mathbf{c}}}={\mathbf{w}}^{?}(\mathbf{c})?{\mathbb{E}}^{\mathbf{\xi }}[{\mathbf{w}}^{?}(\hat{\mathbf{c}}+\sigma \mathbf{\xi })]$$

5.4 黑箱方法

面對(duì)${\mathbf{w}}^{?}(\mathbf{c})$的不可導(dǎo)問題，有一個(gè)更加簡單粗暴的方法，即將求解器函數(shù)視為一個(gè)“黑箱”，并利用解空間的幾何形狀等性質(zhì)找到替代梯度。

如圖所示，Pogancic等人 [3] 提出了“Differentiable Black-box”方法引入一個(gè)插值超參數(shù)$\lambda$。對(duì)于一個(gè)成本向量預(yù)測值$\hat{\mathbf{c}}$，在$\hat{\mathbf{c}}$與$\hat{\mathbf{c}}+\lambda \frac{?l(\hat{\mathbf{c}},\mathbf{c})}{?{\mathbf{w}}^{?}(\hat{\mathbf{c}})}$之間對(duì)分片常數(shù)損失函數(shù)$l(\hat{\mathbf{c}},\mathbf{c})$進(jìn)行線性插值，從而將其轉(zhuǎn)化為分片線性函數(shù)（Piecewise Affine Function），以此可得非0梯度。

此外，Sahoo等人 [7] 提出了一種相當(dāng)簡潔的方案，即用負(fù)單位矩陣$?\mathbf{I}$替代求解器梯度$\frac{?{\mathbf{w}}^{?}(\hat{\mathbf{c}})}{?\hat{\mathbf{c}}}$。我們可以將其稱為“Negative Identity”方法。從直觀角度理解，對(duì)于一個(gè)最小化問題$\underset{\mathbf{w}\in \mathbf{W}}{\min }{\mathbf{c}}^{?}\mathbf{w}$，我們希望通過如下方式更新成本向量的預(yù)測值$\hat{\mathbf{c}}$：沿著${\mathbf{w}}^{?}(\hat{\mathbf{c}})$需要上升的方向減少，沿著${\mathbf{w}}^{?}(\hat{\mathbf{c}})$需要下降的方向增加，這會(huì)使${\mathbf{w}}^{?}(\hat{\mathbf{c}})$接近最優(yōu)決策${\mathbf{w}}^{?}(\mathbf{c})$。另外，該研究也證明了，這個(gè)方法可以看作是“Differentiable Black-box”方法在特定超參數(shù)λ下的特例。

5.5 對(duì)比、排序方法：

Mulamba [5] 則是曲線救國，采用了 “噪聲對(duì)比估計(jì)（Noise Contrastive Estimation）” 的技巧，巧妙地計(jì)算出替代損失函數(shù)。

首先，由于我們的可行域$\mathbf{w}\in \mathbf{W}$是固定不變的，因此在訓(xùn)練集以及訓(xùn)練、求解過程中，我們可以自然地收集到大量的可行解，形成一個(gè)解集合$\Gamma$。

該方法的關(guān)鍵思路是，將非最優(yōu)可行解的子集$\Gamma ?{\mathbf{w}}^{?}(c)$作為負(fù)樣本，讓最優(yōu)解和“負(fù)樣本”之間的的差值盡可能大。對(duì)于一個(gè)最小化問題$\underset{\mathbf{w}\in \mathbf{W}}{\min }{\mathbf{c}}^{?}\mathbf{w}$，有：
$$l_{\text{NCE}}(\hat{\mathbf{c}},\mathbf{c})=\frac{1}{|\Gamma |?1}\sum _{\mathbf{w}\in \Gamma ?{\mathbf{w}}^{?}(\mathbf{c})}({\hat{\mathbf{c}}}^{?}{\mathbf{w}}^{?}(\mathbf{c})?{\hat{\mathbf{c}}}^{?}\mathbf{w})$$

受到這項(xiàng)工作構(gòu)造損失函數(shù)區(qū)分最優(yōu)解的啟發(fā)，Mandi等人 [6] 提出了一種新思路，將端對(duì)端預(yù)測后優(yōu)化任務(wù)轉(zhuǎn)化為一個(gè)排序?qū)W習(xí)(Learning to rank) [15]，學(xué)習(xí)一個(gè)目標(biāo)函數(shù)（如${\hat{\mathbf{c}}}^{?}\mathbf{w}$）作為排序得分，以便對(duì)可行解的子集$\Gamma$進(jìn)行正確排序（和使用真實(shí)成本向量$\mathbf{c}$時(shí)一致）。和之前的方法相比，這種方法的優(yōu)勢在于，它對(duì)使用的優(yōu)化方法和目標(biāo)函數(shù)的形式不加以限制。

例如，對(duì)于一個(gè)線性規(guī)劃問題，${\mathbf{c}}^{?}\mathbf{w}$可以被視為排序得分。對(duì)于預(yù)測的成本向量$\hat{\mathbf{c}}$，為了排序得分${\hat{\mathbf{c}}}^{?}\mathbf{w}$能在解集$\mathbf{w}\in \Gamma$中有正確的排序，我們可以采用以下三種經(jīng)典的排序?qū)W習(xí)方法：單文檔方法（Pointwise Approach）、文檔對(duì)方法（Pairwise Approach）、以及文檔列表方法（Listwise Approach）。

在單文檔方法中，我們希望成本向量的預(yù)測值$\hat{\mathbf{c}}$在可行解的子集$\Gamma$中的得分${\hat{\mathbf{c}}}^{?}\mathbf{w}$盡可能接近${\mathbf{c}}^{?}\mathbf{w}$；在文檔對(duì)方法中，我們可以在最優(yōu)解和其他解之間創(chuàng)造排序得分的差值；而在文檔列表方法中，我們根據(jù)排序得分使用SoftMax函數(shù)計(jì)算每個(gè)可能解$\mathbf{w}\in \Gamma$被排在最前面的概率$P(\mathbf{w}|\mathbf{c})$，然后定義損失為概率的交叉熵$l_{\text{LTR}}(\hat{\mathbf{c}},\mathbf{c})=\frac{1}{|\Gamma |}{\sum }_{\mathbf{w}\in \Gamma }P(\mathbf{w}|\mathbf{c})\log P(\mathbf{w}|\hat{\mathbf{c}})$。

5.6 損失函數(shù)近似法：

最后，我們來聊一個(gè)堪稱邪道的方法——損失函數(shù)近似法。當(dāng)我們的預(yù)測模型$\mathbf{g}(\mathbf{x},\mathbf{\theta })$預(yù)測出成本向量$\hat{\mathbf{c}}$后，我們需要尋找最優(yōu)解${\mathbf{w}}^{?}(\hat{\mathbf{c}})$，然后計(jì)算相應(yīng)的決策損失$l(\hat{\mathbf{c}},\mathbf{c})$。然而，這個(gè)過程面臨著兩個(gè)主要的問題：一是優(yōu)化求解過程計(jì)算效率低下，二是損失函數(shù)$l(\hat{\mathbf{c}},\mathbf{c})$可能不存在有效的梯度。

針對(duì)這些問題，Shah等人 [17] 提出了一個(gè)頗為驚人的方案：局部優(yōu)化決策損失（Locally Optimized Decision Loss）。他們提出對(duì)于任意決策誤差的損失函數(shù)$l(\hat{\mathbf{c}},\mathbf{c})$，我們都可以使用一個(gè)額外的神經(jīng)網(wǎng)絡(luò)模型$h_{\text{LODL}}(\hat{\mathbf{c}},\mathbf{c})$進(jìn)行擬合。具體來說，他們通過采樣預(yù)測成本向量和其對(duì)應(yīng)的真實(shí)值$(\hat{\mathbf{c}},\mathbf{c})$，訓(xùn)練近似函數(shù)模型$h_{\text{LODL}}(\hat{\mathbf{c}},\mathbf{c})$，其損失定義為真實(shí)損失函數(shù)$l(\hat{\mathbf{c}},\mathbf{c})$和近似損失函數(shù)$h_{\text{LODL}}(\hat{\mathbf{c}},\mathbf{c})$的均方誤差（MSE）：
$${\Vert l(\hat{\mathbf{c}},\mathbf{c})?h_{\text{LODL}}(\hat{\mathbf{c}},\mathbf{c})\Vert }^2$$

接下來，我們固定好模型$h_{\text{LODL}}(\hat{\mathbf{c}},\mathbf{c})$的參數(shù)，作為決策損失的近似。在這個(gè)近似的指導(dǎo)下，我們通過對(duì)$h_{\text{LODL}}(\mathbf{g}(\mathbf{x},\mathbf{\theta }),\mathbf{c})$執(zhí)行梯度下降操作來更新預(yù)測模型$\mathbf{g}(\mathbf{x},\mathbf{\theta })$的參數(shù)$\mathbf{\theta }$。這個(gè)流程既避免了求解優(yōu)化問題的計(jì)算成本，又確保了損失函數(shù)能夠有效地計(jì)算梯度。

雖然這種方法看似天方夜譚，實(shí)則根植于深度學(xué)習(xí)的一項(xiàng)核心理論——“萬能近似定理（Universal Approximation Theorem）”，即神經(jīng)網(wǎng)絡(luò)理論上具備擬合任何函數(shù)的能力。事實(shí)上，值函數(shù)的近似是強(qiáng)化學(xué)習(xí)中的一種常見策略。因此，用類似的方法擬合端到端預(yù)測后優(yōu)化的決策誤差中也是行得通的。

這種策略優(yōu)雅地規(guī)避了求解優(yōu)化問題的計(jì)算效率瓶頸（盡管在訓(xùn)練近似函數(shù)$h_{\text{LODL}}(\hat{\mathbf{c}},\mathbf{c})$的時(shí)候，優(yōu)化求解仍然難以避免），同時(shí)充分利用了神經(jīng)網(wǎng)絡(luò)在擬合復(fù)雜損失函數(shù)方面的強(qiáng)大能力。然而，這也帶來了額外的模型訓(xùn)練步驟，并且近似損失函數(shù)的準(zhǔn)確性將直接影響到最終模型的表現(xiàn)。盡管理論上神經(jīng)網(wǎng)絡(luò)具備表示任何函數(shù)的能力，但在實(shí)踐中，要訓(xùn)練神經(jīng)網(wǎng)絡(luò)有效地學(xué)習(xí)并近似特定函數(shù)可能并非易事。這涉及到一個(gè)復(fù)雜損失函數(shù)的優(yōu)化問題，可能存在大量的局部最優(yōu)解，而且可能受到過擬合、梯度消失、梯度爆炸等問題的影響。此外，這種方法在基準(zhǔn)數(shù)據(jù)集上的性能尚缺乏詳盡的比較，其實(shí)際效用仍待進(jìn)一步探索和證明。

6. 使用PyEPO進(jìn)行端對(duì)端預(yù)測后優(yōu)化

PyEPO（PyTorch-based End-to-End Predict-then-Optimize Tool） [16] 是我讀博期間的開發(fā)的工具，該工具的源代碼已經(jīng)發(fā)布在GitHub上，可以通過以下鏈接查找：https://github.com/khalil-research/PyEPO。它是一款基于Python的開源軟件，支持預(yù)測后優(yōu)化問題的建模和求解。PyEPO的核心功能是使用GurobiPy、Pyomo或其他求解器和算法建立優(yōu)化模型，然后將優(yōu)化模型嵌入到人工神經(jīng)網(wǎng)絡(luò)中進(jìn)行端到端訓(xùn)練。具體來說，PyEPO借助PyTorch autograd模塊，實(shí)現(xiàn)了如SPO+、黑箱方法、擾動(dòng)方法以及對(duì)比排序方法等多種策略的框架。具體使用方法可以查看文檔。

作為一款開源工具，PyEPO也歡迎社區(qū)的貢獻(xiàn)和反饋，我們也將持續(xù)更新和優(yōu)化其中的算法。

6.1 下載和安裝

要下載PyEPO，你可以從GitHub倉庫克隆：

git clone -b main --depth 1 https://github.com/khalil-research/PyEPO.git

之后進(jìn)行安裝：

pip install PyEPO/pkg/.

6.2 建立優(yōu)化模型

使用PyEPO的第一步是創(chuàng)建一個(gè)繼承于optModel類的優(yōu)化模型。由于PyEPO處理未知成本系數(shù)的預(yù)測后優(yōu)化，因此首先需要實(shí)例化一個(gè)具有固定約束和可變成本的優(yōu)化模型optModel。這樣一個(gè)優(yōu)化模型可以接受不同的成本向量，并能夠在固定的約束條件下找到相應(yīng)的最優(yōu)解。

在PyEPO中，optModel類的作用類似于一個(gè)黑箱對(duì)求解器進(jìn)行封裝，這意味著PyEPO并不一定要使用某種特定的算法或求解器。

對(duì)如下問題：
max ? x ∑ i = 0 4 c i x i s . t . 3 x 0 + 4 x 1 + 3 x 2 + 6 x 3 + 4 x 4 ≤ 12 4 x 0 + 5 x 1 + 2 x 2 + 3 x 3 + 5 x 4 ≤ 10 5 x 0 + 4 x 1 + 6 x 2 + 2 x 3 + 3 x 4 ≤ 15 ? x i ∈ { 0 , 1 } \begin{aligned} \underset{\mathbf{x}}{\max} & \sum_{i=0}^4 c_i x_i \\ s.t. \quad & 3 x_0 + 4 x_1 + 3 x_2 + 6 x_3 + 4 x_4 \leq 12 \\ & 4 x_0 + 5 x_1 + 2 x_2 + 3 x_3 + 5 x_4 \leq 10 \\ & 5 x_0 + 4 x_1 + 6 x_2 + 2 x_3 + 3 x_4 \leq 15 \\ & \forall x_i \in \{0, 1\} \end{aligned} xmax?s.t.?i=0∑4?ci?xi?3x0?+4x1?+3x2?+6x3?+4x4?≤124x0?+5x1?+2x2?+3x3?+5x4?≤105x0?+4x1?+6x2?+2x3?+3x4?≤15?xi?∈{0,1}?

PyEPO也提供了Gurobi的API，用戶能輕松地對(duì)各種優(yōu)化問題進(jìn)行建模，無需手動(dòng)編寫復(fù)雜的求解過程：

import gurobipy as gp
from gurobipy import GRB
from pyepo.model.grb import optGrbModelclass myOptModel(optGrbModel):def _getModel(self):# ceate a modelm = gp.Model()# variblesx = m.addVars(5, name="x", vtype=GRB.BINARY)# sensem.modelSense = GRB.MAXIMIZE# constraintsm.addConstr(3*x[0]+4*x[1]+3*x[2]+6*x[3]+4*x[4]<=12)m.addConstr(4*x[0]+5*x[1]+2*x[2]+3*x[3]+5*x[4]<=10)m.addConstr(5*x[0]+4*x[1]+6*x[2]+2*x[3]+3*x[4]<=15)return m, xoptmodel = myOptModel()

6.3 生成數(shù)據(jù)集

我們用隨機(jī)特征生成有高斯噪音的成本向量：

import torch
torch.manual_seed(42)num_data = 1000 # number of data
num_feat = 5 # feature dimension
num_cost = 5 # cost dimension# randomly generate data
x_true = torch.rand(num_data, num_feat) # feature
weight_true = torch.rand(num_feat, num_cost) # weight
bias_true = torch.randn(num_cost) # bias
noise = 0.5 * torch.randn(num_data, num_cost) # random noise
c_true = x_true @ weight_true + bias_true + noise # cost coef

對(duì)于端到端預(yù)測后優(yōu)化，只有成本向量$\mathbf{c}$作為標(biāo)簽是不夠的，我們還需要最優(yōu)解${\mathbf{w}}^{?}(\mathbf{c})$和相應(yīng)的目標(biāo)函數(shù)值。因此，我們可以使用optDataset。optDataset是在PyTorch的Dataset類的基礎(chǔ)上進(jìn)行擴(kuò)展的一個(gè)類，它允許我們利用optModel方便地獲取求解數(shù)據(jù)，并且可以被PyTorch的DataLoader直接使用。

# split train test data
from sklearn.model_selection import train_test_split
x_train, x_test, c_train, c_test = train_test_split(x_true, c_true, test_size=200, random_state=42)# build optDataset
from pyepo.data.dataset import optDataset
dataset_train = optDataset(optmodel, x_train, c_train)
dataset_test = optDataset(optmodel, x_test, c_test)# build DataLoader
from torch.utils.data import DataLoader
batch_size = 32
loader_train = DataLoader(dataset_train, batch_size=batch_size, shuffle=True)
loader_test = DataLoader(dataset_test, batch_size=batch_size, shuffle=False)

6.4 建立預(yù)測模型

由于PyEPO是基于PyTorch構(gòu)建的，所以我們可以像平常一樣使用PyTorch進(jìn)行模型的搭建，函數(shù)的使用，以及模型的訓(xùn)練等操作。這為使用各種深度學(xué)習(xí)技術(shù)的用戶提供了極大的便利。下面，我們將建立一個(gè)簡單的線性回歸模型作為預(yù)測模型：

import torch
from torch import nn# build linear model
class LinearRegression(nn.Module):def __init__(self):super(LinearRegression, self).__init__()self.linear = nn.Linear(num_feat, num_cost)def forward(self, x):out = self.linear(x)return out# init model
reg = LinearRegression()
# cuda
if torch.cuda.is_available():reg = reg.cuda()

6.5 模型的訓(xùn)練和測試

PyEPO的核心組件就是它的autograd優(yōu)化模塊，可以方便地調(diào)用前文中提到的各種方法，比如：

SPO+

import pyepo
# init SPO+ loss
spop = pyepo.func.SPOPlus(optmodel, processes=2)

擾動(dòng)方法

import pyepo
# init perturbed optimizer layer
ptb = pyepo.func.perturbedOpt(optmodel, n_samples=3, sigma=1.0, processes=2)
# init perturbed Fenchel-Younge loss
pfy = pyepo.func.perturbedFenchelYoung(optmodel, n_samples=3, sigma=1.0, processes=2)

黑箱方法

import pyepo
# init dbb optimizer layer
dbb = pyepo.func.blackboxOpt(optmodel, lambd=20, processes=2)
# init optimizer layer with identity grad
nid = pyepo.func.negativeIdentity(optmodel, processes=2)

對(duì)比、排序方法

import pyepo
# init NCE loss
nce = pyepo.func.NCE(optmodel, processes=2, solve_ratio=0.05, dataset=dataset_train)
# init constrastive MAP loss
cmap = pyepo.func.contrastiveMAP(optmodel, processes=2, solve_ratio=0.05, dataset=dataset_train)

import pyepo
# init pointwise LTR loss
ltr = pyepo.func.pointwiseLTR(optmodel, processes=2, solve_ratio=0.05, dataset=dataset_train)
# init pairwise LTR loss
ltr = pyepo.func.pairwiseLTR(optmodel, processes=2, solve_ratio=0.05, dataset=dataset_train)
# init listwise LTR loss
ltr = pyepo.func.listwiseLTR(optmodel, processes=2, solve_ratio=0.05, dataset=dataset_train)

訓(xùn)練

接下來，以SPO+為例，我們可以正常使用PyTorch進(jìn)行模型訓(xùn)練:

# set adam optimizeroptimizer = torch.optim.Adam(reg.parameters(), lr=5e-3)# train modereg.train()for epoch in range(5):# load datafor i, data in enumerate(loader_train):x, c, w, z = data # feat, cost, sol, obj# cudaif torch.cuda.is_available():x, c, w, z = x.cuda(), c.cuda(), w.cuda(), z.cuda()# forward passcp = reg(x)# spo+ lossloss = spop(cp, c, w, z)# backward passoptimizer.zero_grad()loss.backward()optimizer.step()# logregret = pyepo.metric.regret(reg, optmodel, loader_test)print("Loss: {:9.4f},  Regret: {:7.4f}%".format(loss.item(), regret*100))

由于不同的模塊可能有不同的輸入輸出，在使用這些模塊時(shí)，我們需要特別關(guān)注各模塊的接口文檔，確保我們的輸入輸出數(shù)據(jù)與其兼容，避免出現(xiàn)不一致的情況。

以擾動(dòng)優(yōu)化（perturbedOpt）為例，其訓(xùn)練過程和SPO+有所不同:

  # set adam optimizeroptimizer = torch.optim.Adam(reg.parameters(), lr=5e-3)# set some lossl1 = nn.L1Loss()# train modereg.train()for epoch in range(5):# load datafor i, data in enumerate(loader_train):x, c, w, z = data # feat, cost, sol, obj# cudaif torch.cuda.is_available():x, c, w, z = x.cuda(), c.cuda(), w.cuda(), z.cuda()# forward passcp = reg(x)# perturbed optimizerwe = ptb(cp)# lossloss = l1(we, w)# backward passoptimizer.zero_grad()loss.backward()optimizer.step()# logregret = pyepo.metric.regret(reg, optmodel, loader_test)print("Loss: {:9.4f},  Regret: {:7.4f}%".format(loss.item(), regret*100))

7. 結(jié)語

端到端預(yù)測后優(yōu)化是一項(xiàng)有趣的工作，也正是這項(xiàng)工作激發(fā)了我對(duì)優(yōu)化和機(jī)器學(xué)習(xí)的深入探索。我無比敬佩在這個(gè)領(lǐng)域中工作的研究者們，他們提出的各種方法都有著獨(dú)特的理論支撐和應(yīng)用價(jià)值。我們明白這只是一個(gè)開始，端對(duì)端預(yù)測后優(yōu)化這個(gè)領(lǐng)域還有有許多新的問題和理論等待我們?nèi)ヌ剿?。我期待在未來的研究?#xff0c;我們可以繼續(xù)深化對(duì)這個(gè)領(lǐng)域的理解，發(fā)現(xiàn)更多的可能性。

參考文獻(xiàn)

[1] Elmachtoub, A. N., & Grigas, P. (2021). Smart “predict, then optimize”. Management Science.

[2] Mandi, J., Stuckey, P. J., & Guns, T. (2020). Smart predict-and-optimize for hard combinatorial optimization problems. In Proceedings of the AAAI Conference on Artificial Intelligence.

[3] Pogan?i?, M. V., Paulus, A., Musil, V., Martius, G., & Rolinek, M. (2019, September). Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations.

[4] Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J. P., & Bach, F. (2020). Learning with differentiable pertubed optimizers. Advances in neural information processing systems, 33, 9508-9519.

[5] Mulamba, M., Mandi, J., Diligenti, M., Lombardi, M., Bucarey, V., & Guns, T. (2021). Contrastive losses and solution caching for predict-and-optimize. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence.

[6] Mandi, J., Bucarey, V., Mulamba, M., & Guns, T. (2022). Decision-focused learning: through the lens of learning to rank. Proceedings of the 39th International Conference on Machine Learning.

[7] Sahoo, S. S., Paulus, A., Vlastelica, M., Musil, V., Kuleshov, V., & Martius, G. (2022). Backpropagation through combinatorial algorithms: Identity with projection works. arXiv preprint arXiv:2205.15213.

[8] Kervadec, H., Dolz, J., Yuan, J., Desrosiers, C., Granger, E., & Ayed, I. B. (2022, August). Constrained deep networks: Lagrangian optimization via log-barrier extensions. In 2022 30th European Signal Processing Conference (EUSIPCO) (pp. 962-966). IEEE.

[9] Elmachtoub, A. N., Liang, J. C. N., & McNellis, R. (2020, November). Decision trees for decision-making under the predict-then-optimize framework. In International Conference on Machine Learning (pp. 2858-2867). PMLR.

[10] Amos, B., & Kolter, J. Z. (2017, July). Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning (pp. 136-145). PMLR.

[11] Wilder, B., Dilkina, B., & Tambe, M. (2019, July). Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 1658-1665).

[12] Mandi, J., & Guns, T. (2020). Interior point solving for lp-based prediction+ optimisation. Advances in Neural Information Processing Systems, 33, 7272-7282.

[13] Ferber, A., Wilder, B., Dilkina, B., & Tambe, M. (2020, April). Mipaal: Mixed integer program as a layer. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 34, No. 02, pp. 1504-1511).

[14] Dalle, G., Baty, L., Bouvier, L., & Parmentier, A. (2022). Learning with combinatorial optimization layers: a probabilistic approach. arXiv preprint arXiv:2207.13513.

[15] Liu, T. Y. (2009). Learning to rank for information retrieval. Foundations and Trends? in Information Retrieval, 3(3), 225-331.

[16] Tang, B., & Khalil, E. B. (2022). PyEPO: A PyTorch-based end-to-end predict-then-optimize library for linear and integer programming. arXiv preprint arXiv:2206.14234.

[17] Shah, S., Wilder, B., Perrault, A., & Tambe, M. (2022). Learning (local) surrogate loss functions for predict-then-optimize problems. arXiv e-prints, arXiv-2203.