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

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

? ? ? 本文提綱

• 整數(shù)規(guī)劃回顧?

• 算法復(fù)雜度?

• 精確解--分支定界法

• 分支定界法的“收斂”?

• 啟發(fā)式/近似算法

• 運籌學(xué)的“引擎”--優(yōu)化求解器?

• 整數(shù)規(guī)劃模型的意義

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

首先，對運籌學(xué)（Operations Research, O.R.）和線性規(guī)劃(Linear Programming)還比較陌生的童鞋，請戳本專欄的其中倆篇：

運籌學(xué)--一門建模、優(yōu)化、決策的科學(xué)（知乎專欄）：http://t.cn/ROBybx3

OR | 離散/整數(shù)/組合/非凸優(yōu)化概述及其在AI的應(yīng)用案例 【運籌帷幄】

/? 1? /

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

整數(shù)規(guī)劃，或者離散優(yōu)化（Discrete Optimization），是指數(shù)學(xué)規(guī)劃（Math Programming）問題中自變量存在整數(shù)的一類問題。上面這個數(shù)學(xué)規(guī)劃問題，便是一個混合整數(shù)線性規(guī)劃問題。

首先目標(biāo)方程和約束方程都是線性的，其次自變量既有連續(xù)變量（x1、x3），又有整數(shù)變量（x2）。

與線性規(guī)劃連續(xù)的可行域（可行解組成的集合）不同，整數(shù)規(guī)劃的可行域是離散的。

如上圖，一條藍線代表一個線性不等式，但是這里x,y自變量被約束成整數(shù)變量，因此可行域變成了紅線區(qū)域內(nèi)的9個離散的黑點（線性規(guī)劃的可行域是藍色線段內(nèi)部所有的區(qū)域）。

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

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

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

整數(shù)規(guī)劃由于可行域是極度非凸（Highly Nonconvex）的，因此也可以看作是一類特殊的非凸優(yōu)化（Nonconvex Optimization）問題。

/? 2? /

算法復(fù)雜度（Algorithm complexity）

一般情況下，求解整數(shù)規(guī)劃的精確解（全局最優(yōu)）是NP難的，簡單地說，也就是只存在指數(shù)級算法復(fù)雜度（Exponential Time Solvable）。

怎么來理解指數(shù)級復(fù)雜度呢？假設(shè)這里的整數(shù)變量是{0,1}變量，那么我們可以簡單地理解為算法復(fù)雜度至少是O(2^n)（需要解2^n個線性規(guī)劃問題，其中n是整數(shù)變量的個數(shù)）。其中線性規(guī)劃被認為是可以較為高效求解的，其復(fù)雜度是多項式時間的（O(n^k)，其中k是常數(shù)，注意這里n在底數(shù)上）。

也就是說，每增加一個整數(shù)變量，求解其精確解的運算速度最壞情況下就要增加一倍！例如求解n=100的整數(shù)規(guī)劃問題需要1小時，那么求解n=101的規(guī)?？赡軙枰?小時，n=102需要4小時，n=105需要32小時......

這就是指數(shù)爆炸！

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

/? 3? /

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

整數(shù)規(guī)劃的精確算法框架中最核心的便是B&B，以及增加分支定界效率的各種技巧，例如割平面方法（Cutting Planes Method）等。

假設(shè)是求解目標(biāo)函數(shù)最小化的問題，它的核心思想便是把這個NP難的問題分解成求解一個個的線性規(guī)劃（LP）問題（每個LP問題是多項式時間可解），并且在求解的過程中實時追蹤原問題的上界（最優(yōu)可行解）和下界（最優(yōu)線性松弛解）。

我們先看個簡單的例子以便理解：

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

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

x1- x3 +x4 >=1

x1..x4 is {0,1}, x5 >=0

假設(shè)有4個{0,1}變量，x1..x4，以及1個連續(xù)變量x5。圖中最頂上的點叫Root Node，通過把整數(shù)變量x1..x4線性松弛(Linear Relaxation)，例如這里松弛成[0,1]區(qū)間內(nèi)的連續(xù)變量，然后求解相應(yīng)的松弛后的線性規(guī)劃問題(Linear Relaxation Problem)。

求解該LRP問題所得的解（通常對于原問題來說是不可行的，因為x1..x4可能是小數(shù)），這個解便是該問題的第一個下界（Lower Bound）。

為什么是下界呢？

對于一個最小化問題，因為通過把{0,1}變量松弛成[0,1]，等于增加了可行解的個數(shù)（可行域的范圍），這樣該最小化問題就有可能得到比原問題更好（小）的解，因此松弛后的問題求得的解是原問題的下界（Lower Bound）。

