論文解讀者：史銘偉，胡明傑，趙田田，陳宇文
編者按：
深度學習近十年的飛速發展帶動了各行各業對于資料驅動的研究熱潮，運籌學也不例外。本文将展開讨論Deepmind于2020年發表的有關深度學習對混合整數模型加速方法性能的提升。
論文資訊：Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, Yori Zwols. Solving Mixed Integer Programs Using Neural Networks, arXiv,2020
傳統的混合整數規劃中通常是基于分支定界法（branch and bound），通過不斷求解連續凸松弛問題找出最優解，但是理論上需要求解的松弛問題個數随着整數變量次元上升呈指數倍數增長。是以，實際中我們會添加許多加速方法去減少需要求解的松弛問題數量，其中有很多加速方法的效果取決于混合整數規劃的問題結構或是目前分支定界已有的資訊，但是很多時候由于模型過于複雜，我們可能無法直接提取出這類資訊，而這正好是深度學習方法的優勢，它能基于充足的資料通過黑盒優化提供一個預測模型，捕捉我們一些我們難以解釋的有效資訊。本文介紹了Deepmind于2020年發表的有關深度學習在運籌優化中的運用[1]。論文核心是使用神經網絡提升傳統混合整數規劃中兩種常見的啟發式方法的性能：下潛（Diving）搜尋和分支（branching）選取。其主要思想還是利用神經網絡基于資料的預測能力對某一類特定問題求解實作加速。
傳統混合整數規劃中的下潛和分支方法
結合神經網絡的下潛和分支方法
在本篇論文中，作者将學習的方法引入下潛和分支方法選取的優化，我們分别稱之為neural diving和neural branching。
1. Neural diving
圖1 MIP的二分圖表示用于神經網絡的輸入
接着我們可以将之前混合整數規劃的二分圖作為輸入，将它遞交給圖卷積神經網絡進行分類監督學習。如圖二所示。對于圖神經網絡來說，将限制條件和限制目标對應的節點當成輸入，圖卷積神經網絡對二分圖每個節點所連的邊進行卷積操作,這樣就可以友善抽取特征。最後将抽取特征的矩陣作為輸入送入到多層感覺機，我們就可以進行分類預測了。因為分類的标簽有多個結果，是以每個二分圖的節點輸出滿足伯努利分布。具體實作細節可以參考論文第6部分[1]。
圖2 MIP二分圖，圖神經網絡，條件獨立模型之間的轉化
2. Neural Branching
分支變量的選擇是影響分支定界算法效率的關鍵因素。高品質的分支變量能夠有效減少分支定界算法的疊代次數。強分支（FBS）政策在實踐中具有較好的性能，相比于其他分支政策，建構的分支搜尋樹的規模往往更小。每次搜尋時，FBS通過模拟所有候選變量的一步分支結果，并選擇bound提升效果最好的變量進行分支。然而，實際中FBS每步的計算成本是非常高昂的。我們可以通過神經網絡模仿學習（ Imitation Learning）啟發式政策（專家政策）。通過将計算成本高昂的專家政策蒸餾至神經網絡，我們可以在近似保留解的品質的前提下大幅減少計算時長。更重要的是，在一個給定節點的分支變量決策隻需要節點的局部資訊，網絡隻需要輸入節點的相關特征，這使得該方法具有很好的可擴充性。計算成本高昂的專家政策被用來在離散狀态下一次性生成訓練資料。即使如此，由于FBS過高的計算成本，離線資料生成也非常困難 ，論文提出了來加速專家政策，通過在一個批次中同時處理多個LP來加速求解。
對于模仿學習，論文考慮了三種變形：專家政策克隆（expert policy cloning)，随機移動蒸餾（distillation with random moves）以及DAgger。蒸餾是最簡單的方式，在每個節點預測專家政策的輸出。然而，這種方法對于分布偏移（distribution drift）不夠魯棒。當根節點發生錯誤時，可能導緻後續節點與訓練看到的節點完全不同。為了解決上述問題，可以在訓練過程中結合随機移動與專家政策，在運作專家政策的同時以10%的機率随機采取一個動作。DAgger将随機移動蒸餾和專家輸入相結合，用作學習的目标。這會産生一步DAgger資料，可以利用其重新訓練智能體。
在實驗中，作者将三種模仿學習變體的選擇視為超參，為每個資料集生成資料，使用所有三種變體政策進行訓練并根據三小時内在驗證集上的表現選出最優政策。具體實作細節可以參考論文第7部分[1]。
數值實驗結果
為了驗證本文的方法在執行個體求解中具有一定的優越性，作者團隊進行了數值實驗。
他們将神經網絡在這些資料集上分别進行了訓練，然後使用學習增強的SCIP算法求解測試集。對照的标準是調優的SCIP算法（本質是SCIP算法；通過在每個資料集上分别進行網格搜尋，來調整算法中的參數）。他們設定一個較大的時間限制，并在該時間範圍内分别使用兩種算法處理同一組執行個體，然後比較它們在某一時刻對應求解結果的平均對偶間隙。實驗結果如下圖所示。
圖3. 本文方法和原始SCIP算法：在不同運作時間下的平均對偶間隙
在評估結果中，學習增強的SCIP算法在四個資料集上都有明顯的加速效果：在相同的運作時間内，它計算的結果具有更小的間隙；或者說，它需要更少的時間達到相同的間隙。具體地，對于其中三個資料集，它獲得了1.5倍, 2倍 和1萬倍更好的效果；對于第四個資料集（Google Production Packing），它能夠以原始算法5倍的速度讓平均對偶間隙下降到0.1。而對于第五個資料集，它取得了和調優SCIP不相上下的結果。
可以看出，對于大規模的現實世界應用資料集和MIPLIB，本文的方法都取得了優于SCIP的結果。在這項工作之前，還沒有哪一種方法能夠在這些數值實驗中取得如此程度的優勢。但是，這裡有兩點值得注意：
• 一個是比較的标準。某一時刻所對應平均對偶間隙的大小，并不是求解器性能的主要衡量标準。根據目前公認的測試标準，一般是給定最大求解時間，考慮求解器在某一個資料集上能按時求解的問題數量，以及它們的平均求解時間。是以，文中的資料結果可能放大了算法的優勢。
• 另一個是資料集的選取。實際上，隻有MIPLIB包含了來自不同應用場景的例子。而對于其他的四個資料集，它們的執行個體都分别來自于同一應用背景。對于這四個資料集而言，它們在訓練時給算法輸送的是大量的同類問題，而機器學習的優勢正在于提取同類問題的特征結構，是以算法能在測試集上取得好的結果，我們并不感到意外。MIPLIB也有相同的缺點。盡管例子來自不同背景，但是對于測試集中的問題，我們也總能在訓練集中找到結構相似的執行個體。是以，本文提出的方法未必具有很強的泛化能力。
盡管數值實驗的結果并不完美，但我們可以肯定，本文的方法對于特定結構的問題求解有着一定的加速效果。事實上，也有其他一些文章嘗試利用深度學習算法加速整數規劃的求解。Morabit M et al. (2021) 提出了利用神經網絡加速列生成算法。該算法通過學習一個神經網絡，在每步疊代時，從一組列集合中預測出最佳的列加入列生成的主問題，進而加速列生成算法的收斂。文章證明該算法在VRP問題執行個體上使得計算時長提高了30%[3]。
參考文獻
[1] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, Yori Zwols. Solving Mixed Integer Programs Using Neural Networks, arXiv,2020
[2] “DeepMind 激起千層浪的神經網絡求解 MIP 論文，并非無所不能”, https://www.ithome.com/0/569/302.htm
[3] Morabit M, Desaulniers G, Lodi A. Machine-learning–based column selection for column generation. Transportation Science, 2021, 55(4): 815-831.