近日，華為云企業(yè)智能(EI)創(chuàng)新孵化實驗室OROAS與華為諾亞決策推理實驗室聯(lián)合團(tuán)隊(以下簡稱“華為聯(lián)合團(tuán)隊”)參加了由人工智能頂級學(xué)術(shù)會議NeurIPS 2021承辦的Machine Learning for Combinatorial Optimization(ML4CO)競賽，并斬獲求解器超參優(yōu)化賽道冠軍，成績大幅度領(lǐng)先于第二名。

　　該競賽聚焦特定問題與歷史數(shù)據(jù)信息，與參賽者共同探討如何通過機(jī)器學(xué)習(xí)方法來提升求解器的性能。在華為供應(yīng)鏈算法工作組的支持下，華為聯(lián)合團(tuán)隊針對“增強(qiáng)通用求解器在特定混合整數(shù)規(guī)劃(MIP)問題上的求解性能”，提出了離線參數(shù)整定、在線參數(shù)推薦兩大解決方案，在三類問題上均實現(xiàn)了最佳性能。華為聯(lián)合團(tuán)隊在本次賽事中沉淀的技術(shù)將對幫助行業(yè)客戶高效計算最優(yōu)方案、提升資源利用率和運轉(zhuǎn)效率、突破業(yè)界運籌優(yōu)化極限有重要意義。

NeurIPS 2021(ML4CO)競賽榜單

　　混合整數(shù)規(guī)劃(Mixed Integer Programming, MIP)問題(如資源調(diào)度、生產(chǎn)排產(chǎn)、路徑優(yōu)化、運營管理、研發(fā)設(shè)計、財經(jīng)管理等)是企業(yè)運籌優(yōu)化時面臨的最常見的問題類型，覆蓋商業(yè)決策優(yōu)化的大部分流程，在求解器應(yīng)用場景中的占比超75%?；旌险麛?shù)規(guī)劃求解器(MIP Solver)是數(shù)學(xué)規(guī)劃(mathematical programming)算法的集大成者，內(nèi)嵌原/對偶單純形、內(nèi)點法等線性規(guī)劃(LP)算法、分支定界算法、各類割平面算法、各類原啟發(fā)算法、各類預(yù)處理算法、各類域傳播算法等。這些算法在MIP求解器內(nèi)的實現(xiàn)涉及到大量超參數(shù)，如開源MIP求解器中性能最為強(qiáng)勁的SCIP求解器提供了2617個超參數(shù)，其中超過2000個超參數(shù)與求解過程中的決策強(qiáng)相關(guān)。

　　通常，這些超參數(shù)由求解器開發(fā)者依據(jù)人工經(jīng)驗整定，面向通用問題提供一套適用性最為廣泛的參數(shù)作為默認(rèn)值。但面向細(xì)分行業(yè)特定場景，首先，默認(rèn)參數(shù)難以發(fā)揮求解器的最佳性能。第二，求解器使用門檻相對較高，要求用戶對組合優(yōu)化、數(shù)學(xué)規(guī)劃算法和場景問題本身有較為深入的理解。第三，即使是行業(yè)領(lǐng)域的專家，在求解器的海量參數(shù)組合中為特定場景問題選擇最佳參數(shù)的過程中，也存在著人工調(diào)參耗時耗力的挑戰(zhàn)。

　　NeurIPS 2021(ML4CO)競賽的超參優(yōu)化賽道直面上述痛點，號召全球研究者探索機(jī)器學(xué)習(xí)在求解器參數(shù)整定、參數(shù)推薦中的應(yīng)用，以“多維背包問題、流量均衡問題、面向?qū)嶋H問題且包含多種類型問題的匿名問題集”為研究對象，征集SCIP求解器的最佳參數(shù)推薦方案，從而幫助提升通用求解器在細(xì)分行業(yè)特定場景問題上的性能。

