【學界】運籌學數學規劃|離散優化求解器大搜羅

來自專欄『運籌OR帷幄』大數據人工智慧時代的運籌學50 人贊了文章

本文作者@留德華叫獸 系美國克萊姆森大學運籌學碩士，Ph.D. Candidate，歐盟瑪麗居里學者，德國海德堡大學組合優化、計算機視覺博士，期間前往義大利IBM Cplex實習半年，巴黎綜合理工訪問一季。

歡迎原鏈接轉發，轉載請前往 @留德華叫獸的主頁獲取信息，盜版必究。

會邀請全球知名學者陸續發布運籌學、供應鏈管理、人工智慧中優化理論、知乎Live及相關行業動態：『運籌OR帷幄』大數據人工智慧時代的運籌學--知乎專欄

一、前言

這篇文章筆者一年前就已開始構思，苦於時間有限而遲遲沒有下筆。今天終於鼓足勇氣，動筆時間晚上11點，今天就算通宵也要把它寫完～

言歸正傳，由於筆者背景偏重於整數規劃，因此本文大量篇幅將介紹整數規劃求解器。

【學界】離散/整數/組合/非凸優化概述及其在AI的應用

當我們費勁千辛萬苦對一個實際問題用整數規劃建模以後，寫成如下優化問題：

我們知道，建模完成後要求解具體的實例，下一步便是設計相應演算法。

而求解整數規劃模型的基本演算法便是分支定界法：

留德華叫獸：【學界】混合整數規劃/離散優化的精確演算法--分支定界法及優化求解器

那麼我們是否要親自手擼一遍分支定界法呢？

幾十年前，當市面上這些求解器還不存在的時候，很不幸的告訴你：當然需要！

這是我與歐洲運籌協會主席、巴塞羅那理工Elena Fernandez教授親切會談後她給我的回答。

當時作為一名運籌學研究精確演算法的博士生畢業難度（代碼能力）可想而知。

而今，正因為有了優化求解器的存在，我們只需將以上整數規劃模型的係數矩陣輸入到優化求解器中，它就能夠給我們快速求出最優解或可行解（除了分支定界法還集成了各種花式啟發式和割平面演算法）！

因此，運籌學博士生的畢業難度大大降低！

整數規劃求解器是什麼？

大家可以把它理解為一個專門求解整數規劃模型的演算法包，你可以用任何編程語言（C/C++、Java、Python）去調用這個包里的方程，只要你把你要求解的整數規劃模型目標方程和係數矩陣輸入進去（告訴它你要求解的具體問題），它就會給你求解出結果。

怎麼樣，是不是很神奇？

廢話不多說，今天我們來梳理一遍市面上流行的整數規劃求解器！

二、商業整數規劃求解器

1. IBM ILOG Cplex

沒錯，就是筆者在義大利Blogna「實習」半年所在的求解器公司

網址：IBM ILOG CPLEX Optimization Studio

支持模型：混合整數（平方）規劃、Constraint programming

支持語言：C/C++、Java、Python、Matlab等

特點：支持Benders分解模塊（僅此一家）、速度Top2

當前版本：12.8

2. Gurobi

網址：The State-of-the-Art Mathematical Programming Solver

支持模型：混合整數（平方）規劃、Constraint programming

支持語言：C/C++、Java、R、Python、Matlab等

特點：速度Top1、價格最高

當前版本：8.0

3. FICO Xpress

網址：FICO? Xpress Optimization | FICO?

支持模型：混合整數（非線性）規劃、Constraint programming

特點：速度Top3，支持魯棒優化

當前版本：8.5

4. MOSEK

網址：The State-of-the-Art Mathematical Programming Solver

支持模型：混合整數（平方）規劃、Second-order cone programming、Semidefinite programming、General convex nonlinear

支持語言：C/C++、Java、R、Python、Matlab等

特點：解SOCOP、SDP更快

當前版本：8.1

價格：

因為是商業軟體，意味著他們是收費的

以下這份價格列錶轉自高級建模語言AMPL的官網：

MOSEK售價為1950刀起

從價格可以看出，Gurobi是目前的NO.1（一個小插曲，或許是因為SCIP創始人Tobias Achterberg從Cplex跳槽至Gurobi以後的事）

好在學生|高校|科研用途都是免費的，只需學校郵箱即可免費下載並使用！

三、開源整數規劃求解器

1. SCIP

網址：SCIP

開發地：德國柏林ZIB研究中心（該中心畢業的博士就職於二中各大求解器公司，share著辦公室並一起交流，得益於德國的一個政府項目）

