華為云擎天調(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ī)性，使得算法在對(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ā)式搜索呢？
在計(jì)算復(fù)雜性和最優(yōu)化領(lǐng)域，有個(gè)“沒(méi)有免費(fèi)的午餐（NFL，No Free Lunch）”理論，即對(duì)于優(yōu)化問(wèn)題，在有限的搜索空間中，當(dāng)且僅當(dāng)我們指定了具體的問(wèn)題的時(shí)候，我們才能說(shuō)一個(gè)優(yōu)化方法要優(yōu)于另一種優(yōu)化方法?；蛘哒f(shuō)，理論上，并不存在一個(gè)在所有問(wèn)題上都能獲得最優(yōu)結(jié)果的算法。
常用求解NP難約束優(yōu)化問(wèn)題的方法，大致可分為精確算法和啟發(fā)式算法。
精確算法，如Branch-and-cut,Branch-and-bound等，可以在理論上保證算法朝最優(yōu)解收斂，但是通常適用于問(wèn)題規(guī)模較小的情況。對(duì)于云上這么大規(guī)模（上億決策變量）與復(fù)雜約束的問(wèn)題，求解時(shí)長(zhǎng)與資源消耗都是計(jì)算機(jī)無(wú)法接受的，因此并不適合在云場(chǎng)景下使用。
啟發(fā)式算法，又可以分為簡(jiǎn)單啟發(fā)式和元啟發(fā)式。二者最大的區(qū)別就是，簡(jiǎn)單啟發(fā)式算法更多的是問(wèn)題相關(guān)的，而元啟發(fā)式算法更多的是“問(wèn)題無(wú)關(guān)”的。或者說(shuō)，簡(jiǎn)單啟發(fā)式算法對(duì)于A問(wèn)題有效，但是對(duì)于B問(wèn)題可能完全無(wú)法使用。但是，元啟發(fā)式是相對(duì)“通用”的搜索框架，幾乎可應(yīng)用到所有的優(yōu)化問(wèn)題上面。
這么聽起來(lái)，元啟發(fā)式算法是不是違反了NFL理論，在使用一個(gè)算法解決所有問(wèn)題？
并不是。元啟發(fā)式算法內(nèi)部一般包含兩種關(guān)鍵機(jī)制，就是搜索集中性（intensification）的機(jī)制和搜索的疏散性（diversification）的機(jī)制。前者負(fù)責(zé)搜索當(dāng)前解的周圍區(qū)域，而后者負(fù)責(zé)逃出局部?jī)?yōu)陷阱去更有“前途”的搜索區(qū)域。而一個(gè)完善的搜索策略就是要做二者的折中或者平衡，這里并沒(méi)有一個(gè)“完美策略”可以使得該策略在所有優(yōu)化問(wèn)題上的性能都最好，所以也恰恰是符合NFL理論的。
在決定采用什么求解算法之前，我們?cè)賮?lái)看看云上面臨的最優(yōu)化問(wèn)題的兩個(gè)特點(diǎn)：
云上面臨的是不止一個(gè)而是一系列的優(yōu)化問(wèn)題，問(wèn)題之間可能具有一定的相似性和關(guān)聯(lián)性。比如在線資源調(diào)度、資源容量管理、資源碎片整理等，都以云資源為核心且具有相似的模型和約束。
云上的絕大多數(shù)優(yōu)化問(wèn)題并不要求必須得全局最優(yōu)解，而是要求在限定的時(shí)間內(nèi)，給出盡可能高質(zhì)量的解。
結(jié)合NFL理論、元啟發(fā)式算法的特點(diǎn)以及云上優(yōu)化問(wèn)題的特點(diǎn)，我們采用基于元啟發(fā)式的求解框架就順理成章了。元啟發(fā)式算法可以在限定時(shí)間內(nèi)求解問(wèn)題的“足夠好的解”，同時(shí)，使用元啟發(fā)式的問(wèn)題無(wú)關(guān)性來(lái)適應(yīng)多種多樣的優(yōu)化的問(wèn)題。另外，又由于云上系列問(wèn)題的相似性和關(guān)聯(lián)性，針對(duì)某個(gè)問(wèn)題的優(yōu)化策略很可能也會(huì)在其他相近或者關(guān)聯(lián)問(wèn)題上生效，多個(gè)問(wèn)題又往往可以聯(lián)合優(yōu)化。
當(dāng)然并不是我們只要使用了元啟發(fā)式框架整個(gè)引擎和算法就萬(wàn)事大吉了，求解框架只是第一步。復(fù)雜問(wèn)題的建模、求解的算法集、策略集、參數(shù)調(diào)教都是我們的重點(diǎn)工作。尤其建模更是重中之重，它關(guān)系到問(wèn)題的復(fù)雜度以及解是不是可以被應(yīng)用到實(shí)際的生產(chǎn)環(huán)境當(dāng)中去。我們還嘗試引入多種元啟發(fā)式算法框架，引入和設(shè)計(jì)多種集中性和疏散性策略包括文獻(xiàn)中最好的方法以及團(tuán)隊(duì)創(chuàng)新的方法，并嘗試創(chuàng)新的組合以及參數(shù)優(yōu)化，包括引導(dǎo)式局部搜索、種群管理甚至是基于機(jī)器學(xué)習(xí)的手段，來(lái)豐富我們的策略，使得求解引擎能夠?qū)υ粕弦幌盗械膯?wèn)題生效。比如，新的引導(dǎo)式局部搜索和種群管理策略就是我們刷新本次PDPTW記錄的兩項(xiàng)關(guān)鍵技術(shù)。此外，我們采用了并行化、參數(shù)自適應(yīng)等多種技術(shù)來(lái)進(jìn)一步改善我們求解引擎的性能表現(xiàn)和適應(yīng)能力。
至此，我們?nèi)〉昧艘恍﹥?yōu)秀成果，包括此前獲得GECCO2020 OCP&USCP競(jìng)賽冠軍，以及此次刷新51項(xiàng)PDPTW問(wèn)題榜單。更為重要的是，面向云場(chǎng)景的約束規(guī)劃問(wèn)題優(yōu)化求解引擎作為華為云擎天架構(gòu)的一部分，為華為云的資源規(guī)劃、資源經(jīng)營(yíng)保障、資源彈性能力等方面提供了強(qiáng)大的優(yōu)化算法支持，最終客戶也會(huì)從彈性能力保障、服務(wù)質(zhì)量等方面獲益。在探索云上最優(yōu)化問(wèn)題的道路上，我們并非閉門造車，華為云聯(lián)合ICPC組委會(huì)將在12月12日-12月20日在線舉辦ICPC 2020 NERC華為挑戰(zhàn)賽，以云上調(diào)度挑戰(zhàn)問(wèn)題為題，邀請(qǐng)全球算法精英一同探索云上最優(yōu)解之道。
參考
https://ieeexplore.ieee.org/document/585893
https://codeforces.com/nerc2020
https://bbs.huaweicloud.com/blogs/175251
華為云
專欄
閩公網(wǎng)安備 35010202001226號(hào)
