高季堯：定製化優化演算法的應用與威力

隨著大數據與人工智慧領域技術的發展和應用的普及，演算法越發繁多複雜，需要處理的數據量也越發龐大，高性能計算能力就顯得尤為重要。

本篇選自高季堯先生近期於清華大數據「技術·前沿」系列講座上所做的題為《定製化優化演算法的應用與威力》的主題演講。

本篇主要通過三個方面進行分享:

1. 何為運籌優化

2. 為什麼需要定製化演算法

3. 定製化演算法案例分享

作者介紹：

高季堯，本科畢業於清華大學化學工程系，博士就讀於美國康奈爾大學，並從事能源系統供應鏈的數學建模與運籌優化研究。博士期間以第一作者的身份在行業頂級期刊發表數十篇論文，並多次在國際會議上做學術報告。Google Scholar引用次數達300多次，並擔任多個國際期刊的審稿人。曾參與中國石化公司的多項生產優化項目，加入杉數後為多家標杆企業提供技術服務。

一、何為運籌優化

數學家歐拉曾提出：從古至今，「優化」一直是生產生活中的重要的部分。在二戰期間，現代運籌學曾在戰場上發揮巨大作用；直至二戰結束後，世界經濟開始復甦，運籌學也被廣泛的運用到金融、生產等領域，其分支也得到相應發展。到20世紀90年代，計算機科學高速發展，人們要解決的問題規模不斷增大，運籌學的應用範圍也取得革命性的突破。21世紀，大數據時代來臨，給運籌學帶來更大的舞台，如何將大數據轉化為現代商業生產環境下的最優決策，成為運籌學的重點課題。

優化的定義：尋找在滿足約束的條件下能夠最大化或者最小化某一目標的最優決策。

在優化過程中，建模和求解是兩個關鍵步驟。建模，將想要優化解決的問題，通過準確有效的數學模型或數學形式來表達出來。第二個是有一個很好的數學模型之後，怎樣通過高效的方法，將這個模型進行高效地求解。優化問題的數學形式往往是有這樣一個形式：一個優化目標，可以是最大化也可以是最小化，同時有一個決策變數用x表示，為了優化x可以遵循一定的約束條件，可以是不等式，也可以是等式。

舉個現實生活中的有趣案例，如果小明同學想吃火鍋，那就會出現兩種情況：

以最大化的飽腹感為目標，而條件是花費要小於預算以及對食材的選擇和衝突。

以最小化花費為目標，條件是飽腹感要超過底線以及對地點和食材的選擇。

如何建模？以不同食材的選擇為條件，引入Index函數：Index

i表示食物的集合，yi表示關於食物選擇的決策;1表示選擇食材，0表示不選食材。

這樣就有了公式：

食材： Index i ∈ I 決策： yi ∈ binary variable

還有一些其他方面的輸入：預算上限、吃飽底線、食材價格及食材帶來的飽腹感。第一個Case目標函數為si乘以yi的加和，表示選中的所有食物帶來的飽腹感的加和能夠最大化。約束條件：首先花費要小於等於預算，其次必點的菜則i固定的等於1，當菜系發生衝突，點了某一種菜，另一種菜一定不點，這就用兩個點跟i相對應。另外一個集合當選了i的時候，不選的一個集合，讓這兩個y相加等於1，就意味著最多只有一個1，最後要定義y是原因變數，只能取0或者1。

那麼第二個Case想要省錢應該如何建模呢？其他條件不變，只是把約束條件和目標函數調換一下，即現在的目標函數是最小化花費，約束條件是選取所有食材飽腹感大於底線。

優化問題可以按照變數類型和約束條件類型被分成四種類型。LP所有的變數都是連續變數，約束都是線性約束。在它的基礎上，如果能夠既涉及到了離散變數，同時也有連續變數就是MIP；基於LP，如果說有非線性的約束，就是NLP；MINLP是最複雜的一種類型，包含了另外三種情況的總和。

在高性能演算法中，大致分為兩類：嚴格優化演算法和Metaheuristic演算法。嚴格優化演算法更好進行說明，在數學上更容易證明，所以在學術界更受歡迎；而Metaheuristic演算法在應用上更有優勢。求解器相當於包裝很多演算法的「盒子」，像MILP這樣的混合整數線性優化問題，只要滿足通用形式，按照標準輸入「盒子」就可以快速求解。在上述的求解器中，GUROBI和CPLEX是最有名的求解器。這兩個求解器都跟IBM有關，IBM旗下CPLEX的創始人之一後來出走，和另外幾個人一起創建了GUROBI。目前，這兩家佔據了通用商業求解器的絕大部分市場份額。杉數也研發了自己的一個求解器，是中國首個由華人開發的數學規劃求解器及機器學習演算法套件，打破了西方在這方面的技術壟斷，具有很重要的歷史意義。

