混合整數規劃/離散優化的精確演算法-分支定界法及優化求解器

本文首發於知乎專欄「運籌OR帷幄」（http://t.cn/RlNoO3P），AI 研習社獲得授權轉載。想了解更多運籌學、人工智慧中優化理論等相關乾貨、知乎 Live 及行業動態，請關注「運籌OR帷幄」知乎專欄及同名微信公眾號（ID：ORycww）。

作者簡介： @留德華叫獸 系美國克萊姆森大學運籌學碩士，Ph.D. Candidate，後跳槽至歐盟瑪麗居里博士項目，期間前往義大利IBM Cplex實習半年，現任德國海德堡大學交叉學科計算中心、組合優化實驗室助理研究員，主攻圖像處理。

前言

運籌學在國內，遠沒有新興的人工智慧以及傳統學科統計來的普及。人工智慧、統計最後幾乎都能化簡成求解一個能量/損失函數的優化問題。但相信很多人不知道，運籌學正是研究優化理論的學科。因此，我把運籌學稱為人工智慧、大數據的「引擎」，正本清源其在人工智慧中重要性。

本文提綱：

整數規劃回顧

演算法複雜度

精確解--分支定界法

分支定界法的「收斂」

啟發式/近似演算法

運籌學的「引擎」--優化求解器 7，整數規劃模型的意義

1、整數規劃（Integer Programming）問題回顧

整數規劃，或者離散優化（Discrete Optimization），是指數學規劃（Math Programming）問題中自變數存在整數的一類問題。上面這個數學規劃問題，便是一個混合整數線性規劃問題。首先目標方程和約束方程都是線性的，其次自變數既有連續變數（x1、x3），又有整數變數（x2）。

與線性規劃連續的可行域（可行解組成的集合）不同，整數規劃的可行域是離散的。

如上圖，一條藍線代表一個線性不等式，但是這裡x,y自變數被約束成整數變數，因此可行域變成了紅線區域內的9個離散的黑點。（線性規劃的可行域是藍色線段內部所有的區域）

凸包（Convex Hull）:整數規劃所有可行解的凸包圍，即圖中紅線組成的多面體（想像多維的情況）。凸包是未知的，已知的是藍線的不等式，並且凸包是非常難求解的，或者形成凸包需要指數數量級的線性不等式（圖中紅線）。如果知道了凸包的所有線性表示，那麼整數規劃問題就可以等價為求解一個凸包表示的線性規劃問題。

另外，除了整數規劃，還有混合整數規劃（Mixed Integer Programming, MIP），即自變數既包含整數也有連續變數。如下圖：

這裡是簡單的二維情況，自變數x是連續的，y被約束成整數變數（0,1,..,n），這時候可行域變成了4條離散的橘黃色線段加上4處的黃色整數點（0,4）。（課後作業，求這個問題的凸包。）

整數規劃由於可行域是極度非凸（Highly Nonconvex）的，因此也可以看作是一類特殊的非凸優化（Nonconvex Optimization）問題。

2.演算法複雜度（Algorithm complexity）

一般情況下，求解整數規劃的精確解（全局最優）是NP難的，簡單地說，也就是只存在指數級演算法複雜度（Exponential Time Solvable）。

怎麼來理解指數級複雜度呢？假設這裡的整數變數是變數，那麼我們可以簡單地理解為演算法複雜度至少是O(2^n)（需要解2^n個線性規劃問題，其中n是整數變數的個數）。其中線性規劃被認為是可以較為高效求解的，其複雜度是多項式時間的（O(n^k)，其中k是常數，注意這裡n在底數上）。

也就是說，每增加一個整數變數，求解其精確解的運算速度最壞情況下就要增加一倍！例如求解n=100的整數規劃問題需要1小時，那麼求解n=101的規模可能會需要2小時，n=102需要4小時，n=105需要32小時。。這就是指數爆炸！

因此，整數規劃問題被看作數學規劃里、乃至世界上最難的問題之一，被很多其他領域（例如機器學習）認為是不可追蹤（Intractable）的問題--也就是他們直接放棄治療了，從不考慮直接求解該問題的精確解，而是退而求其次求解近似解或局部最優解。

3.精確演算法--分支定界法(Branch and Bound Algorithm, B&B)

整數規劃的精確演算法框架中最核心的便是B&B，以及增加分支定界效率的各種技巧，例如割平面方法（Cutting Planes Method）等。假設是求解目標函數最小化的問題，它的核心思想便是把這個NP難的問題分解成求解一個個的線性規劃（LP）問題（每個LP問題是多項式時間可解），並且在求解的過程中實時追蹤原問題的上界（最優可行解）和下界（最優線性鬆弛解）。我們先看個簡單的例子以便理解。

