社會工業(yè)化發(fā)展的進程中，底層基礎(chǔ)技術(shù)和軟件的發(fā)展極為重要。在運籌優(yōu)化領(lǐng)域，“求解器”發(fā)揮了極其重要的作用。求解器技術(shù)屬于典型的底層技術(shù)領(lǐng)域，技術(shù)門檻高、研發(fā)難度大、投入時間長且風險較高。種種條件制約下，從1957年紐厄爾和西蒙等人開始研究一種不依賴于具體領(lǐng)域的“通用問題求解器”到現(xiàn)在，六十多年發(fā)展，全球主流求解器市場仍被美國公司的產(chǎn)品所壟斷，并且構(gòu)筑了極高的市場競爭門檻。由于求解器在工業(yè)場景中的重要作用，近幾年國產(chǎn)求解器研發(fā)領(lǐng)域也在蓬勃發(fā)展，一些新興科技公司和大廠研發(fā)的求解器嶄露頭角，并在線性規(guī)劃求解方面實現(xiàn)突破，達到全球領(lǐng)先地位。物流作為一個數(shù)據(jù)量大、數(shù)據(jù)關(guān)系復雜的行業(yè)，與優(yōu)化求解器有著天然的契合關(guān)系。運籌優(yōu)化求解器在物流領(lǐng)域的應(yīng)用是行業(yè)發(fā)展的必然結(jié)果，也將為解決物流實際問題提供有效的解決方案。
一、求解器的理論基礎(chǔ)：數(shù)學規(guī)劃問題
數(shù)學規(guī)劃是運籌學的一個分支，用于研究在給定的約束條件下如何按照某一衡量指標（即目標函數(shù)）來尋求最優(yōu)的方案。數(shù)學規(guī)劃是優(yōu)化問題建模的第一步，也是最重要的一步，因為它界定了問題的類型和求解難度。在數(shù)學模型的基礎(chǔ)上，求解器可以對問題進行求解并尋找問題的最優(yōu)解。簡而言之，求解器是用來求解數(shù)學規(guī)劃問題的一類軟件，在現(xiàn)實生產(chǎn)生活中具有重要價值和意義。
根據(jù)問題的性質(zhì)和處理方法的差異，數(shù)學規(guī)劃又可分成許多不同的分支，如線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、混合整數(shù)規(guī)劃等，各種數(shù)學規(guī)劃問題分類及其之間的關(guān)系如圖7-13。


