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ù)學最優(yōu)化問題，它由目標函數(shù)以及與目標函數(shù)中的變量相關(guān)的約束條件兩部分組成，優(yōu)化過程則為在約束條件下最優(yōu)化（最大化或最小化）目標函數(shù)。
太抽象？我們舉個例子：
給定一組物品，每種物品都有自己的重量和價格，在限定總重量的情況下，我們?nèi)绾芜x擇才能使得物品的總價格最高？這就是經(jīng)典的背包問題。從約束優(yōu)化角度來看，目標函數(shù)就是選擇物品使得總價值最高；約束是不能超過“限定的總重量”，此外，還有一個隱含約束：每個物品都是一個整體，不能切分。
在云場景下，我們同樣面臨著很多復(fù)雜的、大規(guī)模、多目標的NP難優(yōu)化問題，如機型規(guī)劃、彈性保障、資源/任務(wù)調(diào)度、資源整理、容量管理等，這些問題也可以建模為一個或多個約束優(yōu)化問題的組合。背包問題和云上的虛擬機放置問題是同源問題，只是虛擬機放置問題的約束和目標會復(fù)雜得多。
求解這些約束優(yōu)化問題有什么價值？
隨著公有云規(guī)模越來越大，優(yōu)化所能帶來的價值也越來越高。單個云數(shù)據(jù)中心的物理主機規(guī)?？梢赃_到百萬數(shù)量級，云服務(wù)器規(guī)?？蛇_數(shù)百萬到千萬臺數(shù)量級。如果能夠提升1%的資源分配率，這些資源就可以在高峰期為用戶提供更強的彈性能力，為客戶創(chuàng)造價值。
提升資源分配率僅僅是云場景優(yōu)化問題中的冰山一角。這是一個龐大的系統(tǒng)層面的問題，其中包含了多種復(fù)雜的NP難約束優(yōu)化問題。這些問題不僅出現(xiàn)在資源調(diào)度的層面，而是貫穿云資源的整個生命周期。
云上遇到的約束優(yōu)化問題有多難？
云上面臨的約束優(yōu)化問題通常有規(guī)模大、約束復(fù)雜、多目標、NP-困難等特點。
隨著問題規(guī)模的增大，求解該問題最優(yōu)解的時間是非多項式級別（比如指數(shù)級）增長的，且是計算機無法承受的。
規(guī)模大
云上面臨的約束優(yōu)化問題往往規(guī)模非常大，決策變量可高達上億規(guī)模，并且通常是離散的組合優(yōu)化問題而不是單純的線性規(guī)劃問題。這么大規(guī)模的組合優(yōu)化問題，求解難度非常高，即使使用號稱業(yè)界速度最快的商用求解器Gurobi也是無法直接求解的。
約束多
公有云是一個復(fù)雜的系統(tǒng)，需要考慮很多復(fù)雜的實際約束。以資源調(diào)度場景為例，需要考慮的約束可能包括：NUMA結(jié)構(gòu)問題，租戶的親和性與反親和性、負載的親和性與反親和性、離線任務(wù)與在線任務(wù)的親和性與反親和性，生命周期的親和性、機柜功率約束、故障域約束、網(wǎng)絡(luò)QoS約束、散熱約束、節(jié)省電力、SLA約束等等。如此多的約束會大大增加求解難度。
動態(tài)性
相較于企業(yè)私有云，公有云的客戶對資源彈性訴求更高，公有云運營商需要面對突發(fā)流量峰谷時急速擴容，彈性調(diào)度資源。然而急速彈性會為資源的調(diào)度與經(jīng)營帶來高動態(tài)性，這意味著求解的狀態(tài)變化很快，對算法求解時間的要求也更為苛刻，求解時間過長則結(jié)果無意義。同時，這種動態(tài)性及隨機性，使得算法在對解的優(yōu)度進行評估時，還需避免當前的優(yōu)化目標對未來的決策產(chǎn)生負面影響。
此外，隨著公有云發(fā)展，新增了分布式、邊緣節(jié)點自治、突發(fā)型實例等特性，這些都讓問題的難度指數(shù)級增加。
我們的解決方案：面向云場景的約束規(guī)劃問題優(yōu)化求解引擎
為了解決云上遇到的此類復(fù)雜的約束優(yōu)化問題，尤其是資源規(guī)劃與調(diào)度相關(guān)問題，華為云擎天架構(gòu)調(diào)度與算法團隊設(shè)計了面向云場景的約束規(guī)劃問題優(yōu)化求解引擎。
面向云場景的約束規(guī)劃問題優(yōu)化求解引擎的核心是基于元啟發(fā)式搜索算法框架的，那么為什么我們選擇元啟發(fā)式搜索呢？
在計算復(fù)雜性和最優(yōu)化領(lǐng)域，有個“沒有免費的午餐（NFL，No Free Lunch）”理論，即對于優(yōu)化問題，在有限的搜索空間中，當且僅當我們指定了具體的問題的時候，我們才能說一個優(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ù)雜約束的問題，求解時長與資源消耗都是計算機無法接受的，因此并不適合在云場景下使用。
啟發(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)鍵機制，就是搜索集中性（ intensification）的機制和搜索的疏散性（diversification）的機制。前者負責搜索當前解的周圍區(qū)域，而后者負責逃出局部優(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)化。
當然并不是我們只要使用了元啟發(fā)式框架整個引擎和算法就萬事大吉了，求解框架只是第一步。復(fù)雜問題的建模、求解的算法集、策略集、參數(shù)調(diào)教都是我們的重點工作。尤其建模更是重中之重，它關(guān)系到問題的復(fù)雜度以及解是不是可以被應(yīng)用到實際的生產(chǎn)環(huán)境當中去。我們還嘗試引入多種元啟發(fā)式算法框架，引入和設(shè)計多種集中性和疏散性策略包括文獻中最好的方法以及團隊創(chuàng)新的方法，并嘗試創(chuàng)新的組合以及參數(shù)優(yōu)化，包括引導式局部搜索、種群管理甚至是基于機器學習的手段，來豐富我們的策略，使得求解引擎能夠?qū)υ粕弦幌盗械膯栴}生效。比如，新的引導式局部搜索和種群管理策略就是我們刷新本次PDPTW記錄的兩項關(guān)鍵技術(shù)。此外，我們采用了并行化、參數(shù)自適應(yīng)等多種技術(shù)來進一步改善我們求解引擎的性能表現(xiàn)和適應(yīng)能力。
至此，我們?nèi)〉昧艘恍﹥?yōu)秀成果，包括此前獲得GECCO2020 OCP&USCP競賽冠軍，以及此次刷新51項PDPTW問題榜單。更為重要的是，面向云場景的約束規(guī)劃問題優(yōu)化求解引擎作為華為云擎天架構(gòu)的一部分，為華為云的資源規(guī)劃、資源經(jīng)營保障、資源彈性能力等方面提供了強大的優(yōu)化算法支持，最終客戶也會從彈性能力保障、服務(wù)質(zhì)量等方面獲益。在探索云上最優(yōu)化問題的道路上，我們并非閉門造車，華為云聯(lián)合ICPC組委會將在12月12日-12月20日在線舉辦ICPC 2020 NERC華為挑戰(zhàn)賽，以云上調(diào)度挑戰(zhàn)問題為題，邀請全球算法精英一同探索云上最優(yōu)解之道。
目前基于華為云擎天架構(gòu)加持的競享實例正在熱銷中，針對任務(wù)型、可容錯的算力密集型場景，提供超高性價比算力，在保證使用時長的情況下還可節(jié)省85%的使用成本。同時，華為云“雙12會員節(jié)”，還有更多高性能、高性價實例正在熱促，全場低至1.5折！更有企業(yè)客戶專享權(quán)益、新購滿額送P40 Pro活動，多款產(chǎn)品優(yōu)惠，助你上云一步到位！閱讀原文，了解詳情。
(閱讀原文跳轉(zhuǎn)連接：https://activity.huaweicloud.com/1212_promotion/index.html?utm_source=InfoQ&utm_medium=banner&utm_campaign=&utm_content=&utm_term=&utm_adplace=AdPlace036568)
參考
https://ieeexplore.ieee.org/document/585893
https://codeforces.com/nerc2020
https://bbs.huaweicloud.com/blogs/175251
