一文教你基于學(xué)習(xí)的方法決定在哪些分支節(jié)點(diǎn)上運(yùn)行heuristic算法
論文閱讀筆記,個(gè)人理解,如有錯(cuò)誤請(qǐng)指正,感激不盡!該文分類(lèi)到Machine learning alongside optimization algorithms。
1 混合整數(shù)規(guī)劃求解
混合整數(shù)規(guī)劃問(wèn)題(MIP)目前比較有效的算法就是branch and bound,branch and cut等。很多商業(yè)的或者非商業(yè)的MIP solver用的都是這些框架。branch and bound構(gòu)建MIP的搜索數(shù),通過(guò)搜索策略(DFS、BFS等)對(duì)分支樹(shù)進(jìn)行搜索,通過(guò)求解節(jié)點(diǎn)的linear relaxation(LP)獲得節(jié)點(diǎn)的下界(lower bound)。如果LP解滿(mǎn)足整數(shù)約束(IP),則可認(rèn)為找到了原問(wèn)題的一個(gè)可行解(feasible solution),branch and bound記錄在搜索過(guò)程中找到的可行解,并維護(hù)一個(gè)最優(yōu)可行解作為全局的上界。當(dāng)節(jié)點(diǎn)的下界比上界還差時(shí),則減掉該支路。最終遍歷所有支路,獲得最優(yōu)解。
2 Primal Heuristic
通過(guò)branch and bound,branch and cut等求解MIP時(shí),通常需要花費(fèi)大量的計(jì)算時(shí)間,因?yàn)楹芏鄦?wèn)題的LP模型獲得的lower bound非常差。在分支節(jié)點(diǎn)上運(yùn)行heuristic算法對(duì)可行解進(jìn)行搜索,可大大提高搜索的速度。比如在前期通過(guò)heuristic找到一個(gè)較好的上界,可以使得branch and bound在搜索的過(guò)程中減掉很多沒(méi)用的支路,從而加快優(yōu)化的速度。
在現(xiàn)在常用的MIP solver中已經(jīng)集成了很多成熟的heuristic算法,例如在IBM 的CPLEX中對(duì)heuristic有這樣一段說(shuō)明:
何為探試?
定義探試,并描述 CPLEX 在 MIP 優(yōu)化中應(yīng)用探試的條件。
在 CPLEX 中,探試是一個(gè)過(guò)程,用于嘗試快速生成良好或近似的問(wèn)題解,但缺少理論保證。在求解 MIP 的上下文中,探試是可以生成一個(gè)或多個(gè)解的方法,它可滿(mǎn)足所有約束和所有整數(shù)性條件,但沒(méi)有關(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 提供了探試系列,用于在分支裁剪過(guò)程中尋找節(jié)點(diǎn)(包括根節(jié)點(diǎn))處的整數(shù)解。下列主題對(duì)這些探試系列進(jìn)行闡述。
其中一個(gè)比較關(guān)鍵的問(wèn)題就是:在分支樹(shù)的哪些節(jié)點(diǎn)運(yùn)行heuristic有可能獲得更好的結(jié)果?這樣就引出了這篇文章的motivation:通過(guò)對(duì)模型的訓(xùn)練,將機(jī)器學(xué)習(xí)的模型集成到MIP的求解過(guò)程中,在分支節(jié)點(diǎn)中模型決定是否運(yùn)行heuristic。模型必須是online的,即訓(xùn)練好以后,在進(jìn)行預(yù)測(cè)時(shí)只知道當(dāng)前節(jié)點(diǎn)以及分支樹(shù)的信息,整顆分支樹(shù)或者剩下節(jié)點(diǎn)的信息。
在這篇文章中,作者給這個(gè)模型取了一個(gè)很有深意的名字,叫oracle,中文翻譯過(guò)來(lái)叫“神諭”,簡(jiǎn)直是綿羊放山羊屁--既洋氣又騷氣……
3 數(shù)據(jù)特征
機(jī)器學(xué)習(xí)是通過(guò)輸入的數(shù)據(jù)來(lái)給出預(yù)測(cè)的結(jié)果,而應(yīng)當(dāng)輸入數(shù)據(jù)的特征應(yīng)當(dāng)良好地反映問(wèn)題當(dāng)前的狀態(tài),這樣才能給出準(zhǔn)確的結(jié)果。這篇論文中使用了49個(gè)數(shù)據(jù)特征:
Global features通過(guò)一些"gap"描述了當(dāng)前搜索的狀態(tài);Node LP features使用了節(jié)點(diǎn)N的LP解來(lái)指示一些節(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è)用于搜索過(guò)程中的啟發(fā)式算法,那么關(guān)于的數(shù)據(jù)集可以從每一個(gè)算例上獲取,最終的訓(xùn)練集為。
作者在每個(gè)分支節(jié)點(diǎn)上運(yùn)行,然后收集0-1分類(lèi)標(biāo)簽值,以及數(shù)據(jù)特征向量。如果在節(jié)點(diǎn)找到了一個(gè)可行解,否則為0。但是如果在節(jié)點(diǎn)找到了一個(gè)更好的可行解,那么有可能會(huì)影響到在之后的節(jié)點(diǎn)的值。這樣收集的數(shù)據(jù)是有問(wèn)題的。
因此作者采取的數(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在求解過(guò)程中會(huì)調(diào)用多種heuristic)。
5 實(shí)驗(yàn)
作者修改了開(kāi)源的SCIP規(guī)劃求解器,并使用CPLEX作為SCIP的LP solver。機(jī)器學(xué)習(xí)采用框架scikit-learn,使用logistic regression (LR)來(lái)學(xué)習(xí)一個(gè)二進(jìn)制的分類(lèi)模型。
作者選取了SCIP中10個(gè)Heuristic算法進(jìn)行訓(xùn)練,每個(gè)算法訓(xùn)練了一個(gè)模型,運(yùn)行時(shí)10個(gè)模型都加載進(jìn)去,策略是Run-When-Successful,即oracle說(shuō)能成功的時(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)判搜索過(guò)程中算法好壞的,粗略的介紹如下圖,總之就是該指標(biāo)越小越好:
可以看到,相比默認(rèn)設(shè)置,作者提出的結(jié)合oracle在各項(xiàng)指標(biāo)上均取得不錯(cuò)的效果。其實(shí)從訓(xùn)練的結(jié)果來(lái)看,準(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.
發(fā)表評(píng)論
請(qǐng)輸入評(píng)論內(nèi)容...
請(qǐng)輸入評(píng)論/評(píng)論長(zhǎng)度6~500個(gè)字
最新活動(dòng)更多
-
10月31日立即下載>> 【限時(shí)免費(fèi)下載】TE暖通空調(diào)系統(tǒng)高效可靠的組件解決方案
-
即日-11.13立即報(bào)名>>> 【在線會(huì)議】多物理場(chǎng)仿真助跑新能源汽車(chē)
-
11月28日立即報(bào)名>>> 2024工程師系列—工業(yè)電子技術(shù)在線會(huì)議
-
12月19日立即報(bào)名>> 【線下會(huì)議】OFweek 2024(第九屆)物聯(lián)網(wǎng)產(chǎn)業(yè)大會(huì)
-
即日-12.26火熱報(bào)名中>> OFweek2024中國(guó)智造CIO在線峰會(huì)
-
即日-2025.8.1立即下載>> 《2024智能制造產(chǎn)業(yè)高端化、智能化、綠色化發(fā)展藍(lán)皮書(shū)》
推薦專(zhuān)題
- 1 【一周車(chē)話】沒(méi)有方向盤(pán)和踏板的車(chē),你敢坐嗎?
- 2 特斯拉發(fā)布無(wú)人駕駛車(chē),還未迎來(lái)“Chatgpt時(shí)刻”
- 3 特斯拉股價(jià)大跌15%:Robotaxi離落地還差一個(gè)蘿卜快跑
- 4 馬斯克給的“驚喜”夠嗎?
- 5 大模型“新星”開(kāi)啟變現(xiàn)競(jìng)速
- 6 海信給AI電視打樣,12大AI智能體全面升級(jí)大屏體驗(yàn)
- 7 打完“價(jià)格戰(zhàn)”,大模型還要比什么?
- 8 馬斯克致敬“國(guó)產(chǎn)蘿卜”?
- 9 神經(jīng)網(wǎng)絡(luò),誰(shuí)是盈利最強(qiáng)企業(yè)?
- 10 比蘋(píng)果偉大100倍!真正改寫(xiě)人類(lèi)歷史的智能產(chǎn)品降臨
- 高級(jí)軟件工程師 廣東省/深圳市
- 自動(dòng)化高級(jí)工程師 廣東省/深圳市
- 光器件研發(fā)工程師 福建省/福州市
- 銷(xiāo)售總監(jiān)(光器件) 北京市/海淀區(qū)
- 激光器高級(jí)銷(xiāo)售經(jīng)理 上海市/虹口區(qū)
- 光器件物理工程師 北京市/海淀區(qū)
- 激光研發(fā)工程師 北京市/昌平區(qū)
- 技術(shù)專(zhuān)家 廣東省/江門(mén)市
- 封裝工程師 北京市/海淀區(qū)
- 結(jié)構(gòu)工程師 廣東省/深圳市