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

?

問題介紹

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

?

VRP問題示意圖

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

?

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

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

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

?

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

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

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

?

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

?

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

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

規(guī)模大

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

約束多

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

動態(tài)性

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

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

?

解決方案：面向云場景的約束規(guī)劃問題優(yōu)化求解引擎

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

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

在計算復(fù)雜性和最優(yōu)化領(lǐng)域，有個“沒有免費的午餐（NFL，No Free Lunch）”理論，即對于優(yōu)化問題，在有限的搜索空間中，當(dāng)且僅當(dāng)我們指定了具體的問題的時候，我們才能說一個優(yōu)化方法要優(yōu)于另一種優(yōu)化方法?；蛘哒f，理論上，并不存在一個在所有問題上都能獲得最優(yōu)結(jié)果的算法。

常用求解NP難約束優(yōu)化問題的方法，大致可分為精確算法和啟發(fā)式算法。

精確算法，如Branch-and-cut, Branch-and-bound 等，可以在理論上保證算法朝最優(yōu)解收斂，但是通常適用于問題規(guī)模較小的情況。 對于云上這么大規(guī)模（上億決策變量）與復(fù)雜約束的問題，求解時長與資源消耗都是計算機(jī)無法接受的，因此并不適合在云場景下使用。

啟發(fā)式算法，又可以分為簡單啟發(fā)式和元啟發(fā)式。二者最大的區(qū)別就是，簡單啟發(fā)式算法更多的是問題相關(guān)的，而元啟發(fā)式算法更多的是“問題無關(guān)”的?；蛘哒f，簡單啟發(fā)式算法對于A問題有效，但是對于B問題可能完全無法使用。 但是，元啟發(fā)式是相對“通用”的搜索框架，幾乎可應(yīng)用到所有的優(yōu)化問題上面。

這么聽起來，元啟發(fā)式算法是不是違反了NFL理論，在使用一個算法解決所有問題？

并不是。元啟發(fā)式算法內(nèi)部一般包含兩種關(guān)鍵機(jī)制，就是搜索集中性（ intensification）的機(jī)制和搜索的疏散性（diversification）的機(jī)制。前者負(fù)責(zé)搜索當(dāng)前解的周圍區(qū)域，而后者負(fù)責(zé)逃出局部優(yōu)陷阱去更有“前途”的搜索區(qū)域。而一個完善的搜索策略就是要做二者的折中或者平衡，這里并沒有一個“完美策略”可以使得該策略在所有優(yōu)化問題上的性能都最好，所以也恰恰是符合NFL理論的。

在決定采用什么求解算法之前，我們再來看看云上面臨的最優(yōu)化問題的兩個特點：

云上面臨的是不止一個而是一系列的優(yōu)化問題，問題之間可能具有一定的相似性和關(guān)聯(lián)性。 比如在線資源調(diào)度、資源容量管理、資源碎片整理等，都以云資源為核心且具有相似的模型和約束。

云上的絕大多數(shù)優(yōu)化問題并不要求必須得全局最優(yōu)解，而是要求在限定的時間內(nèi)，給出盡可能高質(zhì)量的解。

結(jié)合NFL理論、元啟發(fā)式算法的特點以及云上優(yōu)化問題的特點，我們采用基于元啟發(fā)式的求解框架就順理成章了。 元啟發(fā)式算法可以在限定時間內(nèi)求解問題的“足夠好的解”，同時，使用元啟發(fā)式的問題無關(guān)性來適應(yīng)多種多樣的優(yōu)化的問題。另外，又由于云上系列問題的相似性和關(guān)聯(lián)性，針對某個問題的優(yōu)化策略很可能也會在其他相近或者關(guān)聯(lián)問題上生效，多個問題又往往可以聯(lián)合優(yōu)化。

當(dāng)然并不是我們只要使用了元啟發(fā)式框架整個引擎和算法就萬事大吉了，求解框架只是第一步。復(fù)雜問題的建模、求解的算法集、策略集、參數(shù)調(diào)教都是我們的重點工作。尤其建模更是重中之重，它關(guān)系到問題的復(fù)雜度以及解是不是可以被應(yīng)用到實際的生產(chǎn)環(huán)境當(dāng)中去。我們還嘗試引入多種元啟發(fā)式算法框架，引入和設(shè)計多種集中性和疏散性策略包括文獻(xiàn)中最好的方法以及團(tuán)隊創(chuàng)新的方法，并嘗試創(chuàng)新的組合以及參數(shù)優(yōu)化，包括引導(dǎo)式局部搜索、種群管理甚至是基于機(jī)器學(xué)習(xí)的手段，來豐富我們的策略，使得求解引擎能夠?qū)υ粕弦幌盗械膯栴}生效。比如，新的引導(dǎo)式局部搜索和種群管理策略就是我們刷新本次PDPTW記錄的兩項關(guān)鍵技術(shù)。此外，我們采用了并行化、參數(shù)自適應(yīng)等多種技術(shù)來進(jìn)一步改善我們求解引擎的性能表現(xiàn)和適應(yīng)能力。

面向云場景的約束規(guī)劃問題優(yōu)化求解引擎作為華為云擎天架構(gòu)的一部分，為華為云的資源規(guī)劃、資源經(jīng)營保障、資源彈性能力等方面提供了強(qiáng)大的優(yōu)化算法支持，最終客戶也會從彈性能力保障、服務(wù)質(zhì)量等方面獲益。