min x1+ 3 x2- x3+ 2 x4 - x5

s.t. x1+ x2 - x5 >= 5

x1- x3 +x4 >=1

x1..x4 is , x5 >=0

這裡假設有4個變數，x1..x4，以及1個連續變數x5。圖中最頂上的點叫Root Node，通過把整數變數x1..x4線性鬆弛(Linear Relaxation)，例如這裡鬆弛成[0,1]區間內的連續變數，然後求解相應的鬆弛後的線性規劃問題(Linear Relaxation Problem)。求解該LRP問題所得的解（通常對於原問題來說是不可行的，因為x1..x4可能是小數），這個解便是該問題的第一個下界（Lower Bound）。

為什麼是下界呢？對於一個最小化問題，因為通過把變數鬆弛成[0,1]，等於增加了可行解的個數（可行域的範圍），這樣該最小化問題就有可能得到比原問題更好（小）的解，因此鬆弛後的問題求得的解是原問題的下界（Lower Bound）。

事實上，圖中每一個點，都是一個鬆弛後的線性規劃（LRP）問題的解。由於被鬆弛成了[0,1]間的連續變數，因此原問題中應屬於的自變數，例如x1，通過求解線性規劃，得到的解可能是0.4，顯然不滿足原問題的條件。這時候，我們就需要做分支（Branch）,例如對Root Node做左右倆個分支，左邊的分支可以是x1=0，右邊的分支是x1=1。分支的意思，可以理解為在原本Root Node的LRP基礎上，加上一個x=0或1的約束條件。這樣，通過加上這個約束條件，再解該問題，x1就必定等於0或1，x1也便是可行的。當然剩餘的自變數x2..x4，由於沒有類似的整數約束，還有可能是小數，因此我們還需要更多的分支。

上圖4個變數，最壞的情況需要2^4次分支，也就是求解16個線性規劃問題。那麼圖中紅色的部分是什麼意思呢？

這就需要先引進上界（Upper Bound、最優可行解）的概念。當分支一個個進行下去時，到某一個Node（點），鬆弛後線性規劃問題求得的解可能是原問題的可行解，也就是說，x1..x4都是。這個時候，我們便找到了一個原問題的可行解，它的目標函數例如4，我們把它放入Upper Bound里。

在接下來的分支里，如果求解一個Node的LRP的解是大於上界4的，例如4.5。那麼這個時候，雖然我們還沒找到這個點其下分支可能的可行解，但是如果繼續對這個點進行分支，由於分支代表增加更多的約束，減少了可行解的個數，以後求得的解只會比4.5來得更差（大）。因此，從優化的角度，我們不可能從這個點以後的分支中找到比目前上界4更優的解，因此沒有必要對4.5這個點繼續再做分支，可以直接刪（Prune）掉，也就是圖中紅色的區域。

這就是分支定界里定界的重要性，它使得你不需要求解所有2^n個LRP問題，因為很多Node及其下面的分支，都被Prune了。

Prune情況一：下界大於上界

Prune情況二：該Node的LRP問題無解（Infeasible）。

對提問區的補充：紅色部分表示這部分分支已經被丟棄掉了，因為找到的upper bound（當前最優解）的值小於lower bound（線性規劃鬆弛解），也就是說，即使紅色的部分探索下去，找到一個可行解，也不可能比當前找到的最優解要來得好（那麼為何還要浪費時間再去探索他們呢？）。

4.分支定界法的「收斂（Convergence）」

這裡的收斂不是分析意義上的收斂，而是演算法、計算意義上的。上面我們提到分支定界法存在上界和下界，並且隨著一個個Node LRP問題的求解，不斷進行著更新。每當求得一個原問題的可行解（混合整數解），如果這個解的目標函數小於當前的最優可行解，那麼就對上界進行更新。下界更新方式類似。

分支定界法是一個迭代演算法(Iteration Algorithm)，每次迭代都在求解LRP問題，收斂的準則是計算意義上的，例如可以設置當上界和下界非常接近（0.001）時，結束迭代。

然而比起絕對差值更為流行的，是相對差值，也即分支定界法的Gap。它的計算方法，（上界-下界）/上界。

通常我們設置Gap 終止（Terminate）。

5.啟發式/近似演算法（Heuristic/Approximation Algorithms）

作為研究世界上最難問題的學者，想出了解決整數規劃問題的各種其他途徑，例如近似演算法（Approximation Algorithms），啟發式演算法（Heuristic Algorithms），遺傳演算法（Generic Algorithm），Evolutionary Algorithms等等。它們雖然不能求得整數規劃的最優解，但是卻能在短時間（通常多項式時間）內給出一個較好的可行解。

