運籌學自二戰(zhàn)誕生以來，現(xiàn)已被廣泛應(yīng)用于工業(yè)生產(chǎn)領(lǐng)域了，比如交通運輸、供應(yīng)鏈、能源、經(jīng)濟以及生產(chǎn)調(diào)度等。離散優(yōu)化問題（discrete optimization problems）是運籌學中非常重要的一部分，他們通?？梢越３烧麛?shù)優(yōu)化模型進行求解，即通過決定一系列受約束的整數(shù)或者0-1變量，得出模型最優(yōu)解。

有一些組合優(yōu)化問題不是那么的“難”，比如最短路問題，可以在多項式的時間內(nèi)進行求解。然而，對于一些NP-hard問題，就無法在多項式時間內(nèi)求解了。簡而言之，這類問題非常復雜，實際上現(xiàn)在的組合優(yōu)化算法最多只能求解幾百萬個變量和約束的問題而已。

機器學習是一門多領(lǐng)域交叉學科，涉及概率論、統(tǒng)計學、逼近論、凸分析、算法復雜度理論等多門學科?，F(xiàn)在，有很多研究想將學習的方法應(yīng)用與組合優(yōu)化領(lǐng)域，提高傳統(tǒng)優(yōu)化算法的效率。

By the way，大家請原諒我，有些單詞我真不知道咋翻譯，就直接用英文了，所以你們閱讀的時候看見中英混用，絕不是我在裝13，而是有些情景用英文大家理解起來會更方便。

1 動機

在組合優(yōu)化算法中使用機器學習的方法，主要有兩方面：

（1）優(yōu)化算法中某些模塊計算非常消耗時間和資源，可以利用機器學習得出一個近似的值，從而加快算法的速度。

（2）現(xiàn)存的一些優(yōu)化方法效果并不是那么顯著，希望通過學習的方法學習搜索最優(yōu)策略過程中的一些經(jīng)驗，提高當前算法的效果。（算是一種新思路？）

2 介紹

這一節(jié)簡要介紹下關(guān)于組合優(yōu)化和機器學習的一些概念，當然，只是粗略的看一下，詳細內(nèi)容大家還是去參照以往公眾號的文章（指的組合優(yōu)化方面）。因為之前做的一直是運籌優(yōu)化領(lǐng)域，對機器學習一知半解，所以關(guān)于這部分的闡述則是從網(wǎng)上篩選過來的，出處我均已貼到參考那里了。

2.1 組合優(yōu)化

組合優(yōu)化相信大家都很熟悉了，因為公眾號一直在做的就是這方面的內(nèi)容。一個組合優(yōu)化問題呢通常都能被建模成一個帶約束的最小化問題進行求解，即將問題以數(shù)學表達式的形式給出，通過約束變量的范圍，讓變量在可行域內(nèi)作出決策，使得目標值最小的過程。

如果決策變量是線性的，那么該問題可以稱為線性規(guī)劃（Linear programming）；如果決策變量是整數(shù)或者0-1，那么可以稱為整數(shù)規(guī)劃（Integer programming）；而如果決策變量是整數(shù)和線性混合的，那么可以稱為混合整數(shù)規(guī)劃（Mixed-integer programming）?？梢岳胋ranch and bound算法解決Mixed-integer programming問題，目前應(yīng)用的比較多，也有很多成熟的求解器了，比如cplex、lpsolve、國產(chǎn)的solver等等。但是就目前而言，求解器在求解效率上仍存在著問題，難以投入到實際的工業(yè)應(yīng)用中，現(xiàn)在業(yè)界用啟發(fā)式比較多。

2.2 監(jiān)督學習(supervised learning)

監(jiān)督學習(supervised learning)的任務(wù)是學習一個模型，使模型能夠?qū)θ我饨o定的輸入，對其相應(yīng)的輸出做一個好的預測。監(jiān)督學習其實就是根據(jù)已有的數(shù)據(jù)集，知道輸入與輸出的結(jié)果之間的關(guān)系，然后根據(jù)這種關(guān)系訓練得到一個最優(yōu)的模型。

2.3 強化學習(Reinforcement learning)

強化學習（Reinforcement Learning, RL），又稱再勵學習、評價學習或增強學習，是機器學習的范式和方法論之一，用于描述和解決智能體（agent）在與環(huán)境的交互過程中通過學習策略以達成回報最大化或?qū)崿F(xiàn)特定目標的問題。[百度百科]

馬爾可夫決策過程（Markov Decision Processes,MDPs） MDPs 簡單說就是一個智能體（Agent）采取行動（Action）從而改變自己的狀態(tài)（State）獲得獎勵（Reward）與環(huán)境（Environment）發(fā)生交互的循環(huán)過程。

