整數規劃經典方法-割平面法

『運籌OR帷幄』原創

作者知乎ID：留德華叫獸

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

敬請關注和擴散本公眾號及知乎同名專欄，會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態：

『運籌OR帷幄』大數據人工智慧時代的運籌學--知乎專欄：http://t.cn/RlNoO3P

某天在全球運籌學者群，好幾個小夥伴問到了關於Branch-and-Cut 以及Cutting Plane Method。由於其在整數規劃的重要作用，於是一鼓作氣寫篇專欄解釋一下。（結果還是拖到現在。。）

會點開這篇文章的小夥伴應該已是運籌學的中級玩家，至少學過線性規劃和整數規划了，因此這裡不再多軟文宣傳運籌學，有興趣的可以關注以下幾篇專欄文章。

人工智慧的「引擎」--運籌學，一門建模、優化、決策的科學：http://t.cn/ROBybx3

本文提綱：

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）問題。

（關於離散優化，分享一個免費的coursera視頻，Lecture 43 - MIP：http://t.cn/R8SePou，by 墨爾本大學Pascal Van Hentenryck教授。）

2

整數規劃的精確演算法

分支定界法

Branch-and-Bound

科學的本質便是由簡到難，先把簡單問題研究透徹，然後把複雜問題分解（decompose）成求解一個個的簡單問題，最後把簡單問題的解「有機結合」起來，希望找到原問題的全局最優解或近似解。

整數規劃問題通常是NP難（NP完全）的，求解整數規劃的精確演算法，便是利用分支定界法求解一個個線性規劃問題。

每一個線性規劃問題是多項式時間可解的，然而最壞情況需要求解2^n個線性規劃問題。（這裡假設整數變數是0,1變數，n是整數變數的個數）

這是指數爆炸！什麼意思呢？當n=100時，求解時間是1分鐘的話，那麼n=101，時間可能是2分鐘（最壞情況），n=102便是4分鐘，以此類推。。

正是由於如此，數學家們需要想出一些比分支定界更「聰明」的分解方法，包括割平面方法、行生成以及列生成方法等等。

3

整數規劃的割平面方法

Branch-and-Cut

UserCut

整數規劃中的割平面方法，大致分為砍掉實數解的分割（cut，即一個線性不等式）和砍掉整數解的分割。前者對於原問題是一個valid inequality，而後者不是。

如上圖，有這麼一個整數規劃問題，黑色線段是線性不等式，藍色的點是離散的可行域，藍色線段包圍的空間是IP Hull（整數解形成的凸包，NP-hard to find，因為一旦找到，那麼求解整數規劃只需要求解凸包這個LP問題），在其外面黑色線段的包圍是LP Hull（線性鬆弛解形成的凸包）。

正是因為IP Hull和LP Hull中間的間隙，使得該LP的最優解是fractional（對於原問題infeasible）的，而這段間隙，對於LP（線性規劃）來講，是多餘的搜索空間。如果我們在這個時候可以加上一個或多個線性不等式（cut），把無用空間完全「砍」掉，那麼LP Hull = IP Hull，這時我們就得到整數解了。

當然一般情況沒有這麼好運，可以把無用空間完全砍掉。如上圖，加上紅色虛線這個cut，我們砍掉了紅色陰影區域這部分無用空間。雖然沒有把LP Hull直接縮小成IP Hull這麼立竿見影，但對於求解原問題，由於減少了搜索空間，也是一種效率上的提升。

另外值得注意的是，紅色虛線的cut，對於原問題（IP Hull）也是滿足的（valid），它砍掉的，只是實數部分無用的搜索空間。

最後我們想像上圖是分支定界法求解到其中一個node所解得的線性鬆弛解，那麼如果該步驟在分支定界法所有（或部分）node上不斷重複（recall that一個0-1規劃每一次branch就等價於求解倆個LP問題，每個LP問題都是一個node），該方法就被稱為Branch-and-Cut。

而以上cut，在Cplex等優化求解器中，被稱為UserCut。

4

整數規劃的割平面方法

LazyCut

上一節講了砍掉實數解的cut，這一節我們講講砍掉整數解（feasible solution）的cut--LazyCut。

如上圖，我們有IP hull和LP hull，我們加上一個Lazy Constraints，這時候把頂上三個原問題的可行整數解也砍掉了。

為什麼要把原問題可行的整數解也cut掉呢？適用範圍有哪些呢？

割平面法最經典的應用，莫過於Travelling Salesman Problem（我老闆的成名作）了。這個問題是每個學運籌學特別是組合優化必學的經典問題。

而這個問題求解的關鍵，便是割平面方法-- the subtour elimination constraints.

如上圖，TSP需要找從一點出發，遍歷所有城市（1-6點）再回到出發點的cycle（迴路）。為了簡化問題，在master problem（初始問題）的表達式中，我們忽略subtour（小的cycle，例如上圖4-5-6）約束（因為有指數級個數該約束），然後求解該IP問題。

忽略掉subtour求得的IP問題雖然是整數可行解，但是其中可能存在subtour（如上圖倆個subtour），因此其實並不是我們想要的解。這時候，我們設計一個啟發式演算法，來探測這些subtour，然後加上相應的cut砍掉這些subtour對應的整數解，然後再次求解IP。

由此循環，直到求得的IP整數解中，不再存在subtour，這時候我們找到了最終問題的全局最優解。

關於TSP問題，除了我老闆1994年出版的教科書The Traveling Salesman - Computational Solutions for TSP Gerhard Reinelt Springer：http://t.cn/R8SeV82，最好的參考資料莫過於滑鐵盧大學William Cook：http://t.cn/R8SeCw5教授的網頁了：

