論文閱讀筆記,個(gè)人理解,如有錯(cuò)誤請(qǐng)指正,感激不盡!該文分類到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等)對(duì)分支樹進(jìn)行搜索,通過求解節(jié)點(diǎn)的linear relaxation(LP)獲得節(jié)點(diǎn)的下界(lower bound)。如果LP解滿足整數(shù)約束(IP),則可認(rèn)為找到了原問題的一個(gè)可行解(feasible solution),branch and bound記錄在搜索過程中找到的可行解,并維護(hù)一個(gè)最優(yōu)可行解作為全局的上界。當(dāng)節(jié)點(diǎn)的下界比上界還差時(shí),則減掉該支路。最終遍歷所有支路,獲得最優(yōu)解。

2 Primal Heuristic

通過branch and bound,branch and cut等求解MIP時(shí),通常需要花費(fèi)大量的計(jì)算時(shí)間,因?yàn)楹芏鄦栴}的LP模型獲得的lower bound非常差。在分支節(jié)點(diǎn)上運(yùn)行heuristic算法對(duì)可行解進(jìn)行搜索,可大大提高搜索的速度。比如在前期通過heuristic找到一個(gè)較好的上界,可以使得branch and bound在搜索的過程中減掉很多沒用的支路,從而加快優(yōu)化的速度。

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

何為探試?

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)

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

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

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

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

參考文獻(xiàn)

[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．