前言：運(yùn)籌學(xué)在國內(nèi)，遠(yuǎn)沒有新興的人工智能以及傳統(tǒng)學(xué)科統(tǒng)計(jì)來的普及。人工智能、統(tǒng)計(jì)問題，最后幾乎都能化簡成求解一個(gè)能量/損失函數(shù)的優(yōu)化問題。但相信很多人不知道，運(yùn)籌學(xué)正是研究優(yōu)化理論的學(xué)科。因此，我把運(yùn)籌學(xué)稱為人工智能、大數(shù)據(jù)的“引擎”，正本清源其在人工智能中重要性。

作者 留德華叫獸 系美國Clemson大學(xué)數(shù)學(xué)碩士(運(yùn)籌學(xué)方向)、Ph.D. candidate，歐盟瑪麗居里學(xué)者，德國海德堡大學(xué)數(shù)學(xué)博士(離散優(yōu)化、圖像處理方)，讀博期間前往意大利博洛尼亞大學(xué)、IBM實(shí)習(xí)半年，巴黎綜合理工訪問一季?，F(xiàn)任德國某汽車集團(tuán)無人駕駛部門，從事大數(shù)據(jù)和計(jì)算機(jī)視覺算法的研發(fā)。讀博期間創(chuàng)辦【運(yùn)籌OR帷幄】、【DIY飛躍計(jì)劃】社區(qū)并運(yùn)營至今，2020.08創(chuàng)辦【DeepMatch交友AI】社區(qū)?，知乎｜今日頭條｜微博等平臺科普自媒體創(chuàng)作者（近20w關(guān)注者）。

本文提綱

• 運(yùn)籌學(xué)、線性規(guī)劃回顧?

• ?整數(shù)規(guī)劃問題

• 什么是組合優(yōu)化

• 非凸優(yōu)化

• 整數(shù)規(guī)劃與非凸優(yōu)化的關(guān)系

• 整數(shù)規(guī)劃、非凸優(yōu)化為何重要

• 整數(shù)規(guī)劃在工業(yè)界的應(yīng)用

• 整數(shù)規(guī)劃在AI的應(yīng)用和展望

注：以下文中黑體字代表其在學(xué)術(shù)界的術(shù)語

首先，對運(yùn)籌學(xué)（O.R.）還比較陌生的童鞋，請戳我在【運(yùn)籌OR帷幄】的開篇之作：

《運(yùn)籌學(xué)--一門建模、優(yōu)化、決策的科學(xué)》?http://t.cn/ROBybx3

/ 1?/

運(yùn)籌學(xué)、線性規(guī)劃（Linear Programming）回顧

• 運(yùn)籌學(xué)的初學(xué)者，歡迎查看我在下面的回答：《運(yùn)籌學(xué)如何入門？》http://t.cn/RlNoHiM

運(yùn)籌學(xué)、數(shù)學(xué)規(guī)劃（Math Programming）問題的數(shù)學(xué)表達(dá)式，由自變量（Variables）、目標(biāo)函數(shù)（Objective Function）和約束條件（Constraints）組成，所有優(yōu)化問題本質(zhì)上都可以化簡為由它們組成的數(shù)學(xué)表達(dá)式，然后求解滿足約束條件下使得目標(biāo)函數(shù)最大/小的變量的值。

如上圖，當(dāng)自變量是連續(xù)的，目標(biāo)函數(shù)和不等式是線性的時(shí)候，該問題被稱為線性規(guī)劃問題。線性規(guī)劃因其具有的良好性質(zhì)（例如，最優(yōu)解必定出現(xiàn)在極點(diǎn)），可以用單純型法（Simplex Method）或內(nèi)點(diǎn)算法（Interior Method）高效地求解，熟悉算法復(fù)雜度的童鞋，知道它是多項(xiàng)式時(shí)間可解的（Polynomial Time Solvable--O（n^k）），這里n表示自變量個(gè)數(shù)。

可行域（Feasible Set）：可行解的集合。

如下圖，陰影區(qū)域（多面體、Polyhedron）即為三個(gè)線性不等式（半平面）組成的可行域。