Solving a TSP > Tour Quality > Subtour Elimination：http://t.cn/R8Sej8Y

這一節我非常簡略地引入TSP問題介紹了LazyCut，由於是我老闆的成名作（老闆同時還創立了TSP的數據集TSPLIB：http://t.cn/R8Seny7），也因為該問題麻雀雖小五臟俱全，日後有時間一定單篇專欄詳細介紹該問題。

關於割平面法的優化求解器實現，通常都需要用到其中的callback function，cplex等求解器也都有關於此法的算例，請參考example文件夾中的源代碼。日後有空我也會專門寫專欄詳述。

本節最後和大家分享一個非常棒的OR博客（by Prof.Paul Rubin：http://t.cn/R8SDq5z），關於UserCut和LazyCut，那裡有著更加詳細的解釋。（有幸在美國一次MIP會議上與其聊過）

OR in an OB World--User Cuts versus Lazy Constraints：http://t.cn/R8SD6Gv

5

行生成方法

Row Generation

割平面方法，從更宏觀的角度，可以看作是一種行生成方法。這裡的「行」（row），指的是線性不等式。每找到一個cut，就增加一個線性不等式。

線性規劃的演算法複雜度和連續變數呈多項式級關係，另外隨著約束條件（不等式）個數的增加，求解時間也會隨之增加。（不確定呈什麼關係，求拍磚）

上面說到整數規劃的演算法複雜度和整數變數的個數n基本呈指數關係，那麼它還和其他什麼因素相關呢？答案是不等式的個數。（recall求解整數規劃需要求解一個個的線性規劃）

我們從線性規劃角度，理解行生成方法的基本思想：形成極值（最優解）所需要的約束條件個數，往往遠小於原問題的約束條件個數。因此為何不在需要的時候，才把這些「重要」的約束條件加上來呢？

下面舉個簡單例子：

如下圖，原問題有5個不等式（一條紅線代表一個不等式），但是最優解點D只需CD和DE 2個不等式即可表述。

因此行生成方法的基本思路：先求解原問題的鬆弛問題，即初始問題（master problem）不加約束條件或只加其中幾個約束，然後求解該鬆弛問題，如果得到的解是可行解，那麼該解就是原問題的最優解（例如剛開始運氣很好地加了CD和DE）。

如果得到的解對原問題是不可行的，例如解是（0，6）這個點（因為沒有加BC這個約束），或者無界的，那麼這時候加上BC這個不等式便可以把這個不可行解排除。

以此循環，直到鬆弛問題的解是可行的，那麼該解也是原問題的最優解。

而通過行生成方法，上面問題本來需要5個約束條件，很可能只需要2-3個約束條件，上面的循環已經終止了。

在實際問題中，最優解所需要的約束條件往往遠遠小於原問題的約束條件個數。例如幾萬個約束條件，實際只有幾百個是用來刻畫最優解的。那麼這個時候，割平面方法便可以大大提速線性規劃的求解。

在上一節的TSP問題中，subtour elimination constraints的個數是指數級的（因此不可能把他們全部加進來），但是求解實際問題中，往往通過割平面方法只需找到其中幾千或幾百個，即可找到原問題的最優解。用到的，正是相似的思路。

其實TSP問題是有完整刻畫的表達式的（Complete Formulation），這時的約束個數雖然不是指數級，但是數量也非常大，因此求解效率很低。割平面方法的引入，大大增加了TSP問題求解的高效性，這也是該方法一次完美的show off。

搜索Literature 行生成方法，最先映入眼帘的可能是Benders" Decomposition。在那裡，一般把整數和實數變數隔離做分解，然後有比較「嚴格」的如何選取初始約束以及如何一步步地增加約束（feasibility cut和optimality cut）。

與行生成法對偶的方法，是列生成法（逐步增加變數個數）。其中的Dantzig-Wolfe分解法，是Benders" Decomposition的dual problem，這些是以後我將和大家分享的求解整數規劃眾多分解法其中的倆個。

由於時間關係不再展開，作為預熱，有興趣的可以參考：

BENDERS DECOMPOSITION WITH GAMS：http://t.cn/R8SDl3t

Column Generation and Dantzig-Wolfe Decomposition：http://t.cn/R8SD3QV

6

割平面法

在計算機視覺的應用

割平面法，可以說是整數、離散優化最經典的分解方法之一，在運籌學各個方向被廣泛應用。

下面我僅提一下其在計算機視覺、圖像分割（找圖像中object的）領域的應用 -- Multicuts

Globally Optimal Image Partitioning by Multicuts：http://t.cn/R8Skv8Q(主要貢獻及其拓展出自海德堡大學團隊).

而我的博士論文，也大量用到該方法，同樣是應用在圖像分割問題。

該圖像分割問題被數學建模成一個求解能量函數最小值的優化問題，其中multicut constraints的個數是指數級的，因此採用割平面方法add on-the-fly.

以下是Multicut Problem的簡短陳述，摘自：A First Derivative Potts Model for Segmentation and Denoising Using ILP：http://t.cn/R8Or4g7

上面公式中，x_e是一個布爾變數，當它為1時, 即是倆個segment的臨界處（分割線--下圖中黃色輪廓）。這裡僅po幾張實驗效果圖，如有興趣, paper鏈接：

Globally Optimal Image Partitioning by Multicuts：http://t.cn/R8OrMQ0

如果你和一年多前的我一樣，是AI、計算機視覺領域的小白，那麼下面的文章可能會對你有用：

大話「人工智慧、數據科學、機器學習」-- 綜述：http://t.cn/RXkSyMn

本文首發於『運籌OR帷幄』，轉載請聯繫本公眾號獲得授權

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