編輯:杜偉、陳萍
混合整數規劃(MIP)是一類 NP 困難問題,來自 DeepMind、谷歌的一項研究表明,用神經網路與機器學習方法可以解決混合整數規劃問題。
混合整數規劃(Mixed Integer Program, MIP)是一類 NP 困難問題,旨在最小化受限於線性約束的線性目標,其中部分或所有變數被約束為整數值。混合整數規劃的形式如下:
![](https://img2.vitomag.com/b2/70/b270999e05c0430edd48b1c98656671f2ffeda8e.jpg)
MIP 已經在產能規劃、資源分配和裝箱等一系列問題中得到廣泛應用。人們在研究和工程上的大量努力也研發出了 SCIP、CPLEX、Gurobi 和 Xpress 等實用的求解器。這些求解器使用複雜的啟發式演算法來指導求解 MIP 的搜尋過程,並且給定應用上求解器的性能主要依賴於啟發式演算法適配應用的程度。
在本文中,來自 DeepMind、谷歌的研究者展示了機器學習可以用於從 MIP 實例資料集自動構建有效的啟發式演算法。
![](https://img2.vitomag.com/c0/d2/c0d28630ddd0fc4281387c8e4c284d375fdf99a3.jpg)
在實踐中經常會出現這樣的用例,即應用程序需要用不同的問題參數解決同一高級語義問題的大量實例。
文中此類「同質」資料集的示例包括:(1)最佳化電網中發電廠的選擇以滿足需求,其中電網拓撲保持不變,而需求、可再生能源發電等則因情況而異(2)解決了谷歌在生產系統中的一個包裝問題,在這個系統中,要包裝的「items」和「bins」的語義基本保持不變,但它們的尺寸在不同的實例之間有所波動。
然而,現有的 MIP 求解器無法自動構造啟發式來利用這種結構。在具有挑戰性的應用程序中,使用者可能依賴專家設計的啟發式,或者以放棄潛在的大型性能改進為代價。而機器學習提供了在不需要特定於應用程序專業知識的情況下進行大規模改進的可能性。
![](https://img2.vitomag.com/2c/76/2c7673e6bb4c2b1d182a3e8de0a5786eb621b5e6.jpg)
論文地址:https://arxiv.org/pdf/2012.13349.pdf
該研究證明,機器學習可以構建針對給定資料集的啟發式演算法,其性能顯著優於 MIP 求解器中使用的經典演算法,特別是具有 SOTA 性能的非商業求解器 SCIP 7.0.1。
該研究將機器學習應用於 MIP 求解器的兩個關鍵子任務:(1)輸出對滿足約束的所有變數的賦值(如果存在此類賦值)(2)證明變數賦值與最優賦值之間的目標值差距邊界。這兩個任務決定了該方法的主要元件,即:Neural Diving、 Neural Branching(見圖 1)。
![](https://img2.vitomag.com/59/39/59395361db5563d2ae2f377ed07b81ec8f8e4f43.jpg)
該研究在不同的資料集上進行了評估,這些資料集包含來自實際應用的大規模 MIP,包括來自谷歌生產系統和 MIPLIB 的兩組資料。來自所有資料集的大多數 MIP 組合集在解算後都有 10^3-10^6 個變數和約束,這明顯大於早期的工作。一旦在給定的資料集上訓練 Neural Diving 和 Neural Branching 模型,它們就被集成到 SCIP 中,以形成專門針對該資料集的「神經求解器」。基線是 SCIP,其重點參數通過網格搜尋在每個資料集上進行調整,稱之為 Tuned SCIP。
將神經求解器和 Tuned SCIP 與原始對偶間隙(primal-dual gap)在一組實例上的平均值進行比較,圖 2 所示,神經求解器在相同的運行時間內提供了更好的間隙,或者在更短的時間內提供了相同的間隙,在五個資料集中進行評估,有四個資料集的 MIP 最大,而第五個資料集的性能與 Tuned SCIP 性能相匹配。據了解,這是第一次使用機器學習在大規模真實應用資料集和 MIPLIB 上得到如此大的改進。
![MIP 表示與神經網路架構](https://img2.vitomag.com/30/46/304662f361a8d47a9c15de629a3aa543a6376f2d.jpg)
MIP 表示與神經網路架構
該研究描述了 MIP 如何表示為神經網路的輸入,並用來學習 Neural Diving、Neural Branching 模型的架構。該研究使用的深度學習架構為一種圖神經網路,特別是圖卷積網路 (GCN)。
將 MIP 表示為神經網路的輸入
該研究使用 MIP 的二部圖表示,方程(1)可用於定義二部圖,其中圖中的一組 n 個節點對應於被最佳化的 n 個變數,另一組 m 個節點對應於 m 個約束,參見圖 3。
![神經網路架構](https://img2.vitomag.com/6a/27/6a2719297d0e96926f802790107f072a566d09c5.jpg)
神經網路架構
下面介紹一下 Neural Diving 、 Neural Branching 所使用的網路架構中共同的方面。
給定一個 MIP 的二部圖表示,該研究使用 GCN 來學習 Neural Diving 、Neural Branching 模型。設 GCN 的輸入為圖
![](https://img2.vitomag.com/a9/f6/a9f6c5226d8802a1c12ddabcdfdd47a441e61d34.jpg)
,其中 V 為節點集合、ε為邊集合、A 為圖鄰接矩陣。對於 MIP 二部圖,V 是 n 個變數節點和 m 個約束節點的並集,大小 N := |V| = n + m。一個單層 GCN 用來學習計算輸入圖中每個節點的 H 維連續向量表示,稱為節點嵌入。
在 MIP 和 GCN 體系架構中二部圖表示的兩個關鍵性質是:(1)網路輸出對變數和約束的排列是不變的(2)可以使用同一組參數應用於不同大小的 MIP。
這兩個性質很重要,因為變數和約束可能沒有任何規範順序,而且同一應用程序中的不同實例可能具有不同數量的變數和約束。
架構改進
該研究對上述體系架構進行了改進,這些改進提高了網路的性能,主要體現在以下方面:
該研究修改了 MIP 二部圖的鄰接矩陣 A ,以包含來自 MIP 約束矩陣 A 的係數,而不在是表示邊緣存在的二進位制值;
該研究通過連接來自第 l 層的節點嵌入來擴展第 l + 1 層的節點嵌入;
該研究在每一層的輸出處應用 layer norm,使得 Z^ (l+1) =
此外,該研究還探索了可以用來替代的架構,這些架構對節點和邊使用嵌入,並使用單獨的 MLP 來計算。當在每一層中使用具有高維邊嵌入的此類網路時,它們的記憶體使用量可能會比 GCN 高得多,因為 GCN 只需要鄰接矩陣,可能不適合 GPU 記憶體,除非以精度為代價減少層數。GCN 更適合擴展到大規模 MIP。
資料集
表 1 中總結了資料集的詳細資訊,除 MIPLIB 之外的所有資料集都是特定於應用程序的,即它們只包含來自單個應用程序的實例。
![](https://img2.vitomag.com/04/b9/04b9efe91740a6063c0238fcf0cba51f599e2cbe.jpg)
解算後各種資料集的 MIP 大小如圖 4 所示:
![](https://img2.vitomag.com/f3/c2/f3c205a0fe101b72b263e393a5233814ee3576b5.jpg)
除了 MIPLIB 之外的所有資料集,該研究將實例隨機拆分為 70%、15% 和 15% 的不相交子集來定義訓練集、驗證集和測試集。對於 MIPLIB,該研究使用來自 MIPLIB 2017 基準集的實例作為測試集。在刪除與 MIPLIB 2017 基準集的重疊實例後,分別使用 MIPLIB 2017 Collection Set 和 MIPLIB 2010 set 作為訓練集和驗證集。對每個資料集來說,訓練集用於學習該資料集的模型,驗證集用於調整學習超參數和 SCIP 的元參數,測試集用於報告評估結果。
評估
首先該研究單獨評估了 Neural Diving、 Neural Branching,後續又進行了聯合評估。不管在哪種情況下,該研究都評估了與訓練集分離的 MIP 測試集,以衡量模型對未見實例的泛化能力。並使用 gap plot 和 survival plot 呈現結果。
校準時間(Calibrated time):所有資料集和比較任務所需的評估工作量需要 160000 多個 MIP 解算,以及近一百萬個 CPU 和 GPU 小時。為了滿足計算需求,該研究使用了一個共享的、異構的計算集群。
為了提高準確性,對於每個求解任務,該研究定期在同一臺機器上的不同執行緒上解決一個小的校準 MIP。該研究還使用在同一臺機器上解決任務時的校準 MIP 求解數的估計來測量時間,然後使用參考機器上的校準 MIP 求解時間將這個量轉換為時間值。
Neural Diving
在本節中,研究者用本文方法來學習 diving-style 原始啟發式的方法,該演算法從給定的實例分佈為 MIP 生成高質量的賦值。思想是訓練一個生成模型,對 MIP 的整數變數進行賦值,從這些整數變數中可以抽樣部分賦值。該研究使用 SCIP 獲得高質量的賦值(不一定是最優的)作為 MIP 訓練集的目標標籤。
一旦在這些資料上進行了訓練,該模型就可以預測來自同一問題分佈的未見實例上的整數變數值。模型預測中所表示的不確定性被用於定義對原始 MIP 的部分賦值,該初始 MIP 固定了很大一部分整型變數。這些非常小的 sub-MIP 可以使用 SCIP 快速解決,產生高質量的可行賦值。
解決方案預測作為條件生成模型
考慮一個整數程序(即,所有變數都是整數),其參數為 M = (A, b, c)(見方程 1),並在一組整數變數 x 上有一個非空可行集。假設最小化,該研究使用目標函數定義 x 上的一個能量函數:
![](https://img2.vitomag.com/e5/55/e5550c6e4e0cbca5d53e1174c118f5acbb043839.jpg)
注意,所有變數都使用了相同的 MLP,參見圖 5:
![模型預測與經典求解器相結合](https://img2.vitomag.com/5b/64/5b6446a5c645678ca1b00afc671e270ec0adc430.jpg)
模型預測與經典求解器相結合
該研究使用 SelectiveNet 方法訓練了一個額外的二元分類器,可以用來判斷哪些變數需要預測,哪些不需要預測,並最佳化變數之間的「coverage」,將其定義為預測變數數與未預測變數數之比。
通過分配或收緊大部分變數的邊界,該研究顯著地減少了問題的規模,並熱啟動 SCIP,以在更短的時間內找到高質量的解決方案。
這種方法還提供了實際的計算優勢:預測抽樣和解搜尋是完全並行的。研究者可以重複和獨立地從模型中提取不同的樣本,並且樣本的每個部分賦值都可以獨立地求解。
結果
該研究在訓練集上為每個資料集訓練一個 GNN,並在驗證集上調整超參數。圖 6 為原始間隙(primal gap)與基線 SCIP 的平均結果。
![](https://img2.vitomag.com/08/9f/089fa83dd5c8cded388f613756894991667b6ac5.jpg)
與 SCIP 相比,該研究在並行和順序運行方面,在所有資料集上以更短的時間產生更好的原始邊界。研究者認為該方法的優勢是能迅速找到好的解決方案,但有時它不能找到最優或接近最優的解決方案。這可以從圖 7 的 survival plot 中看出,Neural Diving 方法在較短的時間限制下勝出,但在 Electric Grid Optimization 和 MIPLIB 資料集上不如 SCIP。
![](https://img2.vitomag.com/32/3b/323bc356e43c7fe449e1daa5cbf9bf71a6a13b93.jpg)
該研究在兩個資料集上(Google Production Packing 、 NN Verification,如圖 8、9 所示)引入了兩個額外的結果,並且將 Neural Diving、Gurobi 求解器進行結合:該研究以同樣的方式分配變數,但使用 Gurobi 而不是 SCIP 來解決剩下的問題。
![](https://img2.vitomag.com/d4/c2/d4c2075c08f246dd1303a7f3ff3dada2e9e8fec0.jpg)
除了在上表 1 中的資料集上評估 Neural Diving 之外,研究者還通過修改自身方法來求解 MIPLIB 2017 Collection Set 中的開放實例。這些實例是 MIPLIB 2017 Collection Set 能夠提供的 hardest 的問題。
下表 2 展示了與之前最知名解相比改進後的目標值。
![](https://img2.vitomag.com/c6/ba/c6bae580d13b2ccb36b39bb78498b60b5c6ccd9e.jpg)
Neural Branching
分支定界(branch-and-bound)過程在每次迭代時需要做出兩個決策,即擴展哪個葉節點以及在哪個變數上分支。研究者專注於後一個決策。變數選擇決策的質量對求解 MIP 時分支定界所採取的步驟數量具有重大影響。通過模擬節點高效但計算昂貴的 expert 的行動,他們使用深度神經網路來學習變數選擇策略。
通過將昂貴 expert 的策略提煉到神經網路中,研究者尋求保持大致相同的決策質量,但大大減少了做出決策所需時間。給定樹節點的決策完全是該節點的本地決策,因此學習策略只需要將節點的表示而不是整個樹作為輸入,由此實現更強的可擴展性。
為了證明 expert 資料生成的可擴展性得到了提升,研究者將 ADMM expert 與 Gasse 等人於 2019 年使用的 expert,即 Google Production Packing 和 MIPLIB 上的 Vanilla Full Strong Branching (VFSB)進行了比較。
下圖 10 展示了 60 小時內兩個 expert 生成的每個分支定界節點中變數數量直方圖,該節點位於兩個資料集中變數數量最多的節點上。
![](https://img2.vitomag.com/11/d4/11d431e05da9fee2f74576188cedddf76a977803.jpg)
模仿學習是給定 expert 行為示例的情況時尋求學習 expert 策略的演算法的統稱。研究者在本文中將模仿學習表述為一個監督學習問題,並考慮了三種變體:克隆 expert 策略、隨機移動的蒸餾和 DAgger。
在實驗中,研究者將他們選擇的三種模仿學習變體作為超參數對每個資料集進行調整。他們使用這三種變體為每個資料集生成了資料和訓練策略,並選定了三小時內在驗證集實例上取得最低平均對偶間隙(dual gap)的策略,接著在測試集上對選定的策略進行評估以得出相關結果。
結果
研究者在最佳化雙重約束的任務上對學得的分支策略進行評估。下圖 11 展示了 Neural Branching 與 Tuned SCIP 的平均對偶間隙曲線圖:
![](https://img2.vitomag.com/4d/74/4d74d063ac1941685a8556561c3f49fb54527abc.jpg)
下圖 12 展示了將一個資料集的目標最優間隙應用於每個測試集 MIP 實例的對偶間隙時計算得出的生存曲線。研究者確認了上圖 11 得出的結論,即在除 Google Production Planning 和 MIPLIB 之外的所有資料集上,Neural Branching 能夠在所有時間期限內持續地求解出更高分數的測試實例。
![聯合評估](https://img2.vitomag.com/ae/e6/aee6fb3089c030ba391dadbe72c8c94e30bed6ad.jpg)
聯合評估
研究者將 Neural Branching 和 Neural Diving 結合成了單個求解器,這種做法使得在 Tuned SCIP 上實現了顯著加速。他們通過 PySCIPOpt 包提供的接口使用並將學得的啟發式方法集成到 SCIP 中。
此外,研究者考慮了四種結合 Neural Branching 和 Neural Diving 的可能方法,具體如下:
單獨的 Tuned SCIP;
Neural Branching+Neural Diving(序列)使用神經啟發式方法;
Neural Branching 僅使用學得的 branching 策略;
Tuned SCIP+Neural Diving(序列)僅使用連續版本的 Neural Diving。
下圖 13 展示了作為運行時間函數的平均原始對偶間隙曲線,神經求解器在四個資料集上顯著優於 Tuned SCIP。
具體來講,在 NN Verification 資料集上,神經求解器在大的時間期限內平均原始對偶間隙比 Tuned SCIP 好 5 個數量級以上;在 Google Production Packing 資料集上,Neural Branching 和 Neural Diving(序列)更快地實現更低的間隙,在比 Tuned SCIP 時間少 5 倍多的情況下達到了 0.1 的間隙,但 Tuned SCIP 最後趕上了;在 Electric Grid Optimization 資料集上,神經求解器以更高的運行時間實現了低一半的間隙;在 MIPLIB 資料集上,Tuned SCIP+Neural Diving(序列)組合以更高的運行時間實現了 1.5 倍的間隙。
下圖 14 展示了作為運行時間函數的生存曲線。研究者進一步確認了上圖 13 的觀察結果,同樣在四個資料集上,神經求解器在給定時間期限內求解測試集問題時能夠取得比 Tuned SCIP 更高的分數。因此,這些結果表明學習可以顯著提升 SCIP 等強大求解器的性能。
![](https://img2.vitomag.com/80/13/8013250ff2eddc58c7227fad0f36c6fa3ad9cb6c.jpg)