　　華為聯(lián)合團(tuán)隊認(rèn)為該任務(wù)可被解耦為“離線參數(shù)整定”與“在線參數(shù)推薦”兩個步驟。“離線參數(shù)整定”步驟是針對每一類同質(zhì)問題整定出一套最佳性能的參數(shù)，即調(diào)參;“在線參數(shù)推薦”步驟是訓(xùn)練一個機(jī)器學(xué)習(xí)模型來完成從問題用例特征到問題用例類別的映射關(guān)系學(xué)習(xí)，即匹配。兩個步驟的關(guān)系如下圖所示：

　　華為聯(lián)合團(tuán)隊在NeurIPS 2021(ML4CO)競賽中提出兩大解決方案

　　應(yīng)用“離線參數(shù)整定”技術(shù)，實現(xiàn)綜合BO調(diào)參

　　求解器調(diào)參是一類“單次性能評估的時間、資源代價昂貴”的黑箱優(yōu)化問題。針對這一類問題的常用技術(shù)方案是貝葉斯優(yōu)化(Bayesian Optimization，BO)，但將該技術(shù)直接落地應(yīng)用于求解器調(diào)參面臨以下三方面的挑戰(zhàn)：

　　l 參數(shù)空間規(guī)模大。參數(shù)空間的規(guī)模與參數(shù)維數(shù)構(gòu)成指數(shù)關(guān)系，即存在維數(shù)災(zāi)問題。常規(guī)的BO方法通常適用于參數(shù)維數(shù)在30維以內(nèi)的問題，如神經(jīng)網(wǎng)絡(luò)調(diào)參。面對2000多維的求解器參數(shù)空間，百余次BO采樣如在浩渺宇宙中探索地球，難以建立起有效的代理模型。

　　l 參數(shù)依賴關(guān)系強(qiáng)。常規(guī)的調(diào)參問題中，各維度上的參數(shù)相互獨立，構(gòu)成正交的參數(shù)空間;而求解器參數(shù)構(gòu)成樹狀空間，子級參數(shù)的作用依賴于父級參數(shù)的狀態(tài)，如原啟發(fā)的優(yōu)先級參數(shù)依賴于其開關(guān)參數(shù)。若忽視這種層級關(guān)系則會產(chǎn)生大量無效采樣，甚至引入觀測噪聲。

　　l 參數(shù)性能分布正偏。求解器在不同參數(shù)上的性能分布呈現(xiàn)出正偏趨勢，即好參數(shù)帶來的性能提升幅度遠(yuǎn)小于壞參數(shù)帶來的性能惡化幅度，進(jìn)而在隨機(jī)種子引起的觀測噪聲上表現(xiàn)出較顯著的異方差特性，不符合高斯過程代理模型的前提假設(shè)，最終影響了代理模型的擬合效果。

　　針對上述挑戰(zhàn)，華為聯(lián)合團(tuán)隊整合了在華為供應(yīng)鏈供需雙向模擬和多工廠排產(chǎn)引擎等實際場景積累的多項關(guān)鍵技術(shù)，形成了一套面向求解器參數(shù)整定場景的綜合BO調(diào)參解決方案。

　　首先，依據(jù)團(tuán)隊內(nèi)華為云天籌(OptVerse)AI求解器開發(fā)者的專家經(jīng)驗，并結(jié)合XGBoost擬合隨機(jī)觀測的參數(shù)-性能對的代理模型所得到的Gini系數(shù)信息，完成海量參數(shù)的預(yù)篩選，實現(xiàn)關(guān)鍵參數(shù)辨識目的。