是不是很眼熟？其實(shí)高中代數(shù)課大家就已接觸過線性規(guī)劃了。

/ 2 /

整數(shù)規(guī)劃（Integer Programming）問題

整數(shù)規(guī)劃，或者離散優(yōu)化（Discrete Optimization），是指數(shù)學(xué)規(guī)劃問題中自變量存在整數(shù)。與線性規(guī)劃連續(xù)的可行域不同，整數(shù)規(guī)劃的可行域是離散的。

如上圖，藍(lán)線依舊代表線性不等式，但是這里x,y被約束成整數(shù)變量，因此可行域變成了紅線區(qū)域內(nèi)的9個(gè)離散的點(diǎn)。

凸包（Convex Hull）:整數(shù)規(guī)劃所有可行點(diǎn)的凸包圍，即圖中紅線組成的多面體（想象多維的情況）。

凸包是未知的，已知的是藍(lán)線的不等式，并且凸包是非常難求解的，或者形成凸包需要指數(shù)數(shù)量級的線性不等式（圖中紅線）。如果知道了凸包的所有線性表示，那么整數(shù)規(guī)劃問題就可以等價(jià)為求解一個(gè)凸包表示的線性規(guī)劃問題。

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

x是連續(xù)的，y被約束成整數(shù)變量，這時(shí)候可行域變成了4條離散的橘黃色線段+4處的紅色整數(shù)點(diǎn)（0,4）。

課后作業(yè)，求圖中的凸包。

整數(shù)規(guī)劃的精確算法通常需要用到分支定界法（Branch and Bound Method）,以及增加分支定界效率的各種技巧，例如割平面方法（Cutting Planes Method）。

總的來說，求解整數(shù)規(guī)劃的精確解是NP難的，也就是指數(shù)級算法復(fù)雜度（Exponential Time Solvable）。

怎么來理解指數(shù)級復(fù)雜度呢？假設(shè)這里的整數(shù)是0,1變量，那么我們可以簡單地理解為算法復(fù)雜度是2^n（需要解2^n個(gè)線性規(guī)劃問題）。也就是說，每增加一個(gè)0，1變量，求解的速度就有可能要增加一倍！

例如求解n=100的整數(shù)規(guī)劃問題需要1小時(shí)，那么求解n=101的規(guī)?？赡軙枰?小時(shí)，n=102需要4小時(shí)，n=105需要32小時(shí)……這就是指數(shù)爆炸！

因此，整數(shù)規(guī)劃問題被看作數(shù)學(xué)規(guī)劃里、甚至是世界上最難的問題之一，被很多其他領(lǐng)域（例如機(jī)器學(xué)習(xí)）認(rèn)為是不可追蹤（Intractable）的問題，也就是他們直接放棄治療了。

作為研究世界上最難問題的學(xué)者，想出了解決整數(shù)規(guī)劃問題的各種其他途徑，例如近似算法（Approximation Algorithms），啟發(fā)式算法（Heuristic Algorithms），遺傳算法（Evolution Algorithms, Meta-Heuristic）等等。它們雖然不能求得整數(shù)規(guī)劃的最優(yōu)解，但是卻能在短時(shí)間（通常多項(xiàng)式時(shí)間）內(nèi)給出一個(gè)較好的可行解。

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

/ 3 /

什么是組合優(yōu)化(Combinatorial Optimization)

通俗的講，我把組合優(yōu)化理解為，在組合優(yōu)化種可能性里找出最優(yōu)的方案。假設(shè)自變量為n，用強(qiáng)力搜索法（Brute-force Algorithm）來解組合優(yōu)化的算法復(fù)雜度最壞需要n的階乘！什么概念？這比指數(shù)爆炸還要可怕！

從這個(gè)意義上講，組合優(yōu)化是整數(shù)規(guī)劃的子集。

的確，絕大多數(shù)組合優(yōu)化問題都可以被建模成（混合）整數(shù)規(guī)劃模型來求解。但是似乎學(xué)術(shù)圈更多地把組合優(yōu)化與圖（Graph）優(yōu)化以及網(wǎng)絡(luò)流（Network Flow）優(yōu)化聯(lián)系在一起，并且最終目標(biāo)不在精確解，而是近似解。（這點(diǎn)可以從整數(shù)規(guī)劃的國際會議上看出）

