編者按：在和『運(yùn)籌OR帷幄』社區(qū)群友交流的時候，發(fā)現(xiàn)很多小伙伴還沒能很好地區(qū)分算法設(shè)計和數(shù)學(xué)建模在求解一個具體問題時的區(qū)別。例如有人開口就問：“求解VRP問題用什么算法好？”

今天，希望借這個知乎問題，和大家捋一捋倆者的區(qū)別。

學(xué)術(shù)不精，且不那么嚴(yán)謹(jǐn)，還望大神們斧正！

作者?留德華叫獸?美國Clemson應(yīng)用數(shù)學(xué)|運(yùn)籌學(xué)碩士、博士候選人，德國海德堡大學(xué)數(shù)學(xué)|組合優(yōu)化博士，博士研究方向?yàn)殡x散優(yōu)化在計算機(jī)視覺的交叉應(yīng)用。讀博期間于意大利博洛尼亞大學(xué)和法國巴黎綜合理工訪問10個月，意大利IBM Cplex實(shí)習(xí)半年。學(xué)術(shù)不精，轉(zhuǎn)而致力于科普，讀博期間創(chuàng)辦運(yùn)籌OR帷幄（運(yùn)籌學(xué)|數(shù)據(jù)科學(xué)|人工智能社區(qū)）以及DIY飛躍計劃（全球1000+海外碩博留學(xué)咨詢師）倆個知乎機(jī)構(gòu)號|微信公眾號|頭條號|社區(qū)，并邀請學(xué)界|業(yè)界大佬聯(lián)合舉辦了10+知乎 Live。現(xiàn)于德國某汽車集團(tuán)無人駕駛部門機(jī)器學(xué)習(xí)組，擔(dān)任計算機(jī)視覺研發(fā)工程師。

歡迎原鏈接轉(zhuǎn)發(fā)，付費(fèi)轉(zhuǎn)載請前往 @運(yùn)籌OR帷幄?的主頁獲取信息，盜版必究。?

敬請關(guān)注和擴(kuò)散 @運(yùn)籌OR帷幄 B站及同名公眾號，會邀請全球知名學(xué)者陸續(xù)發(fā)布運(yùn)籌學(xué)、人工智能中優(yōu)化理論等相關(guān)干貨、知乎Live及行業(yè)動態(tài)。

作為一個運(yùn)籌學(xué)數(shù)學(xué)規(guī)劃（Math Programming）領(lǐng)域的博士，我研究問題通常的步驟是：

1. 建立數(shù)學(xué)規(guī)劃模型（最好是線性規(guī)劃或線性整數(shù)規(guī)劃）

2. 將模型直接放入求解器（試圖）求得精確解

3. 如果問題規(guī)模比較大，考慮求解其對偶問題或一些大規(guī)模問題的分解技巧優(yōu)化數(shù)學(xué)模型，例如：割平面、列生成、Benders等

4. 設(shè)計針對該問題的啟發(fā)式算法，（作為初始解）加速2

（其中2-4順序不限）

01

—

數(shù)學(xué)規(guī)劃模型的通用解法

該問題屬于數(shù)學(xué)規(guī)劃問題，因此上面這個問題對我來說，1這個步驟已經(jīng)完成了90%，唯一要做的就是將L1范數(shù)|| . || 這個絕對值項(xiàng)線性化。

這就比較巧了，朋友們！我的這篇paper[1]用到的trick可以完美搞定，如下圖：

問題（2）和知乎問題非常類似，目標(biāo)方程的絕對值求和——即向量的L1范數(shù)，除了x在這里是一個整數(shù)變量。

通過引入倆組新的變量以及增加新的約束條件5b和5e，上述問題即可被線性化。

如下圖：

該問題被轉(zhuǎn)化成了線性整數(shù)規(guī)劃問題（請忽略約束5d），而文章開頭的知乎問題可以被轉(zhuǎn)化成線性規(guī)劃問題，然后就可以丟進(jìn)優(yōu)化求解器（如：Cplex或Gurobi）求得精確解了。

當(dāng)然咯，還不要開心地太早！

既然是通用解法，計算速度是無法保證的。

但是，至少可以作為一個Baseline！這也是非常寶貴的！

要不然干嘛花那么大力氣去做通用的優(yōu)化求解器呢？你說是吧？

02

—

“優(yōu)化”模型

“優(yōu)化”這個詞或許用得欠妥當(dāng)，因?yàn)槲乙蚕肽依ā緦⒃瓎栴}轉(zhuǎn)化為對偶問題】等這些技巧，大家心領(lǐng)神會就行。

回到知乎問題，這時候它已經(jīng)是一個帶約束的線性規(guī)劃問題了，我們試圖去“優(yōu)化”它。至于為什么要優(yōu)化，以及為何用下面的方法“優(yōu)化”，我最后再說。

我們用拉格朗日松弛法，把約束條件“挪”到目標(biāo)方程。

這里偷懶一下，直接引用『運(yùn)籌OR帷幄』優(yōu)化版快主編@覃含章 同學(xué)的知乎回答：

好了，變成一個無約束優(yōu)化問題咯！

03

—

算法設(shè)計--具體問題具體分析

到這里我可以揭曉謎底了--為啥要使用拉格朗日松弛法“優(yōu)化”該模型。

因?yàn)楸弧皟?yōu)化”后，這個知乎問題被轉(zhuǎn)化成了一個Lasso問題！

什么是Lasso？

Umm，我還是直接上圖吧：

看不懂不要緊，總之Lasso是一個非常經(jīng)典的問題！

既然是經(jīng)典問題，那么就意味著有無數(shù)研究者針對這一特定問題設(shè)計了無數(shù)專門的算法，這些算法充分考慮了Lasso問題的特性。

因此，到這里，你應(yīng)該知道如何去設(shè)計針對這個問題的算法了？

--百度或谷歌Lasso算法吧，親！

04

—

解題步驟回顧

遇到一個問題，首先是進(jìn)行常規(guī)的數(shù)學(xué)規(guī)劃建模。

因?yàn)椴还茉鯓樱ê媚Ｐ秃?，把它插入?yōu)化求解器，它至少可以給你一個baseline！

完成這一步，你其實(shí)已經(jīng)可以去設(shè)計針對該問題的特定算法（例如我通常會設(shè)計一個貪婪算法）。

但是……

正如本文的例子，如果你建立的數(shù)學(xué)模型，和經(jīng)典的問題模型有幾分神似，那么，就想盡一切辦法把該問題“轉(zhuǎn)化”成為一個經(jīng)典問題，即使他們不完全等價（例如本文的拉格朗日松弛法）。

因?yàn)?，?jīng)典問題被研究了那么多年，存在一整套數(shù)學(xué)理論和高效算法。

等到這個時候，再去設(shè)計算法也不遲哪！

總結(jié)一下：

建模->優(yōu)化模型->設(shè)計算法

因此，『運(yùn)籌OR帷幄』社群的童鞋們，不要拋出一個問題直接問算法了！

當(dāng)然咯，凡事必有例外--近似算法（理論計算機(jī)）。

談到它——拋出問題，就可以直接談算法了！