　　然后，從參數(shù)類型、參數(shù)作用、依賴關(guān)系等多個維度對這些關(guān)鍵參數(shù)進(jìn)行分層組合，將高維正交的參數(shù)空間轉(zhuǎn)換為若干低維樹狀參數(shù)空間的嵌入。在每個參數(shù)子空間的BO搜索中，首先對已觀測樣本應(yīng)用Box-Cox Transform實現(xiàn)自適應(yīng)分布變換，解決偏態(tài)分布中潛在的異方差問題;在擬合代理模型環(huán)節(jié)，基于集成學(xué)習(xí)思想，使用高斯過程、隨機(jī)森林等方法，實現(xiàn)廣泛參數(shù)類型下的精準(zhǔn)擬合;在采集函數(shù)優(yōu)化環(huán)節(jié)，打破常規(guī)BO實現(xiàn)中單一采集函數(shù)的限制，集成UCB、PI、EI等多種采集函數(shù)進(jìn)行多目標(biāo)優(yōu)化，并從Pareto前沿中采樣推薦參數(shù)，實現(xiàn)期望與方差的更優(yōu)平衡。

　　基于“在線參數(shù)推薦”，完成從特征到類別的映射關(guān)系學(xué)習(xí)

　　對已知樣本的精確類別劃分與匹配是為未知樣本推薦正確參數(shù)的先決條件。華為聯(lián)合團(tuán)隊基于天籌AI求解器開發(fā)的技術(shù)積累，從MIP問題用例中抽取出上百個參數(shù)特征，并結(jié)合MIP問題三部圖的圖卷積特征，建立起MIP問題的精確畫像。基于這些特征，應(yīng)用無監(jiān)督學(xué)習(xí)方法對匿名數(shù)據(jù)集實現(xiàn)類別劃分，進(jìn)一步結(jié)合賽方完全公開的Item Placement和Load Balancing數(shù)據(jù)集，為訓(xùn)練問題類別匹配模型提供海量有效樣本。最后執(zhí)深度學(xué)習(xí)方法之矛，實現(xiàn)MIP問題從用例到類別再到參數(shù)的準(zhǔn)確映射。

　　根據(jù)NeurIPS 2021(ML4CO)競賽主辦方公布的榜單結(jié)果所示，SCIP求解器的默認(rèn)參數(shù)在Item Placement和Load Balancing兩個非匿名數(shù)據(jù)集上的平均性能指標(biāo)分別約為17000和25000。華為聯(lián)合團(tuán)隊推薦的參數(shù)性能指標(biāo)則分別達(dá)到了8741和7856，性能提升幅度分別達(dá)到了2倍和3倍。

　　華為云一站式AI開發(fā)平臺ModelArts為“離線參數(shù)整定”和“在線參數(shù)推薦”技術(shù)方案的實現(xiàn)提供了強(qiáng)有力的軟、硬件支持：ModelArts為華為聯(lián)合團(tuán)隊提供了高效、穩(wěn)定的大規(guī)模服務(wù)器集群、千余顆CPU核心與TB級內(nèi)存，保證了大量MIP用例的并行性能評估;此外，ModelArts預(yù)置的主流機(jī)器學(xué)習(xí)框架與便捷靈活的自定義鏡像環(huán)境極大地加速了上述方案的部署與落地。

　　當(dāng)前，運籌優(yōu)化技術(shù)已在華為供應(yīng)鏈多工廠排產(chǎn)引擎等多個場景落地，不僅幫助實現(xiàn)系統(tǒng)底層完全自研，而且實現(xiàn)了分工廠計劃準(zhǔn)確率、回流調(diào)撥比例、計劃自動執(zhí)行比例等一系列業(yè)務(wù)關(guān)鍵指標(biāo)的顯著提升，并大幅提高了業(yè)務(wù)的作業(yè)效率。同時，華為聯(lián)合團(tuán)隊在比賽當(dāng)中突破的前沿技術(shù)及求解能力也已集成在天籌AI求解器和ModelArts等華為云AI服務(wù)中，并計劃對外開放給更多AI開發(fā)者使用。

　　未來，華為聯(lián)合團(tuán)隊將持續(xù)優(yōu)化天籌AI求解器中的MIP求解性能，面向不同的業(yè)務(wù)場景，不斷創(chuàng)造更大價值。