華為云擎天調(diào)度與算法團(tuán)隊(duì)近日刷新PDPTW問(wèn)題榜單中51項(xiàng)算例的世界最好記錄。該榜單自1990年起由科學(xué)工業(yè)研究院SINTEF發(fā)起并管理，該機(jī)構(gòu)被認(rèn)為是運(yùn)籌優(yōu)化領(lǐng)域中VRP問(wèn)題的全球最權(quán)威評(píng)測(cè)平臺(tái)。

問(wèn)題介紹

PDPTW問(wèn)題屬于VRP系列問(wèn)題，也是經(jīng)典的NP難問(wèn)題，已被廣泛研究超過(guò)50年。 與經(jīng)典VRP問(wèn)題相比，該問(wèn)題擴(kuò)展了更多的約束，求解難度也更高。 VRP系列問(wèn)題，簡(jiǎn)單來(lái)講，就是用來(lái)在圖網(wǎng)絡(luò)中尋找滿足一系列約束情況下的最優(yōu)路徑問(wèn)題。該系列問(wèn)題在物流配送、航路規(guī)劃、電路設(shè)計(jì)以及云計(jì)算等領(lǐng)域都有廣泛應(yīng)用。

VRP問(wèn)題示意圖

VRP系列問(wèn)題都屬于典型的NP難約束優(yōu)化問(wèn)題。 約束優(yōu)化問(wèn)題與工業(yè)場(chǎng)景優(yōu)化關(guān)系非常密切，眾多工業(yè)場(chǎng)景下的問(wèn)題都可以建模為約束優(yōu)化問(wèn)題，如網(wǎng)絡(luò)設(shè)計(jì)優(yōu)化、碼頭作業(yè)調(diào)度、芯片設(shè)計(jì)布線、人員和時(shí)刻表排班、庫(kù)存管理等。

什么是約束優(yōu)化問(wèn)題？

約束優(yōu)化問(wèn)題是一類數(shù)學(xué)最優(yōu)化問(wèn)題，它由目標(biāo)函數(shù)以及與目標(biāo)函數(shù)中的變量相關(guān)的約束條件兩部分組成，優(yōu)化過(guò)程則為在約束條件下最優(yōu)化（最大化或最小化）目標(biāo)函數(shù)。

太抽象？我們舉個(gè)例子：

給定一組物品，每種物品都有自己的重量和價(jià)格，在限定總重量的情況下，我們?nèi)绾芜x擇才能使得物品的總價(jià)格最高？這就是經(jīng)典的背包問(wèn)題。從約束優(yōu)化角度來(lái)看，目標(biāo)函數(shù)就是選擇物品使得總價(jià)值最高；約束是不能超過(guò)“限定的總重量”，此外，還有一個(gè)隱含約束：每個(gè)物品都是一個(gè)整體，不能切分。

在云場(chǎng)景下，我們同樣面臨著很多復(fù)雜的、大規(guī)模、多目標(biāo)的NP難優(yōu)化問(wèn)題，如機(jī)型規(guī)劃、彈性保障、資源/任務(wù)調(diào)度、資源整理、容量管理等，這些問(wèn)題也可以建模為一個(gè)或多個(gè)約束優(yōu)化問(wèn)題的組合。背包問(wèn)題和云上的虛擬機(jī)放置問(wèn)題是同源問(wèn)題，只是虛擬機(jī)放置問(wèn)題的約束和目標(biāo)會(huì)復(fù)雜得多。

求解這些約束優(yōu)化問(wèn)題有什么價(jià)值？

隨著公有云規(guī)模越來(lái)越大，優(yōu)化所能帶來(lái)的價(jià)值也越來(lái)越高。單個(gè)云數(shù)據(jù)中心的物理主機(jī)規(guī)模可以達(dá)到百萬(wàn)數(shù)量級(jí)，云服務(wù)器規(guī)模可達(dá)數(shù)百萬(wàn)到千萬(wàn)臺(tái)數(shù)量級(jí)。如果能夠提升1%的資源分配率，這些資源就可以在高峰期為用戶提供更強(qiáng)的彈性能力，為客戶創(chuàng)造價(jià)值。