MDP 的策略完全取決于當前狀態(tài)（Only present matters），這也是它馬爾可夫性質(zhì)的體現(xiàn)。

先行動起來，如果方向正確那么就繼續(xù)前行，如果錯了，子曰：過則勿憚改。吸取經(jīng)驗，好好改正，失敗乃成功之母，從頭再來就是?？傊袆樱m先生說：怕什么真理無窮，進一寸有一寸的歡喜。

即想要理解信息，獲得輸入到輸出的映射，就需要從自身的以往經(jīng)驗中去不斷學習來獲取知識，從而不需要大量已標記的確定標簽，只需要一個評價行為好壞的獎懲機制進行反饋，強化學習通過這樣的反饋自己進行“學習”。（當前行為“好”以后就多往這個方向發(fā)展，如果“壞”就盡量避免這樣的行為，即不是直接得到了標簽，而是自己在實際中總結(jié)得到的）

3 近來的研究

第1節(jié)的時候，我們提到了在組合優(yōu)化中使用機器學習的兩種動機，那么現(xiàn)在很多研究也是圍繞著這兩方面進行展開的。

首先說說動機（1），期望使用機器學習來快速得出一個近似值，從而減少優(yōu)化算法中某些模塊的計算負擔，加快算法的速度。比如說在branch and price求解VRP類問題中，其子問題SPPRC的求解就是一個非常耗時的模塊，如果利用機器學習，在column generation的每次迭代中能快速生成一些reduced cost為負的路徑，那整個算法的速度就非?？炝?。不過這個難度應(yīng)該會非常大，希望若干年后能實現(xiàn)吧~

而動機（2）則是嘗試一種新的思路來解決組合優(yōu)化問題吧，讓機器學習算法自己去學習策略，從而應(yīng)用到算法中。比如branch and bound中關(guān)于branch node的選取，選擇的策略能夠極大地影響算法運行的時間，目前常見的有深度優(yōu)先、廣度優(yōu)先等。但這些方法效果遠沒有那么出眾，所以寄希望于新興的機器學習方法，期望能得到一些新的，outstanding的策略。

動機（1）和動機（2）下所使用的機器學習方法也是不同的，在開始介紹之前呢，大家先去回顧下第2節(jié)中介紹強化學習時提到的Markov鏈。假設(shè)environment是算法內(nèi)部當前的狀態(tài)，我們比較關(guān)心的是組合優(yōu)化算法中某個使用了機器學習來做決策的函數(shù)，該函數(shù)在當前給定的所有信息中，返回一個將要被算法執(zhí)行的action，我們暫且叫這樣的一個函數(shù)為policy吧。

那么這樣的policy是怎樣給出相應(yīng)的action呢？所謂機器學習，當然是通過學習！而學習也有很多方式，比如有些人不喜歡聽老師口口相傳，只喜歡不聽地做題，上課也在不停的刷題刷題（小編我）。有些人就上課認認真真聽課，課后重點復習老師講的內(nèi)容。所有的方式，目的都是為了獲得知識，考試考高分。同樣的，在兩種動機下，policy學習的方式也是不一樣的，我們且稱之為learning setting吧。

動機（1）下使用的是demonstration setting，他是一種模仿學習，蹣跚學步大家聽過吧~這種策略呢就是不斷模仿expert做的決策進行學習，也沒有什么reward啥的，反正你怎么做我也怎么做。他是通過一系列的“樣例”進行學習，比如你把TSP問題的輸入和最優(yōu)解打包丟給他，讓他進行學習，當他學有所成時，你隨便輸入一個TSP的數(shù)據(jù)，他馬上（注意是非?？焖俚模┚湍芙o出一個結(jié)果。這個結(jié)果有可能是最優(yōu)的，也有可能是近似最優(yōu)的。當然，下面會舉更詳細的例子進行介紹。如下圖所示，在demonstration setting下，學習的目標是盡可能使得policy的action和expert相近。

動機（2）意在發(fā)現(xiàn)新的策略，policy是使用reinforcement learning通過experience進行學習的。他是通過一種action-reward的方式，訓練policy，使得它不斷向最優(yōu)的方向改進。當然了，這里為了獲得最大的reward，除了使用reinforcement learning algorithms的方法，也可以使用一些經(jīng)典的optimization methods，比如genetic algorithms, direct/local search。

簡單總結(jié)一下，動機（1）中的模仿學習，其實是采用expert提供的一些target進行學習（沒有reward）。而動機（2）中的經(jīng)驗學習，是采用reinforcement learning從reward中不斷修正自己（沒有expert）。在動機（1）中，agent is taught what to do。而在動機（2）中，agent is encouraged to quickly accumulate rewards。

