轉載自
https://mp.weixin.qq.com/s/rfdQrgjw4_QOpMyzVqRW0w
國內外優(yōu)化求解器研究現狀1.優(yōu)化求解器 1.1.CPLEX
IBM ILOG CPLEX Optimization Studio（CPLEX）是一個優(yōu)化軟件包。2004年robi，CPLEX的工作獲得了首屆INFORMS影響力獎。CPLEX Optimizer以使用C編程語言實現的單純形方法而命名，盡管今天它還支持其他類型的數學優(yōu)化并提供除C之外的接口。它最初由Robert E.Bixby開發(fā)，并于1988年由CPLEX商業(yè)出售，隨后ILOG在2009年1月被IBM收購。
專門用于求解大規(guī)模的線性規(guī)劃（LP）、二次規(guī)劃（QP）、帶約束的二次規(guī)劃（QCQP）、二階錐規(guī)劃（SOCP）等四類基本問題，以及相應的混合整數規(guī)劃（MIP）問題。
CPLEX Optimizer具有一個稱為Concert的建模層，該層提供了與C++、C＃和Java語言的接口，有一個基于C接口的Python語言接口。此外，還提供了Microsoft Excel和MATLAB的連接器。最后，提供了一個獨立的Interactive Optimizer可執(zhí)行文件，用于調試和其他目的。
1.2.GUROBI
Gurobi是由美國 Gurobi Optimization 公司開發(fā)新一代大規(guī)模優(yōu)化器。Gurobi成立于2008年，以其創(chuàng)始人命名robi：Zonghao Gu、Edward Rothberg和Robert Bixby。Bixby還是CPLEX的創(chuàng)始人，而Rothberg和Gu領導CPLEX開發(fā)團隊近十年。
Gurobi 是全局優(yōu)化器，支持的模型類型包括：
(1) 連續(xù)和混合整數線性問題
(2) 凸目標或約束連續(xù)和混合整數二次問題
(3) 非凸目標或約束連續(xù)和混合整數二次問題
(4) 含有對數、指數、三角函數、高階多項式目標或約束，以及任何形式的分段約束的非線性問題
(5) 含有絕對值、最大值、最小值、邏輯與或非目標或約束的非線性問題
Gurobi Optimizer支持多種編程和建模語言，包括：
(1) C ++、Java、.NET和Python的面向對象接口
(2) 適用于C、MATLAB和R的面向矩陣接口
(3) 可以鏈接到標準建模語言AIMMS、AMPL、GAMS和MPL
(4) 通過其分析求解器和求解器SDK產品鏈接到Excel
Gurobi Optimizer還包括許多功能來支持優(yōu)化模型的構建，其中包括：
(1) 可以靈活確定多個目標的優(yōu)先級
(2) 諸如MIN / MAX、ABS、AND / OR之類的常規(guī)約束以及指標約束
(3) 具有凸、分段線性目標函數的模型用于描述某些非線性問題
(4) 任意分段線性目標函數
(5) 分布式調參，以加快參數設置的探索速度，加快求解時間
Gurobi Optimizer還可以部署在云上，以及用于服務器-客戶端模式。
1.3.Xpress
Xpress優(yōu)化器是商業(yè)優(yōu)化求解器,主要用于求解線性規(guī)劃（LP），混合整數線性規(guī)劃（MILP），凸二次規(guī)劃（QP），凸二次約束二次規(guī)劃（QCQP），二階錐規(guī)劃（SOCP）和它們的混合整數對應物。Xpress 包括通用非線性求解器 Xpress NonLinear，逐次線性規(guī)劃算法（SLP，一階方法）和Artelys Knitro（二階方法）。
Xpress 最初由 Dash Optimization 開發(fā)，并于 2008 年被FICO收購。其最初的作者是 Bob Daniel 和 Robert Ashford。Xpress 的第一個版本只能解決 LP；1986 年添加了對 MIP 的支持。Xpress 于 1983 年發(fā)布，是第一個在PC上運行的商業(yè)LP和MIP求解器。1992年，發(fā)布了并行計算的Xpress版本，五年后擴展到分布式計算。Xpress 是第一個通過在 2010 年引入 64 位索引而跨越十億決策變量閾值的 MIP 求解器。自 2014 年以來，Xpress 首次實現了并行對偶單純形方法的商業(yè)實現。
線性和二次規(guī)劃可以通過原始單純形法、對偶單純形法或勢壘內點法求解。所有混合整數規(guī)劃變體都通過分支定界法和切割平面法的組合來解決。不可行問題可以通過IIS（不可約不可行子集）方法進行分析。Xpress 提供了一個內置調諧器，用于自動調整控制設置。Xpress 包括其建模語言 Xpress Mosel和集成開發(fā)環(huán)境 Xpress Workbench。Mosel 包含分布式計算功能，可并行解決優(yōu)化問題的多個場景。輸入數據的不確定性可以通過穩(wěn)健的優(yōu)化方法來處理。
Xpress 有一個稱為 BCL（構建器組件庫）的建模模塊，它與C、C++、Java編程語言和.NET 框架接口。獨立于 BCL，有Python和MATLAB接口。在 Mosel 旁邊，Xpress 連接到其他標準建模語言，例如AIMMS、AMPL和GAMS。
FICO Xpress Executor使用SOAP或REST接口執(zhí)行和部署 Mosel 模型。它可以從外部應用程序或從FICO 決策管理平臺使用。
1.4.MOSEK
MOSEK是由丹麥MOSEK ApS公司開發(fā)的一款數學優(yōu)化求解器，也是公認的求解二次規(guī)劃、二階錐規(guī)劃和半正定規(guī)劃問題最快的求解器之一，廣泛應用于金融、保險、能源等領域。杉數科技是MOSEK在中國大陸唯一官方授權銷售商，承擔中國市場的銷售和售后服務工作。
MOSEK可以解的數學優(yōu)化問題非常寬泛（如下表格所示），其中最擅長求解的是二次規(guī)劃、二階錐和半正定規(guī)劃問題，在金融、保險、能源等領域均有應用。最典型的是金融領域的資產配置問題，以優(yōu)化馬科維茨模型投資組合為例，本質上，這是一個權衡收益和風險、構建最優(yōu)投資組合的優(yōu)化問題，MOSEK求解此類問題快速且穩(wěn)定。
MOSEK求解問題類型與求解算法
在第 9 版中，Mosek在其求解器中引入了對指數和冪錐的支持。它到C、C#、Java、MATLAB、Python和R語言的接口。此外，Mosek 可以與流行的 MATLAB 包CVX和YALMIP 一起使用。
總體上講，MOSEK有以下技術優(yōu)勢：
提供優(yōu)化服務器用于遠程優(yōu)化。
充分利用多核處理器硬件特點進行并行計算；
可求解的問題規(guī)模僅受限制于計算機內存容量；
領先世界的內點法實現，用于求解線性、二階錐和二次規(guī)劃問題；
提供基于矩陣和Fusion的編程接口，包括C、C++、Python、Java、C#、MATLAB和R；
支持多種建模環(huán)境，包括AMPL、GAMS和CVX等商業(yè)工具，CVXPY和JuMP等開源工具；
支持多種操作系統，包括Windows、Linux和MacOS；
1.5.SAS
SAS是由SAS Institute開發(fā)的一種統計軟件套件，用于數據管理、高級分析、多元分析、商業(yè)智能、刑事調查和預測性分析。SAS是一個軟件套件，可以挖掘、更改、管理和檢索來自各種來源的數據，并對其進行統計分析。SAS為非技術用戶提供了圖形化的點擊式用戶界面，并通過SAS語言提供了更高級的選項。
1.6.SCIP
SCIP是一個混合整數規(guī)劃求解器和一個用于分支定界以及分支定價的框架，主要由柏林楚澤研究所開發(fā)。與大多數商業(yè)求解器不同，SCIP 為用戶提供了對求解過程的低級控制和信息。作為獨立求解器運行，它是用于混合整數程序的最快的非商業(yè)求解器之一。
SCIP是作為C語言可調用庫實現的。對于用戶插件，提供了C++封裝類。用于LP松弛的求解器不是SCIP的本地組件，而是提供一個開放的LP接口。目前支持的LP求解器有CLP、CPLEX、MOSEK、SoPlex和Xpress。SCIP可以在Linux、Mac、Sun和Windows操作系統上運行。
SCIP的設計是基于約束的概念。它支持大約20種約束類型，用于混合整數線性編程、混合整數非線性編程、混合整數全二次編程和偽布爾優(yōu)化。它還可以解決斯坦納樹（Steiner Trees）和多目標優(yōu)化問題。
1.7.CLP
COIN-OR LP (CLP)是 COIN-OR 項目下的 LP 問題求解器,是一個用C++編寫的開源線性規(guī)劃求解器。CLP包括原始和對偶單純形法求解器，對偶和原始算法都可以使用用戶提供的矩陣存儲方法（除了默認的稀疏矩陣外，已經支持0-1和網絡矩陣）。
它是在通用公共許可證下發(fā)布的，因此可以在沒有GNU 通用公共許可證限制的情況下用于專有軟件。盡管可以構建獨立的可執(zhí)行版本，但COIN-OR主要用作可調用庫。它被設計為與任何商業(yè)求解器一樣可靠，但速度要慢幾倍，并且能夠解決非常大的問題。
COIN-OR旨在解決線性規(guī)劃問題，它的主要算法是單純形算法。
1.8.BARON
BARON(Branch And Reduce Optimization Navigator)是一個用于解決非凸優(yōu)化問題到全局最優(yōu)的計算系統。該軟件可以解決純連續(xù)、純整數和混合整數非線性問題。BARON 可在各種平臺上的AIMMS、AMPL和GAMS 建模語言下使用。
BARON算法和軟件的開發(fā)已獲得 2004 年 INFORMS 計算協會獎和 2006 年 Beale-Orchard-Hays 獎的認可，以表彰其在數學優(yōu)化協會的計算數學編程方面的卓越表現。
1.9.COPT
杉數求解器COPT(Cardinal Optimizer)，是杉數自主研發(fā)的針對大規(guī)模優(yōu)化問題的高效數學規(guī)劃求解器套件,也是支撐杉數端到端供應鏈平臺的核心組件,是目前中國唯一一個同時具備大規(guī)模線性規(guī)劃(單純形法和內點法)和混合整數規(guī)劃問題求解能力的綜合性數學規(guī)劃求解器，為企業(yè)應對高性能求解的需求提供了更多選擇。廣泛應用于軍事、航空、航天、交通、能源等領域。
主要求解線性規(guī)劃、混合整數規(guī)劃和二階錐規(guī)劃問題。支持所有主流操作系統Windows、MacOS、Linux（包括Arm64平臺）。支持所有主流編程接口C、C++、C#、Python、Java、AMPL、GAMS、Pyomo、PuLP等。
1.10.MindOpt
MindOpt是阿里達摩院決策智能實驗室自主研發(fā)的數學規(guī)劃求解器套件。通過針對大規(guī)模線性規(guī)劃的快速穩(wěn)定求解，為客戶提供從數據到決策的全鏈路建模和求解能力。
MindOpt求解器可以快速求解大規(guī)模線性規(guī)劃問題，目前支持命令行和C、C++、Python、Java的API調用，可在Windows，MacOS和Linux系統下使用。
1.11.OPTV
9 月 23 日召開的華為全聯接 2021 上，華為云發(fā)布了「天籌」AI 求解器(OPTV)。天籌(OptVerse)AI求解器將運籌學和AI相結合，突破業(yè)界運籌優(yōu)化極限，針對線性和整數模型尋找最優(yōu)解，以通用形式描述問題，高效計算最優(yōu)方案，助力企業(yè)量化決策和精細化運營，提升資源利用率和運轉效率，增強決策水平和競爭力。
小到快遞員路線選擇、商鋪選址，大到工廠排程、物流路徑規(guī)劃和金融風控等問題，都可以建成數學規(guī)劃模型，用天籌(OptVerse)AI求解器進行求解。利用運籌優(yōu)化算法和決策模型求解方法，將業(yè)務問題轉化為數學規(guī)劃模型，適用在多種復雜約束條件限制（如人力、時效、容量等約束限制）和海量數據的基礎上獲取全局最優(yōu)方案（如成本最低、時間最短）的業(yè)務場景，助力業(yè)務實現從數據到決策的閉環(huán)。
天籌(OptVerse)AI求解器已成功支撐華為供應能力及冗余分析等13個場景的模擬應用，計劃預案周期從周縮短到天，保障了高效的連續(xù)性作戰(zhàn)。
支持求解混合整數線性規(guī)劃問題（MIP）和線性規(guī)劃問題（LP）
AI建模，易用高效，大幅度提升建模效率，讓客戶聚焦核心業(yè)務問題和訴求。
AI賦能求解，基于歷史數據和問題特征自適應選擇最優(yōu)參數，不斷挖掘求解器自身潛力，適應客戶場景和問題特點。
支持基于拓撲感知的分布式并行加速，充分利用華為云分布式并行能力，給客戶帶來極致性能體驗。
1.12.CMIP
著名陳省身數學獎獲得者、馮康科學計算獎獲得者、中國科學院數學與系統科學院戴彧虹研究員帶領CMIP團隊從2015年開始，歷經30個月，終于自主研發(fā)了我國第一個具有國際水平的整數規(guī)劃求解器CMIP，并于2018年3月確定版本為CMIP 1.0版本。
CMIP代碼總量已經超過五萬行，涵蓋國際現有求解器預處理、啟發(fā)式、割平面、分支、節(jié)點選擇、區(qū)域傳播等各種功能模塊，并已經較好地具備了求解大規(guī)模整數規(guī)劃的能力。
2.求解器對比
求解器
國別、性質
提供免費學術版
兼容的編程語言
解決問題
備注
CPLEX（IBM）
美國商業(yè)
是
C, C++, Java, C#, Python
線性，整數為主
IBM CPLEX Optimization Studio 是一套優(yōu)化引擎（用于數學編程的 CPLEX 和用于約束編程的 CP Optimizer）、建模語言 (OPL) 和集成開發(fā)環(huán)境。進入中國早，積累用戶多，在衰退。
GUROBI,獨立
美國商業(yè)
是
C++, Java, Python, .Net, Matlab, R
綜合
各項指標前列，Gurobi 以卓越的性能躋身大規(guī)模優(yōu)化器新領袖地位，成為性價比最為優(yōu)秀的企業(yè)大規(guī)模優(yōu)化器首選。目前客戶還在積極拓展。
Xpress(FICO)
美國商業(yè)
是
Mosel, BCL, C, C++, Java, R Python, Matlab, .Net, VB6
綜合
優(yōu)化技術和解決方案套件。各項指標均衡，背靠FICO，金融客戶多，影響力主要在歐美。
MOSEK,獨立
丹麥商業(yè)
是
C,C#,Java,MATLAB,Python,R
二次為主
重點是解決大規(guī)模稀疏問題，特別是在二次規(guī)劃、二階錐和半正定規(guī)劃領域有著不俗的表現?？蛻糁饕诮鹑?，特別是量化計算。
SAS,獨立
美國商業(yè)
是
綜合
SAS是傳統的統計軟件
SCIP,德國ZIB研究所
德國開源
是
C,C++,MATLAB,Python,Java
整數
作為獨立求解器運行，它是用于混合整數程序的最快的非商業(yè)求解器之一。
CLP,多個單位和個人
美國開源
是
C++
線性
CLP是 COIN-OR 項目下線性規(guī)劃問題的求解器,是一個用C++編寫的開源線性規(guī)劃求解器。
BARON,獨立商業(yè)公司
美國商業(yè)
是
C,Python...
非線性為主
用于促進非凸優(yōu)化問題的全局最優(yōu)解，在非線性某些模塊排名較高
COPT，杉數科技
中國商業(yè)
是
C,C++,C,Python,Java
綜合
綜合性數學規(guī)劃軟件，線性規(guī)劃排名世界前列，已應用于多個國內項目
MindOpt,阿里云
中國商業(yè)
是
C,C++,Python
線性
線性單純形法目前排第一，已應用于阿里云內部多個項目
OPTV，華為
中國商業(yè)
否
C++,Pyhton
線性,整數
將運籌學和AI相結合,針對線性和整數模型尋找最優(yōu)解。
CMIP,中科院
中國商業(yè)
否
整數
涵蓋國際現有求解器預處理、啟發(fā)式、割平面、分支、節(jié)點選擇、區(qū)域傳播等各種功能模塊，并已經較好地具備了求解大規(guī)模整數規(guī)劃的能力
3.第三方評測
美國亞利桑那州立大學的Hans Mittelmann教授針對多種開源與商業(yè)數學規(guī)劃求解器進行測評已有近20年的歷史，是公認的可靠第三方測評平臺。
下面列舉幾個常見的數學規(guī)劃問題，全部評測結果見評測官網:http://plato.asu.edu/bench.html
3.1.線性規(guī)劃
評測時間為：2021年11月10日
(1)單純形法線性規(guī)劃求解器
基準測試一共有40個問題，第一行表示平均求解時間(s),第二行以時間最小值為標準進行放縮,第三行表示在規(guī)定時間內解出問題的數量。
可以看出達摩院 MindOpt在單純形法線性規(guī)劃評測中取得 第一的成績，杉數科技 COPT和華為 OPTV分別取得 第二和 第四的成績。
(2)內點法線性規(guī)劃求解器
基準測試一共有47個問題。
在內點法線性規(guī)劃中， GUROBI求解器取得 第一，杉數科技 COPT緊接其次，取得 第二的成績。
3.2.混合整數線性規(guī)劃(1)混合整數線性規(guī)劃基準 - MIPLIB2017
評測時間為：2021年11月13日
上半部分為單線程求解，一共有240個問題，GUROBI求解數量最多，并且用時最短，取得第一；
下半部分為多線程求解，GUROBI在求解數量和求解時間上同樣領先。
(2)輕微病態(tài)的混合整數線性規(guī)劃案例
評測時間為：2021年11月10日
在默認模式下使用MIPLIB2017腳本在 Intel Xeon E5-4657L（48 核，512GB）的 12 個線程上運行。給出的時間是經過的 CPU 秒數。一共有45個問題，限時3小時。
GUROBI求解出了44個問題，并且運行時間最短。杉數科技COPT取得第二的成績，但相比GUROBI的求解數量和求解時間都有很大的差距。
(3)MILP問題的不可行性檢測
評測時間為：2021年12月3日
針對MIPLIB2017在 Intel i7-11700K（64GB，3.6 GHz，8 核） 上的“簡單”不可行問題運行。問題規(guī)模為32個。
GUROBI求解出了最多數量29個，求解時間花費最短，評分第一。杉數科技COPT在求解數量和求解時間上位于第二位。
3.3.混合整數非線性規(guī)劃
評測時間為：2021年8月15日
可行性容差設置為 1e-6。所有不成功都計為最大時間。第二行列出了解決的問題數量（共 87 個）。
BARON在混合整數非線性規(guī)劃中取得第一的成績。
4.關于Mittelmann測評
在測評網站中，我們可以發(fā)現，三大主流求解器只有GUROBI在榜，而CPLEX和Xpress沒有任何測評數據。
2018年12月23日，在數學規(guī)劃求解器業(yè)界有些陰霾的天空中，一聲驚雷。美國亞利桑那州立大學Hans Mittelmann教授在他維護了多年的數學優(yōu)化軟件測評中刪去了IBM Cplex，Gurobi和FICO Xpress這三個主要商業(yè)求解器的全部數據。
這一切都要從新版的MIPLIB說起。由德國科研機構ZIB所維護的MIPLIB是整數規(guī)劃領域最重要的問題集。這個問題集的每個版本都是商業(yè)求解器性能評測的標桿。在2018年11月之前，一直沿用的MIPLIB 2010問題集已有七年之久，而MIPLIB 2017的征集遴選工作也持續(xù)了一年多時間。各大求解器廠商均翹首以盼，希望自己的求解器可以在最新的版本上拔得頭籌。
2018年10月底，跳票許久的MIPLIB 2017終于在即將召開的INFORMS年會之前整理完畢。Mittelmann教授也于11月1日發(fā)布了MIPLIB 2017版本的測評預覽。近年來在舊版MIPLIB一直領先的Gurobi在其當時剛剛完成的8.1版求解器的助力下，保持了優(yōu)勢。
據Mittelmann當時測評信息顯示，Gurobi的速度是Cplex的1.5倍，是Xpress的2倍左右。然而，就在緊接著召開的INFORMS年會上，Gurobi在其宣傳中做了一些變化，在Mittelmann教授發(fā)布的數據的基礎上，有意無意放大了其他兩家廠商未能完成部分的求解時間。并以此得出了Gurobi比Cplex快2.6倍，比Xpress快5.5倍的結論。
這個驚人的“優(yōu)勢”給他們帶來曝光和名聲的同時，也帶來了業(yè)界的批評和競爭對手的律師函。盡管Gurobi很快的撤回了這些數據，并在其官網上發(fā)了致歉聲明，此次事件還是不可逆轉的改變了這個行業(yè)。
2018年12月23日，Mittelmann教授在他的網站上發(fā)布了一個簡短的聲明，說在IBM和FICO的要求下刪除了Cplex和Xpress的數據，并在此同時也刪除了Gurobi的數據。盡管之前事件的誘因是Gurobi的夸大宣傳，但是Mittelmann本人并沒有做錯什么。Cplex和Xpress的主動退出因此也就顯得略有些牽強。所以在后面的測評中不見CPLEX和Xpress的身影，三大主流軟件中只有GUROBI的數據存在。
參考文獻
[1] 1.1.CPLEX: https://en.wikimirror.xyz/w/index.php?search=cplex
[2] 1.2.GUROBI: http://www.gurobi.cn/about.asp?id=1
[3] 1.3.Xpress: https://en.wikimirror.xyz/wiki/FICO_Xpress
[4] 1.4.MOSEK: https://en.wikimirror.xyz/wiki/MOSEK
[5] 1.5.SAS: https://en.wikimirror.xyz/wiki/SAS_(software)
[6] 1.6.SCIP: https://en.wikimirror.xyz/wiki/Zuse_Institute_Berlin
[7] 1.7.CLP: https://en.wikimirror.xyz/wiki/COIN-OR
[8] 1.8.BARON: https://en.wikimirror.xyz/wiki/BARON
[9] 1.9.COPT: https://www.shanshu.ai/copt
[10] 1.10.MindOpt: https://solver.damo.alibaba.com/htmlpages/page#/
[11] 1.11.OPTV: https://www.huaweicloud.com/product/modelarts/optverse.html
[12] 評測主頁:http://plato.asu.edu/bench.html
作者：莫金元，李文樺，李凱文，王銳
莫金元，男，國防科技大學，碩士研究生，研究方向：計算智能與優(yōu)化決策技術