提升資源分配率僅僅是云場(chǎng)景優(yōu)化問(wèn)題中的冰山一角。這是一個(gè)龐大的系統(tǒng)層面的問(wèn)題，其中包含了多種復(fù)雜的NP難約束優(yōu)化問(wèn)題。這些問(wèn)題不僅出現(xiàn)在資源調(diào)度的層面，而是貫穿云資源的整個(gè)生命周期。

云上遇到的約束優(yōu)化問(wèn)題有多難？

云上面臨的約束優(yōu)化問(wèn)題通常有規(guī)模大、約束復(fù)雜、多目標(biāo)、NP-困難等特點(diǎn)。

隨著問(wèn)題規(guī)模的增大，求解該問(wèn)題最優(yōu)解的時(shí)間是非多項(xiàng)式級(jí)別（比如指數(shù)級(jí)）增長(zhǎng)的，且是計(jì)算機(jī)無(wú)法承受的。

規(guī)模大

云上面臨的約束優(yōu)化問(wèn)題往往規(guī)模非常大，決策變量可高達(dá)上億規(guī)模，并且通常是離散的組合優(yōu)化問(wèn)題而不是單純的線性規(guī)劃問(wèn)題。這么大規(guī)模的組合優(yōu)化問(wèn)題，求解難度非常高，即使使用號(hào)稱業(yè)界速度最快的商用求解器Gurobi也是無(wú)法直接求解的。

約束多

公有云是一個(gè)復(fù)雜的系統(tǒng)，需要考慮很多復(fù)雜的實(shí)際約束。以資源調(diào)度場(chǎng)景為例，需要考慮的約束可能包括：NUMA結(jié)構(gòu)問(wèn)題，租戶的親和性與反親和性、負(fù)載的親和性與反親和性、離線任務(wù)與在線任務(wù)的親和性與反親和性，生命周期的親和性、機(jī)柜功率約束、故障域約束、網(wǎng)絡(luò)QoS約束、散熱約束、節(jié)省電力、SLA約束等等。如此多的約束會(huì)大大增加求解難度。

動(dòng)態(tài)性

相較于企業(yè)私有云，公有云的客戶對(duì)資源彈性訴求更高，公有云運(yùn)營(yíng)商需要面對(duì)突發(fā)流量峰谷時(shí)急速擴(kuò)容，彈性調(diào)度資源。然而急速?gòu)椥詴?huì)為資源的調(diào)度與經(jīng)營(yíng)帶來(lái)高動(dòng)態(tài)性，這意味著求解的狀態(tài)變化很快，對(duì)算法求解時(shí)間的要求也更為苛刻，求解時(shí)間過(guò)長(zhǎng)則結(jié)果無(wú)意義。同時(shí)，這種動(dòng)態(tài)性及隨機(jī)性，亞洲服務(wù)器租用，使得算法在對(duì)解的優(yōu)度進(jìn)行評(píng)估時(shí)，還需避免當(dāng)前的優(yōu)化目標(biāo)對(duì)未來(lái)的決策產(chǎn)生負(fù)面影響。

此外，隨著公有云發(fā)展，新增了分布式、邊緣節(jié)點(diǎn)自治、突發(fā)型實(shí)例等特性，這些都讓問(wèn)題的難度指數(shù)級(jí)增加。

我們的解決方案：面向云場(chǎng)景的約束規(guī)劃問(wèn)題優(yōu)化求解引擎

為了解決云上遇到的此類復(fù)雜的約束優(yōu)化問(wèn)題，尤其是資源規(guī)劃與調(diào)度相關(guān)問(wèn)題，華為云擎天架構(gòu)調(diào)度與算法團(tuán)隊(duì)設(shè)計(jì)了面向云場(chǎng)景的約束規(guī)劃問(wèn)題優(yōu)化求解引擎。

面向云場(chǎng)景的約束規(guī)劃問(wèn)題優(yōu)化求解引擎的核心是基于元啟發(fā)式搜索算法框架的，那么為什么我們選擇元啟發(fā)式搜索呢？