3.1 demonstration setting

這一節(jié)介紹下目前使用demonstration setting的一些研究現(xiàn)狀。（挑幾個有代表性的講講，詳情大家去看paper吧~）

我們知道，在求解線性規(guī)劃時，通過添加cutting plane可以tighten當前的relaxation，從而獲得一個更好的lower bound，暫且將加入cutting plane后lower bound相比原來提升的部分稱之為improvement吧。Baltean-Lugojan et al. (2018) 使用了一個neural network去對求解過程中的improvement進行了一個近似。具體做法大家直接去看文獻吧，畢竟有點專業(yè)。

第二個例子，就是我們之前說過的，使用branch and bound求解mixed integer programming的時候，如果選擇分支的節(jié)點，非常重要。一個有效的策略，能夠大大減少分支樹的size，從而節(jié)省大量的計算時間。目前表現(xiàn)比較好的一個heuristic策略是strong branching (Applegate, Bixby, Chva?tal, & Cook, 2007)，該策略計算眾多候選節(jié)點的linear relaxation，以獲得一個potential lower bound improvement，最終選擇improvement最大那個節(jié)點進行分支。盡管如此，分支的節(jié)點數(shù)目還是太大了。因此，Marcos Alvarez, Louveaux, and Wehenkel (2014, 2017)使用了一個經(jīng)典的監(jiān)督學習模型去近似strong branching的決策。He, Daume III, and Eisner (2014)學習了這樣的一個策略--選擇包含有最優(yōu)解的分支節(jié)點進行分支，該算法是通過整個分支過程不斷收集expert的behaviors來進行學習的。

3.2 experience

開局先談?wù)劥蠹曳浅Ｊ煜さ腡SP問題，在TSP問題中，獲得一個可行解是非常容易的一件事，我們只需要依次從未插入的節(jié)點中選擇一個節(jié)點并將其插入到解中，當所有節(jié)點都插入到解中時，就可以得到一個可行解。在貪心算法中，每次選擇一個距離上次插入節(jié)點最近的節(jié)點，當然我們最直接的做法也是這樣的。但是這樣的效果，并沒有那么的好，特別是在大規(guī)模的問題中。具體可以參考下面這篇推文：

Khalil, Dai, Zhang, Dilkina, and Song (2017a)構(gòu)建了一個貪心的啟發(fā)式框架，其中節(jié)點的選擇用的是graph neural network，一種能通過message passing從而處理任意有限大小graphs的neural network。對于每個節(jié)點的選擇，首先將問題的網(wǎng)絡(luò)圖，以及一些參數(shù)（指明哪些點以及被Visited了）輸入到neural network中，然后獲得每個節(jié)點的action value，使用reinforcement learning對這些action value進行學習，reward的使用的是當前解的一個路徑長度。

結(jié)尾

今天先介紹這么多了。以上內(nèi)容都是小編閱讀論文

Machine learning for combinatorial optimization: A methodological tour d’horizon

所得的，基本上翻譯+自己理解。但是這個paper還沒講完哦，后面還有些許的內(nèi)容，容我下篇推文再介紹啦。急不可耐的小伙伴可以直接去看原paper哦。

參考

監(jiān)督學習(supervised learning)的介紹 https://zhuanlan.zhihu.com/p/99022922

強化學習（Reinforcement Learning）知識整理 https://zhuanlan.zhihu.com/p/25319023

強化學習（Q-Learning，Sarsa） https://blog.csdn.net/qq_39388410/article/details/88795124

Baltean-Lugojan, R., Misener, R., Bonami, P., & Tramontani, A. (2018). Strong Sparse Cut Selection via Trained Neural Nets for Quadratic Semidefinite Outer-Approx- imations. Technical Report. Imperial College, London.

Applegate, D., Bixby, R., Chva?tal, V., & Cook, W. (2007). The Traveling Salesman Prob- lem: A Computational Study. Princeton University Press.

Marcos Alvarez, A., Louveaux, Q., & Wehenkel, L. (2014). A supervised machine learning approach to variable branching in branch-and-bound. Technical Report. Universite? de Lie?ge.

Marcos Alvarez, A., Louveaux, Q., & Wehenkel, L. (2017). A machine learning-based approximation of strong branching. INFORMS journal on computing, 29(1), 185–195.

He, H., Daume III, H., & Eisner, J. M. (2014). Learning to search in branch and bound algorithms. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, & K. Q. Weinberger (Eds.), Advances in neural information processing systems 27(pp. 3293–3301). Curran Associates, Inc.

Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L. (2017a). Learning combinatorial optimization algorithms over graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 30 (pp. 6348–6358). Curran Associates, Inc..