事實上，圖中每一個點，都是一個松弛后的線性規(guī)劃（LRP）問題的解。由于被松弛成了[0,1]間的連續(xù)變量，因此原問題中應(yīng)屬于{0,1}的自變量，例如x1，通過求解線性規(guī)劃，得到的解可能是0.4，顯然不滿足原問題的條件。

這時候，我們就需要做分支（Branch）,例如對Root Node做左右倆個分支，左邊的分支可以是x1=0，右邊的分支是x1=1。

分支的意思，可以理解為在原本Root Node的LRP基礎(chǔ)上，加上一個x=0或1的約束條件。這樣，通過加上這個約束條件，再解該問題，x1就必定等于0或1，x1也便是可行的。當(dāng)然剩余的自變量x2..x4，由于沒有類似的整數(shù)約束，還有可能是小數(shù)，因此我們還需要更多的分支。

上圖4個{0,1}變量，最壞的情況需要2^4次分支，也就是求解16個線性規(guī)劃問題。

圖中紅色的部分是什么意思呢？

這就需要先引進上界（Upper Bound、最優(yōu)可行解）的概念。當(dāng)分支一個個進行下去時，到某一個Node（點），松弛后線性規(guī)劃問題求得的解可能是原問題的可行解，也就是說，x1..x4都是{0,1}。這個時候，我們便找到了一個原問題的可行解，它的目標(biāo)函數(shù)例如4，我們把它放入Upper Bound里。

在接下來的分支里，如果求解一個Node的LRP的解是大于上界4的，例如4.5。那么這個時候，雖然我們還沒找到這個點其下分支可能的可行解，但是如果繼續(xù)對這個點進行分支，由于分支代表增加更多的約束，減少了可行解的個數(shù)，以后求得的解只會比4.5來得更差（大）。

因此，從優(yōu)化的角度，我們不可能從這個點以后的分支中找到比目前上界4更優(yōu)的解，因此沒有必要對4.5這個點繼續(xù)再做分支，可以直接刪（Prune）掉，也就是圖中紅色的區(qū)域。

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

Prune情況一：下界大于上界

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

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

/? 4? /

分支定界法的“收斂（Convergence）”

這里的收斂不是分析意義上的收斂，而是算法、數(shù)值意義上的。上面我們提到分支定界法存在上界和下界，并且隨著一個個Node LRP問題的求解，不斷進行著更新。每當(dāng)求得一個原問題的可行解（混合整數(shù)解），如果這個解的目標(biāo)函數(shù)小于當(dāng)前的最優(yōu)可行解，那么就對上界進行更新。下界更新方式類似。

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

然而比起絕對差值更為流行的，是相對差值，也即分支定界法的Gap。

它的計算方法：（上界-下界）/上界。

通常我們設(shè)置Gap < 0.1%，就可把當(dāng)前的最優(yōu)可行解（上界）理解為該問題的全局最優(yōu)解了，分支定界法隨即終止（Terminate）。

/? 5? /

啟發(fā)式/近似算法（Heuristic/Approximation Algorithms）

作為研究世界上最難問題的學(xué)者，想出了解決整數(shù)規(guī)劃問題的各種其他途徑，例如近似算法（Approximation Algorithms），啟發(fā)式算法（Heuristic Algorithms），遺傳算法（Generic Algorithm），Evolutionary Algorithms等等。

它們雖然不能求得整數(shù)規(guī)劃的最優(yōu)解，但是卻能在短時間（通常多項式時間）內(nèi)給出一個較好的可行解。

啟發(fā)式算法，通常采用貪心算法（Greedy Algorithm），所得的解通常只是局部最優(yōu)解，并且完全沒有概念這個解到底有多“好”。

近似算法，與啟發(fā)式算法不一樣，算法往往通過非常巧妙的設(shè)計，計算所得的解可以用嚴格的數(shù)學(xué)證明是“比較好”的，即所謂的近似率（Approximation Ratio）,R。

也就是說，近似算法所得的解，可以被證明是全局最優(yōu)解的R倍之內(nèi)。這樣該算法所得的解被認為是有保證的。

/? 6? /

運籌學(xué)的“引擎”--優(yōu)化求解器（Optimization Solver）

分支定界法雖然思想簡單，但是實現(xiàn)起來卻比想象的復(fù)雜——如何管理各個分支的存儲，分支的先后順序，以及一些提高分支定界法效率的算法，等等。

