離散/整數組合優化概述及其在AI的應用

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

本文提綱：

1，運籌學、線性規劃回顧 2，整數規劃問題 3，什麼是組合優化

4，非凸優化 5，整數規劃與非凸優化的關係

6，整數規劃、非凸優化為何重要 7，整數規劃在工業界的應用

8，整數規劃在AI的應用和展望

註：以下文中黑體字代表其在學術界的術語

1，運籌學、線性規劃（Linear Programming）回顧

運籌學的初學者，歡迎查看我在下面的回答：

運籌學、數學規劃（Math Programming）問題的數學表達式，由自變數（Variables）、目標函數（Objective Function）和約束條件（Constraints）組成，所有優化問題本質上都可以化簡為由它們組成的數學表達式，然後求解滿足約束條件下使得目標函數最大/小的變數的值。

如上圖，當自變數是連續的，目標函數和不等式是線性的時候，該問題被稱為線性規劃問題。線性規劃因其具有的良好性質（例如，最優解必定出現在極點），可以用單純型法（Simplex Method）或內點演算法（Interior Method）高效地求解，熟悉演算法複雜度的童鞋，知道它是多項式時間可解的（Polynomial Time Solvable--O（n^k））。這裡n表示自變數個數。

可行域（Feasible Set）：可行解的集合。如下圖，陰影區域（多面體、Polyhedron）即為三個線性不等式（半平面）組成的可行域。是不是很眼熟？其實高中代數課大家就已接觸過線性規划了。

2，整數規劃（Integer Programming）問題

整數規劃，或者離散優化（Discrete Optimization），是指數學規劃問題中自變數存在整數。與線性規劃連續的可行域不同，整數規劃的可行域是離散的。

如上圖，藍線依舊代表線性不等式，但是這裡x,y被約束成整數變數，因此可行域變成了紅線區域內的9個離散的點。

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

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

x是連續的，y被約束成整數變數，這時候可行域變成了4條離散的橘黃色線段+4處的紅色整數點（0,4）。課後作業，求圖中的凸包。

整數規劃的精確演算法通常需要用到分支定界法（Branch and Bound Method）,以及增加分支定界效率的各種技巧，例如割平面方法（Cutting Planes Method）。總的來說，求解整數規劃的精確解是NP難的，也就是指數級演算法複雜度（Exponential Time Solvable）。

怎麼來理解指數級複雜度呢？假設這裡的整數是0,1變數，那麼我們可以簡單地理解為演算法複雜度是2^n（需要解2^n個線性規劃問題）。也就是說，每增加一個0，1變數，求解的速度就有可能要增加一倍！例如求解n=100的整數規劃問題需要1小時，那麼求解n=101的規模可能會需要2小時，n=102需要4小時，n=105需要32小時。。這就是指數爆炸！

因此，整數規劃問題被看作數學規劃里、甚至是世界上最難的問題之一，被很多其他領域（例如機器學習）認為是不可追蹤（Intractable）的問題，也就是他們直接放棄治療了。

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

篇幅限制，我將在下一篇專欄著重探討整數規劃精確解的演算法、整數規劃求解器、近似演算法以及啟發式演算法，敬請期待。

3，什麼是組合優化(Combinatorial Optimization)

通俗的講，我把組合優化理解為，在組合優化種可能性里找出最優的方案。假設自變數為n，用強力搜索法（Brute-force Algorithm）來解組合優化的演算法複雜度最壞需要n的階乘！什麼概念？這比指數爆炸還要可怕！

從這個意義上講，組合優化是整數規劃的子集。的確，絕大多數組合優化問題都可以被建模成（混合）整數規劃模型來求解。但是似乎學術圈更多地把組合優化與圖（Graph）優化以及網路流（Network Flow）優化聯繫在一起，並且最終目標不在精確解，而是近似解。（這點可以從整數規劃的國際會議上看出）

Anyway，這裡開始，我將混淆整數規劃、離散優化、組合優化。

下面給出一個經典的組合優化例子-最大流問題（Max Flow Problem）：

給定一張圖G（V，E），V是點（Node）的集合，E是邊（Edge）的集合。該問題試圖從點0到5導流最大的流量，邊上的數字代表該條邊的最大流量，因此形成了約束條件--每條邊的流量不得超過該條邊的限額。自然而然地，該問題可以被建模成一個整數規劃問題。

