論文閱讀筆記,個人理解,如有錯誤請指正,感激不盡!該文分類到Machine learning alongside optimization algorithms。

1 混合整數(shù)規(guī)劃求解

混合整數(shù)規(guī)劃問題(MIP)目前比較有效的算法就是branch and bound,branch and cut等。很多商業(yè)的或者非商業(yè)的MIP solver用的都是這些框架。branch and bound構(gòu)建MIP的搜索數(shù),通過搜索策略(DFS、BFS等)對分支樹進行搜索,通過求解節(jié)點的linear relaxation(LP)獲得節(jié)點的下界(lower bound)。如果LP解滿足整數(shù)約束(IP),則可認為找到了原問題的一個可行解(feasible solution),branch and bound記錄在搜索過程中找到的可行解,并維護一個最優(yōu)可行解作為全局的上界。當節(jié)點的下界比上界還差時,則減掉該支路。最終遍歷所有支路,獲得最優(yōu)解。

2 Primal Heuristic

通過branch and bound,branch and cut等求解MIP時,通常需要花費大量的計算時間,因為很多問題的LP模型獲得的lower bound非常差。在分支節(jié)點上運行heuristic算法對可行解進行搜索,可大大提高搜索的速度。比如在前期通過heuristic找到一個較好的上界,可以使得branch and bound在搜索的過程中減掉很多沒用的支路,從而加快優(yōu)化的速度。

在現(xiàn)在常用的MIP solver中已經(jīng)集成了很多成熟的heuristic算法,例如在IBM 的CPLEX中對heuristic有這樣一段說明:

何為探試?

定義探試,并描述 CPLEX 在 MIP 優(yōu)化中應(yīng)用探試的條件。

在 CPLEX 中,探試是一個過程,用于嘗試快速生成良好或近似的問題解,但缺少理論保證。在求解 MIP 的上下文中,探試是可以生成一個或多個解的方法,它可滿足所有約束和所有整數(shù)性條件,但沒有關(guān)于是否已找到最佳可能解的指示。

這些探試解集成到分支裁剪中,在提供最優(yōu)性證明方面可實現(xiàn)與分支所生成的任何解相同的優(yōu)勢,在許多情況下,它們可以加快最終最優(yōu)性證明的速度,或者可以提供次最優(yōu)但高質(zhì)量的解,而所需的時間比單單進行分支更短。使用缺省參數(shù)設(shè)置時,CPLEX 將在探試可能有益時自動調(diào)用探試。

CPLEX 提供了探試系列,用于在分支裁剪過程中尋找節(jié)點(包括根節(jié)點)處的整數(shù)解。下列主題對這些探試系列進行闡述。

其中一個比較關(guān)鍵的問題就是:在分支樹的哪些節(jié)點運行heuristic有可能獲得更好的結(jié)果?這樣就引出了這篇文章的motivation:通過對模型的訓練,將機器學習的模型集成到MIP的求解過程中,在分支節(jié)點中模型決定是否運行heuristic。模型必須是online的,即訓練好以后,在進行預(yù)測時只知道當前節(jié)點以及分支樹的信息,整顆分支樹或者剩下節(jié)點的信息。

在這篇文章中,作者給這個模型取了一個很有深意的名字,叫oracle,中文翻譯過來叫“神諭”,簡直是綿羊放山羊屁--既洋氣又騷氣……

3 數(shù)據(jù)特征

機器學習是通過輸入的數(shù)據(jù)來給出預(yù)測的結(jié)果,而應(yīng)當輸入數(shù)據(jù)的特征應(yīng)當良好地反映問題當前的狀態(tài),這樣才能給出準確的結(jié)果。這篇論文中使用了49個數(shù)據(jù)特征:

Global features通過一些"gap"描述了當前搜索的狀態(tài);Node LP features使用了節(jié)點N的LP解來指示一些節(jié)點的特征(括號中的x2表示該特征包含了更細一級的兩個特征,下同);Scoring Features for Fractional Variables受啟發(fā)于大多數(shù)diving heuristics中使用的scoring functions,該函數(shù)主要用于選取下一個分支的變量。

4 訓練數(shù)據(jù)收集

機器學習的一大關(guān)鍵(亦是難點)就是訓練數(shù)據(jù)的收集。給定一個MIP算例集合,,一個用于搜索過程中的啟發(fā)式算法,那么關(guān)于的數(shù)據(jù)集可以從每一個算例上獲取,最終的訓練集為。

作者在每個分支節(jié)點上運行,然后收集0-1分類標簽值,以及數(shù)據(jù)特征向量。如果在節(jié)點找到了一個可行解,否則為0。但是如果在節(jié)點找到了一個更好的可行解,那么有可能會影響到在之后的節(jié)點的值。這樣收集的數(shù)據(jù)是有問題的。

因此作者采取的數(shù)據(jù)收集策略是:在每個節(jié)點運行,但是找到的可行解并不替換當前的可行解,這樣從分支定界的角度看,就相當于每個節(jié)點都不運行了。其次,收集的數(shù)據(jù)時,其他的啟發(fā)式算法都采用默認設(shè)置(一個solver在求解過程中會調(diào)用多種heuristic)。

5 實驗

作者修改了開源的SCIP規(guī)劃求解器,并使用CPLEX作為SCIP的LP solver。機器學習采用框架scikit-learn,使用logistic regression (LR)來學習一個二進制的分類模型。

作者選取了SCIP中10個Heuristic算法進行訓練,每個算法訓練了一個模型,運行時10個模型都加載進去,策略是Run-When-Successful,即oracle說能成功的時候就運行該heuristic,否則不運行。其他啟發(fā)式算法則采用默認設(shè)置。所提出的框架在MIPLIB2010 Benchmark上的對比結(jié)果如下(DEF表示使用SCIP默認設(shè)置,ML采用提出的oracle):

其中Primal integral為評判搜索過程中算法好壞的,粗略的介紹如下圖,總之就是該指標越小越好:

可以看到,相比默認設(shè)置,作者提出的結(jié)合oracle在各項指標上均取得不錯的效果。其實從訓練的結(jié)果來看,準確率是非常低的,但是默認的設(shè)置下準確率(能找到可行解的比例)更低。因此這個oracle還是有一定的價值的。

參考文獻

[1] Khalil E B , Dilkina B , Nemhauser G L , et al． Learning to Run Heuristics in Tree Search[C]// Twenty-sixth International Joint Conference on Artificial Intelligence． 2017．