Anyway，這里開始，我將混淆整數(shù)規(guī)劃、離散優(yōu)化、組合優(yōu)化。

下面給出一個(gè)經(jīng)典的組合優(yōu)化例子-最大流問題（Max Flow Problem）：

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

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

但是聰明的組合優(yōu)化學(xué)家，把這個(gè)看似指數(shù)級算法復(fù)雜度的問題，用巧妙的算法多項(xiàng)式時(shí)間便可求解出最優(yōu)解。This is the beauty of Mathematics!

▎ 時(shí)間關(guān)系，該問題的具體模型和近似算法，會放在下一篇專欄展開，有興趣的可以搜索“Max Flow/Min Cut”。

/ 4 /

非凸優(yōu)化 （Non-Convex Optimization）

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

簡單的測試一個(gè)集合是不是凸的，只要任意取集合中的倆個(gè)點(diǎn)并連線，如果說連線段完全被包含在此集合中，那么這個(gè)集合就是凸集，例如左圖所示。

凸優(yōu)化有個(gè)非常重要的定理，即任何局部最優(yōu)解即為全局最優(yōu)解。由于這個(gè)性質(zhì)，只要設(shè)計(jì)一個(gè)較為簡單的局部算法，例如貪婪算法（Greedy Algorithm）或梯度下降法（Gradient Decent），收斂求得的局部最優(yōu)解即為全局最優(yōu)。因此求解凸優(yōu)化問題相對來說是比較高效的。這也是為什么機(jī)器學(xué)習(xí)中凸優(yōu)化的模型非常多，畢竟機(jī)器學(xué)習(xí)處理大數(shù)據(jù)，需要高效的算法。

而非凸優(yōu)化問題被認(rèn)為是非常難求解的，因?yàn)榭尚杏蚣峡赡艽嬖跓o數(shù)個(gè)局部最優(yōu)點(diǎn)，通常求解全局最優(yōu)的算法復(fù)雜度是指數(shù)級的（NP難）。如下圖：

最經(jīng)典的算法要算蒙特卡羅投點(diǎn)法(Monte Carlo Algorithm)了，大概思想便是隨便投個(gè)點(diǎn)，然后在附近區(qū)域（可以假設(shè)convex）用2中方法的進(jìn)行搜索，得到局部最優(yōu)值。然后隨機(jī)再投個(gè)點(diǎn)，再找到局部最優(yōu)點(diǎn)。如此反復(fù)，直到滿足終止條件。

假設(shè)有1w個(gè)局部最優(yōu)點(diǎn)，你至少要投點(diǎn)1w次吧？并且你還要假設(shè)每次投點(diǎn)都投到了不同的區(qū)域，不然你只會搜索到以前搜索過的局部最優(yōu)點(diǎn)。

/ 5 /

整數(shù)規(guī)劃與非凸優(yōu)化的關(guān)系

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

實(shí)心黑點(diǎn)組成的集合，是一個(gè)離散集，按照4中判斷一個(gè)集合是否為凸集的技巧，我們很容易驗(yàn)證這個(gè)離散集是非凸的，并且相比4中的非凸集“更甚”。因此整數(shù)規(guī)劃問題也是一個(gè)非凸優(yōu)化問題。

/ 6 /

整數(shù)規(guī)劃、非凸優(yōu)化為何重要

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

同樣，對現(xiàn)實(shí)社會各行各業(yè)問題數(shù)學(xué)建模的時(shí)候，整數(shù)變量有時(shí)是不可避免的。例如：x輛車，y個(gè)人。x，y這里便是整數(shù)變量，小數(shù)是沒有意義的。

決策變量(Decision Varible): x={0,1}.

0/1變量被廣泛地應(yīng)用在商業(yè)和決策領(lǐng)域。我們假設(shè)變量x={0,1}，當(dāng)x=1的時(shí)候，我們便可以建模執(zhí)行x這個(gè)決策；x=0，則表示不執(zhí)行。這樣引入決策變量x的建模技巧，在工業(yè)界案例中屢見不鮮。