我們跳過模型和演算法，直觀的判斷該問題的演算法複雜度大概為多少。設想從0出發，有倆種可能線路，0到1以及0到2；從1和2出發，有分別有倆種可能的線路。因此，可以初步判斷，改問題如果用強力演算法（窮舉法），演算法複雜度將為指數級！

但是聰明的組合優化學家，把這個看似指數級演算法複雜度的問題，用巧妙的演算法多項式時間便可求解出最優解。This is the beauty of Mathematics!

時間關係，該問題的具體模型和近似演算法，會放在下一篇專欄展開，有興趣的可以搜索「Max Flow/Min Cut」。

4，非凸優化 （Non-Convex Optimization）

凸（Convex） VS 非凸的概念，數學定義就不寫了，介紹個直觀判斷一個集合是否為Convex的方法，如下圖：

簡單的測試一個集合是不是凸的，只要任意取集合中的倆個點並連線，如果說連線段完全被包含在此集合中，那麼這個集合就是凸集，例如左圖所示。

凸優化有個非常重要的定理，即任何局部最優解即為全局最優解。由於這個性質，只要設計一個較為簡單的局部演算法，例如貪婪演算法（Greedy Algorithm）或梯度下降法（Gradient Decent），收斂求得的局部最優解即為全局最優。因此求解凸優化問題相對來說是比較高效的。這也是為什麼機器學習中凸優化的模型非常多，畢竟機器學習處理大數據，需要高效的演算法。

而非凸優化問題被認為是非常難求解的，因為可行域集合可能存在無數個局部最優點，通常求解全局最優的演算法複雜度是指數級的（NP難）。如下圖：

最經典的演算法要算蒙特卡羅投點法(Monte Carlo Algorithm)了，大概思想便是隨便投個點，然後在附近區域（可以假設convex）用2中方法的進行搜索，得到局部最優值。然後隨機再投個點，再找到局部最優點。如此反覆，直到滿足終止條件。

假設有1w個局部最優點，你至少要投點1w次吧？並且你還要假設每次投點都投到了不同的區域，不然你只會搜索到以前搜索過的局部最優點。

5，整數規劃與非凸優化的關係

大家或許不知道，（混合）整數規劃被稱為極度非凸問題（highly nonconvex problem），如下圖：

實心黑點組成的集合，是一個離散集，按照4中判斷一個集合是否為凸集的技巧，我們很容易驗證這個離散集是非凸的，並且相比4中的非凸集更甚。因此整數規劃問題也是一個非凸優化問題。

6，整數規劃、非凸優化為何重要

雖然時間是連續的，但是社會時間卻是離散的。例如時刻表，通常都是幾時幾分，即使精確到幾秒，它還是離散的（整數）。沒見過小數計數的時刻表吧？

同樣，對現實社會各行各業問題數學建模的時候，整數變數有時是不可避免的。例如：x輛車，y個人。x，y這裡便是整數變數，小數是沒有意義的。

決策變數(Decision Varible): x=.

0/1變數被廣泛地應用在商業和決策領域。我們假設變數x=，當x=1的時候，我們便可以建模執行x這個決策；x=0，則表示不執行。這樣引入決策變數x的建模技巧，在工業界案例中屢見不鮮。

從這些案例，社會是由一個個離散變數組成的。

關於非凸優化，現實生活中，萬物的本質是非凸的，就像萬物是趨於混亂（Chaos）的，規則化需要代價。如果把4中的圖看作山川盆地，你在現實中有見過左圖那麼「光滑」的地形么？右圖才是Reality！

說到這裡，當然不能否定了凸優化和連續優化的作用，科學的本質便是由簡到難，先把簡單問題研究透徹，然後把複雜問題簡化為求解一個個的簡單問題。求解整數規劃便是利用分支定界法求解一個個線性規劃問題，非凸優化同樣如此。

7，整數規劃在工業界的應用

路徑優化問題（Routing Problem）--交通領域（GPS導航）；

倉儲、運輸等物流（Logistics）以及供應鏈(Supply chain)領域；

製造業里的生產流程優化（Process Optimization）；

電力領域的電網的布局以及分配(Power Grid)；

電子工程里的設施部件分配問題(Facility Layout Problem)；

能源領域的優化，如：如何鋪設輸油管道；

火車、課程、飛機時刻表安排問題等調度問題 (Scheduling Problem);

資產配置 （Asset Allocation）、風險控制 (risk management)等經濟金融領域的應用；