二、為何要對演算法定製化

演算法的必要性可以從其問題本身和演算法兩個方面進行分析。演算法定製化的目的，是給優化問題選擇合適的演算法，而選出合適的演算法主要從三個維度進行衡量：1.穩定性，即在不同的參數和場景下都能給出很好的解。優化效果能夠保證，不能因改變參數而使效果降低很多；同時求解時間要相對穩定。2.保證求解達到最理想化，或距離最優解偏差越小越好。但有時要將求解時間控制在一定範圍內，會犧牲求解的最優性。3.時效性，在客戶需求的範圍以內能夠求出最優解。

案例分享：

MILFP,是一種特殊的混合整數非線性的問題。其主要目標函數是兩個線性方程的比值，其他所有的約束條件都是線性的。假設分母為正，則該線性方程用大於等於符號，這個符號是相對小的數比如0.01，但不能太小，這是一個混合整數問題。該問題有非線性的目標函數，因此是一類特殊的MILFP的問題。該目標函數是一個分式形式，其特性是具有組合性質和偽凸性。其應用在工程、經濟、環境科學等環境中，例如投資回報率及購買物品時所提到的性價比。

Pseudo-convexity(偽凸性），如圖所示函數，只要梯度是正的，在這個方向上就一直增長。基於Cutting plane在圖中所標示的黑點會加一個Cut，這就切掉了一部分可行域，這樣可能無法找到全局最優解，只能找到替代的局部最優解。它是特殊的MINLP的問題，部分演算法能夠求解全局最優的點，也有一些演算法只能保證局部最優，當然還可以用通用的MINLP solvers求解，當然最理想的情況還是採用定製化的演算法。

其中提到MILFP是一類特殊的MINLP的問題，涉及到剛才提到的數學特性（組合性質和偽凸性）。

通用的求解器是基於圖示文獻中提到的演算法，有分解演算法等等。

通用性的求解是針對所有類型非線性問題，往往針對某種特定問題的時候，求解效率不會很高。定製化的演算法，前兩個演算法列出了相應的文獻。往往在解特定問題的時候，會有特別好的表現。

整個演算法框架的整理：

第一步就是初始化。開始設置一些參數和建立模型。之後就是對問題的鬆弛，松馳之後從備選節點中選取一個，然後對子問題做對應的變形。這樣每個子問題獲得的是LP問題，接下來就是分支定界法中最經典的求解步驟。

首先理解子問題，第二步判斷所獲得的解是不是最優解，如果不是就把它丟掉，如果是最優的，就要檢查是不是w等於0或者u，如果不是的話，就向分支定界法一樣，在節點中加入兩個新節點，一個是要固定出w等於0，一個w等於u。如果說，剛好解出來的w都是0或者u，就意味著符合了之前的約束，接下來要檢查目標函數是不是比之前的好。如果沒有的話，這個節點就不要了，如果好的話，就更新下界，同時把節點去掉，同時把之前求解中節點集合中所有的上界比下界還低的界點去掉，這樣的迭代一直循環到節點集合中，所有的節點都被遍歷過後，所得到的最優解便是全局最優解。

該演算法的優點是每一個節點的子問題都被轉化成LP，而且尺度明顯增大，這意味著每個子問題可以非常快的求解；而缺點就是基於分支定界法，求解效率高度依賴分支迭代次數。

給定了一個MLP的標準形式，對不同大小的算力進行測試，I是連續變數的範圍，最小的測試案例只有60個，最大的有3000個。整數變數最小的有15個，最大的有50個。

橫軸是給定的計算時間，如果某條曲線是更靠近左上方的，可以理解為在相應的時間內，解決問題更多，就是更高效。

整體看下來，前兩種定製化的演算法表現是最好的。整體處在左上方，只能求到局部最優的SBB和DICOPT（求解器）。在10秒以內的計算時間內這兩種演算法和定製化演算法差距不是很大，但是當給定的求解時間更長時，這兩種求解器其實並沒有解決更多的問題，折線相對平緩一些，意味著在解決小問題的時候更高效，在解決大問題的時候時間是猛增的。

最後，在給定100秒，第三種定製化演算法比不過另外4種演算法，但它的好處是能夠保證全局最優。當給出的固定時間在100秒的時候，求解出來的問題數量已經和SBB打平手，給定1000秒的時候，其實已經能夠和前兩種定製化演算法基本一樣，甚至趕超了。而且，可以看到當在10000秒最大計算時間的時候，只有前三種定製化演算法完成了所有50個問題的求解。但其他商用的求解器沒有實現完成50個的全部求解。通用的MINLP求解器最終只解決了36到37個問題，他們最通用，任何MINLP問題都可以求解，但計算效率的差距非常大。

案例收穫：

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！