支持：混合整數（非線性）規劃、Constraint integer programming

支持語言：C/C++、Java、Python、Matlab等

特點：支持Branch&Price（僅此一家）

當前版本：6.0

2. GLPK、LP_Solve

網址：lp_solve reference guide、GLPK

摘抄一段Gurobi官網對這倆個開源求解器的介紹：

3. COIN-OR旗下的CBC和SYMPHONY

網址：COIN-OR Branch-and-Cut MIP Solver、SYMPHONY

這裡還是重點介紹下COIN-OR這個組織吧

它成立於17th International Symposium on Mathematical Programming (ISMP) conference in Atlanta in the summer of 2000，是一個公益組織，維護著市面上幾乎所有的開源優化求解器，並且使得它們之間的交互變得可能。

它的網址：The COIN-OR Foundation

4. 華人求解器

開源求解期

• 中科院的CMIP
• 上海財大|杉數科技主導的Leaves優化求解器

【資訊】中科院CMIP混合整數規劃求解器正式發布

商業求解器

• 杉數科技的Cardinal

【資訊】專訪葛冬冬：我們做華人該有的求解器，BAT和國內科研單位做不了

四、求解器大PK

市面上琳琅滿目的求解器，到底該用哪個好呢？

這時候就需要Public Dataset和Benchmark給你一些參考了

這裡我僅貼出幾個對比的案例：

五、其他優化求解器

以上重點介紹了數學規劃中整數規劃的求解器

熟悉運籌學的同學們知道，數學規劃除了整數規劃，還有凸優化、非凸優化、半正定規劃、錐規劃等等。

什麼？對以上術語一無所知？請點擊：

【學界】人工智慧的「引擎」--運籌學，一門建模、優化、決策的科學

Again，COIN-OR 上面羅列著幾乎所有的開源優化求解器

這裡我就簡單地介紹其中一個--Couenne

為啥？

因為Couenne的開發者，是筆者在Clemson讀博期間的導師Pietro Belotti博士（後跳槽至FICO Xpress）。

Couenne (Convex Over and Under ENvelopes for Nonlinear Estimation) is a branch&bound algorithm to solve Mixed-Integer Nonlinear Programming (MINLP) problems of the form:

六、高級建模語言

GAMS、AMPL、JuMP、Mosel、Glop

這裡僅作簡述

他們又是做什麼的？

作為一種高級建模語言，首先可以把一個數學規劃問題更簡單地編程

其次，它可以調用以上任意一種優化求解器（如果兼容，Mosel只能調用Xpress）

這樣，你只需寫一遍code，便可比較多種不同的求解器，然後取結果最好的那個。

P.S.：其實很多軟體，例如Matlab甚至Excel都自帶了優化模塊，可以解線性規劃和整數規劃問題。

由於他們不是專門做數學規劃的，因此只能說可以用，關於效率和速度，和專門做這個的求解器，是沒有對比價值的。

七、展望

運籌學與國民經濟、企業供應鏈、能源交通等優化息息相關，這些實際問題都可以被建模成為運籌學模型。

而優化求解器是數學規劃建模後求解這些實際問題的核心，這個核心長期被國外軟體公司所壟斷（黑盒子），華人在此領域在2017年以前幾乎是空白。

進入運籌學領域7年多以來，結識了全球很多華人運籌學者。一大感覺便是，研究啟發式、進化演算法、元啟發演算法的華人學者佔了多數，而研發求解器所必須的精確演算法華人學者卻屈指可數。

留德華叫獸：【學界】整數規劃精確演算法/近似演算法/(元)啟發演算法/神經網路反向傳播等演算法的區別與關聯

CMIP和Leaves的出現打破了這一僵局。

衷心希望它們早日能與世界一流的求解器匹敵，為國築器！

P.S.：熬夜寫到凌晨倆點，總算完成了拖了一年的任務，希望這個總結對大家有幫助。

錯誤和疏漏在所難免，懇請大家留言指正。

關注文末公眾號後台回復關鍵詞：「學界」，查看「求解器」文件夾，即可免費獲取 IBM Cplex 12.8版本以及Gurobi 8.0版本benchmark ppt，如果覺得有用， 請勿吝嗇你的留言和贊哦！~

如果你是運籌學|人工智慧碩博或在讀，請在下圖公眾號後台留言：「加微信群」。系統會進一步提示，邀請您進全球運籌或AI學者群（群內學界、業界大佬雲集）。

可以在本公眾號後台回復關鍵詞：「學界」獲取大量由我平台編輯精心整理的學習資料，如果覺得有用， 請勿吝嗇你的留言和贊哦！~