從這些案例，社會是由一個(gè)個(gè)離散變量組成的。

關(guān)于非凸優(yōu)化，現(xiàn)實(shí)生活中，萬物的本質(zhì)是非凸的，就像萬物是趨于混亂（Chaos）的，規(guī)則化需要代價(jià)。如果把4中的圖看作山川盆地，你在現(xiàn)實(shí)中有見過左圖那么“光滑”的地形么？右圖才是Reality！

說到這里，當(dāng)然不能否定了凸優(yōu)化和連續(xù)優(yōu)化的作用，科學(xué)的本質(zhì)便是由簡到難，先把簡單問題研究透徹，然后把復(fù)雜問題簡化為求解一個(gè)個(gè)的簡單問題。求解整數(shù)規(guī)劃便是利用分支定界法求解一個(gè)個(gè)線性規(guī)劃問題，非凸優(yōu)化同樣如此。

/ 7?/

整數(shù)規(guī)劃在工業(yè)界的應(yīng)用

• 路徑優(yōu)化問題（Routing Problem）--交通領(lǐng)域（GPS導(dǎo)航）；

• 倉儲、運(yùn)輸?shù)任锪鳎?strong>Logistics）以及供應(yīng)鏈(Supply chain)領(lǐng)域；

• 制造業(yè)里的生產(chǎn)流程優(yōu)化（Process Optimization）；

• 電力領(lǐng)域的電網(wǎng)的布局以及分配(Power Grid)；

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

• 能源領(lǐng)域的優(yōu)化，如：如何鋪設(shè)輸油管道；

• 火車、課程、飛機(jī)時(shí)刻表安排問題等調(diào)度問題 (Scheduling Problem);

• 資產(chǎn)配置 （Asset Allocation）、風(fēng)險(xiǎn)控制 (risk management)等經(jīng)濟(jì)金融領(lǐng)域的應(yīng)用；

以上工業(yè)界的應(yīng)用，頻繁使用著決策變量，以及整數(shù)變量，建模成（混合）整數(shù)規(guī)劃模型，而機(jī)器學(xué)習(xí)（ML），特別是深度學(xué)習(xí)（DL），至今沒有怎么滲透進(jìn)來。也希望有志青年探索ML、DL在這些領(lǐng)域的應(yīng)用。

/ 8 /

整數(shù)規(guī)劃在AI的應(yīng)用案例

這里我舉一個(gè)統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的例子，這個(gè)模型也可以和統(tǒng)計(jì)里經(jīng)典的Lasso問題聯(lián)系起來，以及可以給出L0范數(shù)問題的精確解。

如下圖，是一個(gè)分段常數(shù)回歸問題。統(tǒng)計(jì)中大家都知道線性回歸和常數(shù)回歸，其中常數(shù)回歸即求一組數(shù)的平均值。但是這里，我們想對數(shù)據(jù)分段，并且不知道分段的節(jié)點(diǎn)在哪里。如下例所示，假設(shè)n個(gè)點(diǎn)，要分成三段作常數(shù)回歸，節(jié)點(diǎn)有2個(gè)。那么節(jié)點(diǎn)的選擇有n選2種可能性，從這個(gè)意義上理解，這個(gè)問題是一個(gè)組合優(yōu)化的問題。

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

我們引進(jìn)了一個(gè)0/1決策變量，X_{ei},這個(gè)變量是作用在邊上的。我們希望當(dāng)它是處于節(jié)點(diǎn)位置，即倆段常數(shù)回歸的臨界處，就等于1；但它處于某一段常數(shù)回歸中間時(shí)，就等于0。

因此目標(biāo)函數(shù)前半部分是回歸方程，希望回歸的誤差越小越好，后半部分即為規(guī)則化項(xiàng)（regularization term），用來約束分段的個(gè)數(shù)，來懲罰過多的分段以防止過擬合（over-fitting）。大家經(jīng)?？梢栽谛盘柼幚?、圖像處理中看到這樣的目標(biāo)函數(shù)。