啟發式演算法，通常採用貪心演算法（Greedy Algorithm），所得的解通常只是局部最優解，並且完全沒有概念這個解到底有多「好」。

近似演算法，與啟發式演算法不一樣，演算法往往通過非常巧妙的設計，計算所得的解可以用嚴格的數學證明是「比較好」的，即所謂的近似率（Approximation Ratio）,R。也就是說，近似演算法所得的解，可以被證明是全局最優解的R倍之內。這樣該演算法所得的解被認為是有保證的。

6.運籌學的「引擎」--優化求解器（Optimization Solver）

分支定界法雖然思想簡單，但是實現起來卻比想像的複雜--如何管理各個分支的存儲，分支的先後順序，以及一些提高分支定界法效率的演算法，等等。

市面上知名的混合整數規劃求解器：IBM Cplex，Gurobi，FICO Xpress，SCIP。

前三個都是商業軟體，閉源，第四個是開源的由柏林ZIB研究機構開發並維護的，但是商業用途需要購買版權。這四個如果用作教學、科研，都是免費下載和使用的。

作為運籌學的引擎，優化求解器意義重大，因為所有混合整數規劃模型的求解，都需要靠它。由於是NP難問題，求解的效率至關重要，不同求解器的求解速度也千差萬別。例如同一個問題，用Cplex求解只需1分鐘，用SCIP可能就需要1小時，你自己寫B&B演算法的程序，可能需要1天！（上圖是各求解器效率對比）

而工業界非常多的問題可以被建模成整數規劃問題，例如物流、路徑規劃、航班調度等等。需要得到其精確解，便需要使用優化求解器。但是這些求解器都掌握在以上國外公司或機構，中國沒有自己的優化求解器！

這就意味著，要麼花錢買以上求解器的使用權，要麼就自己寫B&B演算法的Code，然後忍受Cplex 1分鐘可以求解的問題卻要花1天時間的求解。（很多問題時間就是金錢，例如航班延誤後剩餘航班重新排班的問題，通常需要在10分鐘內求解）

杉數科技（北京）（https://www.shanshu.ai/）可能是中國第一個投身於開發優化求解器的公司，其首席科學家顧問 Yinyu Ye（https://stanford.edu/~yyye/）教授是華人運籌學界泰斗人物。忠心希望中國早日有自己的高質量優化求解器，也希望有志青年可以加入到這個行列。

7.整數規劃模型的意義

很多人會問，既然整數規劃模型是NP難的，既然已經有了高效的啟發式演算法、近似演算法，那麼為何還要執念於精確演算法呢？

原因一是數學家的執念，數學家不care具體演算法，更關心數學模型。

其二，同一個問題，雖然可以用啟發式演算法或近似演算法，但是求得的解要麼完全沒有保證，要麼只有R這個近似倍數的保證。但是，只要把該問題數學建模成整數規劃模型，啟發式或近似演算法求得的解，都可以直接作為優化求解器的初始解（上界）。這時候，優化求解器只需求解Root Node（LRP），便可以得到下界，於是你幾乎不費力（多項式時間）便可得到一個Gap。這個Gap，便可以作為這個解的某種保證（例如，Gap是10%，你便知道這個解離最優解「不遠了」）。

此外，工業界應用上，隨著B&B演算法迭代的進行，很有可能降低上界，即找到了更優的解。在工業界，例如成本最小化問題，往往提高1個百分點，就是幾百萬甚至上千萬元成本的差別！

從這個意義上講，深度學習這個極度非凸的優化問題，其反向傳播法也可以理解成一個類似於隨機梯度下降（SGD）的啟發式演算法，它只找到一個沒有任何保證的局部最優解（貌似離全局最優解「不遠」）。如果這個優化問題可以被建模成整數規劃模型，那麼優化求解器就能給出深度學習找出的局部最優解一個Gap，以及可能再次優化這個解。（然而，實際情況是，深度學習問題的規模往往遠大於整數規劃模型的「極限」）

篇幅限制，5-7節沒有深入探究。我將在下一篇專欄著重探討整數規劃的加速，近似演算法以及啟發式演算法，優化求解器也不僅限於整數規劃，還有凸優化、非凸優化、非線性規劃等等，敬請期待。

註：知識點推薦使用書本系統的學習，本篇旨在為大家做一丁點的梳理和總結工作。

春節 AI 學習狂歡，精品課程 豪華特輯

優惠折上折，福利搶不停！

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