圖7-13 常見的數(shù)學規(guī)劃問題分類
資料來源：https://mp.weixin.qq.com/s/ZIVfnAYFNYhK7njiJxJQVQ
數(shù)學規(guī)劃在國防、工業(yè)制造、交通物流、資源管理、金融、集成電路設(shè)計、電力管理等生產(chǎn)生活各個領(lǐng)域都有著十分廣泛的應(yīng)用，是在實際應(yīng)用中創(chuàng)造價值最巨大的優(yōu)化方法。現(xiàn)實中各種類型優(yōu)化問題，小到快遞員路線選擇、商鋪選址，大到工廠生產(chǎn)排程、物流路徑規(guī)劃等，都可以抽象成數(shù)學規(guī)劃問題，采用數(shù)學定義的方式，定義出優(yōu)化問題三要素：決策變量、優(yōu)化目標以及約束條件，然后建立不同的數(shù)學模型，并利用求解器進行求解優(yōu)化。數(shù)學規(guī)劃問題，是求解器運行的理論基礎(chǔ)。
二、主流求解器及其對比分析
目前主流求解器市場主要分為商用求解器、開源求解器兩類，全球知名的商用求解器主要有Gurobi、Cplex、FICO Xpress，而開源求解器主要有SCIP、GLPK。在國內(nèi)，著名的商用求解器包括杉數(shù)科技COPT求解器、阿里云MindOpt求解器、華為天籌AI求解器OPTV，而開源求解器主要有上海財經(jīng)大學LEAVES求解器、中國科學院CMIP求解器等。這些優(yōu)化求解器以工業(yè)軟件的形式，把數(shù)學規(guī)劃方法用于大規(guī)模復雜問題的優(yōu)化求解，是解決各種數(shù)學規(guī)劃問題的核心工具，在實際生產(chǎn)生活中具有重要價值和意義。
（一）國外主流求解器
1. Gurobi
Gurobi是由美國Gurobi Optimization公司開發(fā)的大規(guī)模優(yōu)化器。在理論和實踐中，Gurobi優(yōu)化工具被證明是全球性能領(lǐng)先的大規(guī)模優(yōu)化器，可以為客戶在開發(fā)和實施中極大降低成本，具有突出的性價比。它廣泛應(yīng)用在金融、物流、制造、航空、石油石化、商業(yè)服務(wù)等多個領(lǐng)域，為智能化決策提供了堅實的基礎(chǔ)，成為上千個成熟應(yīng)用系統(tǒng)的核心優(yōu)化引擎。Gurobi是全局精確優(yōu)化器，支持的模型類型包括：連續(xù)和混合整數(shù)線性問題、凸目標或約束連續(xù)和混合整數(shù)二次問題、非凸目標或約束連續(xù)和混合整數(shù)二次問題、含有對數(shù)、指數(shù)、三角函數(shù)、高階多項式目標或約束，以及任何形式的分段約束的非線性問題、含有絕對值、最大值、最小值、邏輯與或非目標或約束的非線性問題。
2. CPLEX
CPLEX最初版本開發(fā)于1988年，2009年納入IBM產(chǎn)品體系，如今發(fā)展成為IBM決策優(yōu)化系統(tǒng)IBM ILOG CPLEX Optimization Studio（簡稱COS）。作為COS系統(tǒng)中的關(guān)鍵組件，CPLEX Optimizer為線性規(guī)劃、混合整數(shù)規(guī)劃、二次規(guī)劃和二次約束規(guī)劃問題提供靈活的高性能數(shù)學規(guī)劃求解器。此外，求解器還包含了用于混合整數(shù)規(guī)劃的分布式并行算法，支持利用多臺計算機來解決難題，可求解具有數(shù)百萬個約束和變量的優(yōu)化模型。
3. SCIP
SCIP（Solving Constraint Integer Programs）是一款開源規(guī)劃問題求解器，主要由德國ZIB研究所開發(fā)。SCIP是目前混合整數(shù)規(guī)劃和混合整數(shù)非線性規(guī)劃最快的非商業(yè)求解器之一，其使用的算法思想為分支定界法。與大多數(shù)商業(yè)求解器不同，SCIP允許用戶對求解過程進行完全控制，并允許用戶訪問求解器內(nèi)部的詳細信息。
4. GLPK
GLPK（GNU Linear Programming Kit，GNU線性編程工具）是GNU下的一個項目，用于建立大規(guī)模線性規(guī)劃和混合型整數(shù)規(guī)劃問題，并對模型進行最優(yōu)化求解。
5. Xpress
Xpress于1983年發(fā)布，是第一個在筆記本電腦上運行的商業(yè)線性規(guī)劃和混合整數(shù)規(guī)劃求解器。1992年推出了并行計算版本，五年后擴展到分布式計算。Xpress還是第一個跨越十億決策變量閾值的混合整數(shù)規(guī)劃求解器，于2013年首次實現(xiàn)了并行對偶單純形方法的商業(yè)實現(xiàn)。Xpress支持多種類型規(guī)劃的求解，主要包括：線性規(guī)劃、混合整數(shù)線性規(guī)劃、二次規(guī)劃、二次約束二次規(guī)劃、二階錐規(guī)劃、混合整數(shù)非線性規(guī)劃、混合整數(shù)二次規(guī)劃、混合整數(shù)二次約束二次規(guī)劃、混合整數(shù)二階錐規(guī)劃、一般非線性規(guī)劃，一般混合整數(shù)非線性規(guī)劃、約束規(guī)劃等。
6. LINGO
LINGO是Linear Interactive and General Optimizer的縮寫，即“交互式的線性和通用優(yōu)化求解器”，是由美國LINDO系統(tǒng)公司（Lindo System Inc.）推出的專門用于求解最優(yōu)化問題的軟件包。其特色在于內(nèi)置建模語言，提供許多常用函數(shù)方便使用者建立優(yōu)化模型時調(diào)用，并提供與其他數(shù)據(jù)文件（如文本、EXCEL、數(shù)據(jù)庫等）的接口，易于方便地輸入、求解和分析大規(guī)模最優(yōu)化問題。LINGO支持求解的規(guī)劃類型為：線性規(guī)劃、非線性規(guī)劃、二次規(guī)劃、二次約束規(guī)劃、二階錐規(guī)劃問題、半定規(guī)劃問題、隨機和整數(shù)規(guī)劃問題等。
7. MOSEK
MOSEK是由丹麥MOSEK ApS公司開發(fā)的一款數(shù)學規(guī)劃求解器，也是公認的求解二次規(guī)劃、二階錐規(guī)劃和半正定規(guī)劃問題最快的求解器之一，廣泛應(yīng)用于金融、保險、能源等領(lǐng)域。其支持求解的模型包括線性規(guī)劃，二次約束凸規(guī)劃，二階錐規(guī)劃，半正定規(guī)劃，一般可分離凸規(guī)劃和混合整數(shù)規(guī)劃等。
8. BARON
BARON（Branch And Reduce Optimization Navigator）是一種通用的非線性優(yōu)化器，能夠?qū)⒎峭箖?yōu)化問題求解到全局最優(yōu)。其決策變量可以是連續(xù)的、整數(shù)的或兩者的混合。BARON已應(yīng)用于化學過程工業(yè)、制藥、能源生產(chǎn)、工程設(shè)計和資產(chǎn)管理等領(lǐng)域。其支持求解的模型包括：線性規(guī)劃、一般非線性規(guī)劃、混合整數(shù)規(guī)劃、一般混合整數(shù)非線性規(guī)劃等。
（二）國內(nèi)主流求解器
1. 上海財經(jīng)大學LEAVES求解器
LEAVES優(yōu)化求解器是上海財經(jīng)大學并行優(yōu)化國際合作實驗室與杉數(shù)科技共同牽頭建設(shè)的一個運籌學與人工智能基礎(chǔ)算法平臺。它目前的功能分為三大模塊，即傳統(tǒng)運籌學的根基數(shù)學規(guī)劃、大規(guī)模機器學習算法的高效實現(xiàn)和運籌學的實際應(yīng)用。其中數(shù)學規(guī)劃求解器的部分，LEAVES是第一個成規(guī)模的華人運籌學優(yōu)化算法求解器，可以解決線性規(guī)劃、半正定規(guī)劃、幾何規(guī)劃、線性約束的凸規(guī)劃等常見的大規(guī)模優(yōu)化算法求解問題，對其中多個經(jīng)典模型的求解速度和效率達到國際一流水平。
2. 中科院CMIP求解器
CMIP求解器由中歐科學院CMIP團隊研發(fā)，于2018年3月發(fā)布1.0版本。目前其代碼總量已經(jīng)超過五萬行，涵蓋國際現(xiàn)有求解器預(yù)處理、啟發(fā)式、割平面、分支、節(jié)點選擇、區(qū)域傳播等各種功能模塊，并已經(jīng)較好地具備了求解大規(guī)模整數(shù)規(guī)劃問題的能力。求解器采用團隊自主研發(fā)的一種廣義系數(shù)縮緊割平面技術(shù)，對于一般的整數(shù)規(guī)劃問題具有一定的改善效果，尤其對于網(wǎng)絡(luò)設(shè)計問題效果顯著。
3. 杉數(shù)求解器COPT
杉數(shù)求解器COPT（Cardinal Optimizer）是杉數(shù)自主研發(fā)的針對大規(guī)模優(yōu)化問題的高效數(shù)學規(guī)劃求解器套件，也是支撐杉數(shù)端到端供應(yīng)鏈平臺的核心組件。COPT是目前同時具備大規(guī)模混合整數(shù)規(guī)劃、線性規(guī)劃（單純形法和內(nèi)點法）、二階錐規(guī)劃、半定規(guī)劃以及凸二次規(guī)劃和凸二次約束規(guī)劃問題求解能力的綜合性能數(shù)學規(guī)劃求解器，為企業(yè)提供了更多高性能求解的選擇。
4. 阿里云MindOpt求解器
MindOpt是阿里達摩院決策智能實驗室自主研發(fā)的一款具備線性規(guī)劃等多種功能的數(shù)學規(guī)劃求解器套件。它通過對大規(guī)模線性規(guī)劃的快速穩(wěn)定求解，為客戶提供從數(shù)據(jù)到?jīng)Q策的全鏈路建模和求解能力，可廣泛應(yīng)用于云計算、電力能源、工業(yè)制造、交通物流、零售、金融等領(lǐng)域，能幫助做方案設(shè)計、生產(chǎn)方案優(yōu)化、資源合理分配、輔助決策等。其支持求解模型主要包括線性規(guī)劃、非線性規(guī)劃和混合整數(shù)規(guī)劃等。
5. 華為天籌AI求解器
天籌（OptVerse）AI求解器將運籌學和人工智能相結(jié)合，突破業(yè)界運籌優(yōu)化極限，針對線性和整數(shù)模型尋找最優(yōu)解，以通用形式描述問題，高效計算最優(yōu)方案，助力企業(yè)量化決策和精細化運營，提升資源利用率和運轉(zhuǎn)效率，增強決策水平和競爭力。其獨特優(yōu)勢在于融合了先進的人工智能技術(shù)，可根據(jù)問題特征自適應(yīng)進行參數(shù)調(diào)優(yōu)和求解策略選取，實現(xiàn)最大30%的求解效率提升。
（三）主流求解器優(yōu)勢特點對比
從求解器的類型來看，商用求解器求解效率明顯高于開源求解器，以制造業(yè)中的生產(chǎn)排程為例，在保證數(shù)據(jù)準確性的前提下，采用商用求解器計算的排產(chǎn)指標可縮短至分鐘級。隨著運籌優(yōu)化問題的不斷細分，不同的求解器在各類數(shù)學規(guī)劃問題求解中表現(xiàn)出不同的優(yōu)勢特點。