約束條件第一個(gè)不等式保證了同一個(gè)分段回歸中，w_i和w_{i+1}的值相等，因?yàn)閤_{ei}=0；而在節(jié)點(diǎn)處，他們可以不相等，M是一個(gè)很大的常數(shù)，以保證節(jié)點(diǎn)處x_{ei}=1時(shí)，不等式總是成立。

寫出了這個(gè)整數(shù)規(guī)劃模型，我們就可以編程并調(diào)用整數(shù)規(guī)劃的優(yōu)化求解器來求解這個(gè)問題的最優(yōu)解。例如IBM Cplex。雖然整數(shù)規(guī)劃通常的算法復(fù)雜度是指數(shù)級的，但是比起強(qiáng)力搜索，還是會高效很多很多。這樣我們就可以得到每個(gè)點(diǎn)的回歸值w以及分段的節(jié)點(diǎn)，即哪些點(diǎn)x_e=1。

▎展望

深度學(xué)習(xí)的優(yōu)化問題在運(yùn)籌學(xué)看來是“小兒科”，這句話可能會打臉大部分觀眾。雖然目標(biāo)函數(shù)非常復(fù)雜，但是它沒有約束條件阿！

深度學(xué)習(xí)里的損失函數(shù)，是一個(gè)高度復(fù)合的函數(shù)。

例如h(x)=f(g(x))就是一個(gè)f和g復(fù)合函數(shù)。深度學(xué)習(xí)里用到的函數(shù)，Logistic, ReLU等等，都是非線性 ，并且非常多。把他們復(fù)合起來形成的函數(shù)h,便是非凸的。但是深度學(xué)習(xí)訓(xùn)練參數(shù)的優(yōu)化問題，本質(zhì)是一個(gè)無約束的非凸優(yōu)化問題。求解這個(gè)非凸函數(shù)的最優(yōu)解，類似于求凸優(yōu)化中某點(diǎn)的gradient，然后按照梯度最陡的方向搜索。不同的是，復(fù)合函數(shù)無法求gradient，于是這里用方向傳播法（Back Propagation）求解一個(gè)類似梯度的東西，反饋能量，然后更新。

機(jī)器學(xué)習(xí)、數(shù)據(jù)科學(xué)因?yàn)樘幚頂?shù)據(jù)量龐大，因此研究問題主要的方法還是凸優(yōu)化模型（包括線性規(guī)劃、錐優(yōu)化），或者是一階優(yōu)化算法，原因正是求解高效，問題可以scale。

《想學(xué)數(shù)據(jù)分析（人工智能）需要學(xué)哪些課程？》?http://t.cn/RQo3JRK

雖然目前還很小眾，但是隨著計(jì)算機(jī)硬件能力的提高，以及GPU并行計(jì)算的流行，以及非凸優(yōu)化算法、模型的進(jìn)化，想必非凸優(yōu)化，（混合）整數(shù)規(guī)劃會是未來的研究熱點(diǎn)。

敬請關(guān)注我老板，Gerhard Reinelt 教授，以及我們的合作教授之一，法國Rouen的Stephane Canu教授，最近便投身于整數(shù)規(guī)劃在機(jī)器學(xué)習(xí)的應(yīng)用。以及蒙特利爾的Andrea Lodi教授，目前與Yoshua探索著MIP與DL的交叉。當(dāng)然還有運(yùn)籌學(xué)界泰斗之一，MIT ORC的Dimitris Bertsimas，近十年都在統(tǒng)計(jì)、數(shù)據(jù)學(xué)界推崇整數(shù)規(guī)劃。

▎后記

本文于2017.06首發(fā)于我的ZH專欄，部分內(nèi)容（特別是第8節(jié)AI相關(guān)的）或許有些過時(shí)，但經(jīng)典理論（整數(shù)規(guī)劃）卻不會。

盡管博士畢業(yè)進(jìn)入了德國的工業(yè)界，從事無人駕駛、計(jì)算機(jī)視覺的研發(fā)，但依舊會與老本行“整數(shù)規(guī)劃”打交道，期待與大家交流！