以上工業界的應用，頻繁使用著決策變數，以及整數變數，建模成（混合）整數規劃模型，而機器學習（ML），特別是深度學習（DL），至今沒有怎麼滲透進來。也希望有志青年探索ML、DL在這些領域的應用。

這裡我舉一個統計和機器學習的例子，這個模型也可以和統計里經典的Lasso問題聯繫起來，以及可以給出L0範數問題的精確解。

如下圖，是一個分段常數回歸問題。統計中大家都知道線性回歸和常數回歸，其中常數回歸即求一組數的平均值。但是這裡，我們想對數據分段，並且不知道分段的節點在哪裡。如下例所示，假設n個點，要分成三段作常數回歸，節點有2個。那麼節點的選擇有n選2種可能性，從這個意義上理解，這個問題是一個組合優化的問題。

自變數有實數變數w和整數變數x，y_i是常數，即點i的值，w_i是回歸值，上半部分的表達式可以看作是偽表達式（pseudo formulation），L0函數即向量中非零的個數（可能需要一些高等的數學知識）。我們直接看下半部分的混合整數非線性規劃模型。

我們引進了一個0/1決策變數，X_,這個變數是作用在邊上的。我們希望當它是處於節點位置，即倆段常數回歸的臨界處，就等於1；但它處於某一段常數回歸中間時，就等於0.

因此目標函數前半部分是回歸方程，希望回歸的誤差越小越好，後半部分即為規則化項（regularization term），用來約束分段的個數，來懲罰過多的分段以防止過擬合（over-fitting）。大家經常可以在信號處理、圖像處理中看到這樣的目標函數。

約束條件第一個不等式保證了同一個分段回歸中，w_i和w_的值相等，因為x_=0；而在節點處，他們可以不相等，M是一個很大的常數，以保證節點處x_=1時，不等式總是成立。

寫出了這個整數規劃模型，我們就可以編程並調用整數規劃的優化求解器來求解這個問題的最優解。例如IBM Cplex。雖然整數規劃通常的演算法複雜度是指數級的，但是比起強力搜索，還是會高效很多很多。這樣我們就可以得到每個點的回歸值w以及分段的節點，即哪些點x_e=1。

展望：

深度學習的優化問題在運籌學看來是「小兒科」，這句話可能會打臉大部分觀眾。雖然目標函數非常複雜，但是它沒有約束條件阿！

深度學習里的損失函數，是一個高度複合的函數。例如h(x)=f(g(x))就是一個f和g複合函數。深度學習里用到的函數，Logistic, ReLU等等，都是非線性 ，並且非常多。把他們複合起來形成的函數h,便是非凸的。但是深度學習訓練參數的優化問題，本質是一個無約束的非凸優化問題。求解這個非凸函數的最優解，類似於求凸優化中某點的gradient，然後按照梯度最陡的方向搜索。不同的是，複合函數無法求gradient，於是這裡用方向傳播法（Back Propagation）求解一個類似梯度的東西，反饋能量，然後更新。

機器學習、數據科學因為處理數據量龐大，因此研究問題主要的方法還是凸優化模型（包括線性規劃、錐優化），原因正是求解高效，問題可以scale。

雖然目前還很小眾，但是隨著計算機硬體能力的提高，以及GPU並行計算的流行，以及非凸優化演算法、模型的進化，想必非凸優化，（混合）整數規劃會是未來的研究熱點。

敬請關注我老闆，Gerhard Reinelt 教授，以及我們的合作教授之一，法國Rouen的Stephane Canu教授，最近便投身於整數規劃在機器學習的應用。（當然還有我：）以及蒙特利爾的Andrea Lodi教授，目前與Yoshua探索著MIP與DL的交叉。

------------------------------------------------------------------------------------------

希望這個系列的專欄，可以為運籌學在中國的普及，起到一點推動的作用。

如果你的想法和我一樣，或者這篇專欄給你帶來了普及效果，請不要吝惜您的「贊」。

如果你是運籌學博士或博士在讀，歡迎知乎私信我，我會拉你進全球運籌學者群（私信請附上個人或機構主頁），也歡迎投稿到該專欄。

歡迎訪問海德堡大學離散與組合優化實驗室：

歡迎大家關注我的運籌學專欄，會陸續發布運籌學、人工智慧相關乾貨：

歡迎參加我2017.6.11號舉辦的「運籌學綜述」知乎live，探討關於運籌學、優化、AI的相關話題：

最後是通往未來運籌學、數據科學家的傳送門，以及我在知乎用心回答的匯總：

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