市面上知名的混合整數(shù)規(guī)劃求解器：IBM Cplex，Gurobi，F(xiàn)ICO Xpress，SCIP。

前三個都是商業(yè)軟件，閉源，第四個是開源的由柏林ZIB研究機構(gòu)開發(fā)并維護的，但是商業(yè)用途需要購買版權(quán)。這四個如果用作教學(xué)、科研，都是免費下載和使用的。

作為運籌學(xué)的引擎，優(yōu)化求解器意義重大，因為所有混合整數(shù)規(guī)劃模型的求解，都需要靠它。

由于是NP難問題，求解的效率至關(guān)重要，不同求解器的求解速度也千差萬別。

例如同一個問題，用Cplex求解只需1分鐘，用SCIP可能就需要1小時，你自己寫B(tài)&B算法的程序，可能需要1天！

而工業(yè)界非常多的問題可以被建模成整數(shù)規(guī)劃問題，例如物流、路徑規(guī)劃、航班調(diào)度等等。需要得到其精確解，便需要使用優(yōu)化求解器。但是這些求解器都掌握在以上國外公司或機構(gòu)，中國還沒有自己的、成熟可以商用的整數(shù)規(guī)劃求解器！

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

好消息是，近幾年中國好幾家公司都在投身于開發(fā)優(yōu)化求解器，其中最令人矚目的杉數(shù)科技的COPT求解器，在線性優(yōu)化方面多次刷榜世界紀錄。其首席科學(xué)家顧問Yinyu Ye（https://stanford.edu/~yyye/）教授是華人運籌學(xué)界泰斗的人物。

報道 | 刷新世界紀錄，杉數(shù)COPT優(yōu)化求解器套件繼續(xù)全面提升

其實不光杉數(shù)，包括阿里、華為這樣的商業(yè)巨頭，還有中科院CMIP混合整數(shù)規(guī)劃求解器團隊，都在研發(fā)國產(chǎn)求解器上投入巨大精力。

報道 | 阿里達摩院求解器MindOpt在國際權(quán)威測評中再獲榜單冠軍

衷心希望中國早日有自己的高質(zhì)量優(yōu)化求解器，也希望有志青年可以加入到這個行列。

/? 7? /

整數(shù)規(guī)劃模型的意義

可能很多人會問，既然整數(shù)規(guī)劃模型是NP難的，既然已經(jīng)有了高效的啟發(fā)式算法、近似算法，那么為何還要執(zhí)念于精確算法呢？

同一個問題，雖然可以用啟發(fā)式算法或近似算法，但是求得的解要么完全沒有保證，要么只有R這個近似倍數(shù)的保證。

但是，只要把該問題數(shù)學(xué)建模成整數(shù)規(guī)劃模型，啟發(fā)式或近似算法求得的解，都可以直接作為優(yōu)化求解器的初始解（上界）。

這時候，優(yōu)化求解器只需求解Root Node（LRP），便可以得到下界，于是你幾乎不費力（多項式時間）便可得到一個Gap。這個Gap，便可以作為這個解的某種保證（例如，Gap是10%，你便知道這個解離最優(yōu)解“不遠了”）。

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

從這個意義上講，深度學(xué)習(xí)這個極度非凸的優(yōu)化問題，其反向傳播法也可以理解成一個類似于隨機梯度下降（SGD）的啟發(fā)式算法，它只找到一個沒有任何保證的局部最優(yōu)解（貌似離全局最優(yōu)解“不遠”）。

其實這個優(yōu)化問題也可以被建模成整數(shù)規(guī)劃模型，優(yōu)化求解器能給出深度學(xué)習(xí)找出局部最優(yōu)解的Gap，以及可能再次優(yōu)化這個解。（然而，實際情況是，深度學(xué)習(xí)問題的規(guī)模往往遠大于整數(shù)規(guī)劃模型的“極限”）

▎篇幅限制，5-7節(jié)沒有深入探究。我將在下一篇專欄著重探討整數(shù)規(guī)劃的加速，近似算法以及啟發(fā)式算法。另外，優(yōu)化求解器也不僅限于整數(shù)規(guī)劃，還有凸優(yōu)化、非凸優(yōu)化、非線性規(guī)劃等等，敬請期待。

注：知識點推薦使用書本系統(tǒng)的學(xué)習(xí)，本篇旨在為大家做一丁點的梳理和總結(jié)工作。

后記

本文于2017.07首發(fā)于我的知乎專欄，部分內(nèi)容（特別是第6節(jié)求解器相關(guān)）做了更新。

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

—— 完 ——