作為首個(gè)全自主研發(fā)國產(chǎn)數(shù)學(xué)規(guī)劃求解器，時(shí)隔四個(gè)月，杉數(shù)科技發(fā)布全新的COPT 4.0。和COPT 3.0相比，此次發(fā)布不僅大幅提升了混合整數(shù)規(guī)劃MIP，線性規(guī)劃LP，和二次錐優(yōu)化SOCP的求解速度，還新增了凸二次規(guī)劃QP和凸二次約束規(guī)劃QCP求解能力，添加了計(jì)算不可行模型最小沖突集IIS的功能。另外，為了回饋社區(qū)，此次發(fā)布也極大簡化了申請安裝流程。
COPT 4.0的測評速度提升
新版的COPT求解器分別在3類問題6個(gè)項(xiàng)目的測評中實(shí)現(xiàn)了大幅的性能提升，并新增了凸二次函數(shù)優(yōu)化。具體數(shù)據(jù)總結(jié)如下表小結(jié)所示。
COPT 4.0版求解速度提升以及同行比較 (根據(jù)2022年2月17日測評數(shù)據(jù))
杉數(shù)求解器COPT自從2019年5月首次公開發(fā)布起，一直長期占據(jù)線性規(guī)劃LP測評榜首的位置。其中單純形法Simplex求解器從2019年5月17日起至今32個(gè)月里，約70%的時(shí)間占據(jù)測評第一，占據(jù)著統(tǒng)治性地位。而線性規(guī)劃中相對更快更有優(yōu)勢的Barrier方法，登上榜首以后更是只讓王冠外落過于Gurobi一次。
混合整數(shù)規(guī)劃的測評一共有三個(gè)項(xiàng)目，分別是MIPLIB 2017 Benchmark，PathologicalMIP和InfeasibleMIP。其中MIPLIB 2017 Benchmark共有240個(gè)算例構(gòu)成，是核心的測試項(xiàng)目，反應(yīng)混合整數(shù)規(guī)劃求解器的綜合實(shí)力。PathologicalMIP顧名思義是“不理智的、病態(tài)的”算例集，是一些特別難解的混合整數(shù)規(guī)劃問題。InfeasibleMIP是無可行解的問題集，考察的是求解器證明MIP問題不可行性的速度。
在混合整數(shù)規(guī)劃MIP這三個(gè)測試項(xiàng)目中，國外老牌求解器Gurobi依然處于領(lǐng)先的位置，COPT在三項(xiàng)測評中均為第二名。如上表所示，COPT 4.0較COPT 3.0在三個(gè)測試項(xiàng)目里均有顯著的性能提升。其中在MIPLIB 2017 Benchmark這個(gè)關(guān)鍵測試集上，和Gurobi相比，相對求解時(shí)間從4.92直接降至3.50，COPT的速度提升了41%。此外，兩小時(shí)內(nèi)可解算例的數(shù)量也從176增加到185個(gè)。另外，相比于老牌求解器Xpress下榜前的最后一次記錄是可解180個(gè)問題，我們基本已經(jīng)達(dá)到了跟他們一個(gè)水平線。也有一些學(xué)術(shù)界的朋友幫我們做了一次內(nèi)測，實(shí)際對比我們求解時(shí)間大約為Xpress的1.8倍，也是首次與三大求解器的差距拉到了2倍之內(nèi)，對我們來說這是一個(gè)有著最重要意義的進(jìn)步。
COPT 4.0測評數(shù)據(jù)
此外COPT求解大規(guī)模二階錐規(guī)劃SOCP的性能較上一個(gè)版本提升了40%左右。目前較榜上第一名的Mosek還有21%的速度差距。面對差距，我們新的一年將繼續(xù)努力，下一版本我們的目標(biāo)將會(huì)是世界第一！
COPT 4.0的新求解功能：凸QP和凸QCP求解器
在不斷提升已有求解器性能的同時(shí)，杉數(shù)求解器團(tuán)隊(duì)不斷拓展求解器的能力范圍。COPT４.０新增了凸QP和凸QCP問題的求解能力。
其中二次規(guī)劃問題QP是指在目標(biāo)函數(shù)內(nèi)部有如x平方以及xy等二次項(xiàng)的這樣的問題。二次規(guī)劃問題最早在金融領(lǐng)域提出，用來做投資組合優(yōu)化。二次約束規(guī)劃問題QCP則是在問題約束之內(nèi)有二次項(xiàng)。若一個(gè)規(guī)劃問題，同時(shí)有二次約束以及二次目標(biāo)函數(shù)，則稱之為二次約束二次規(guī)劃問題，英文簡稱為QCQP。
和線性規(guī)劃不同，求解QP、QCP以及QCQP等問題前需要檢查該問題是否為凸。如果為凸則可以使用內(nèi)點(diǎn)法求解，如果非凸則為NP難問題，需要用到分支定界等算法求解。COPT 4.0新增的求解功能為凸QP、QCP和QCQP三項(xiàng)。雖然緊密相關(guān)，但其實(shí)背后的實(shí)現(xiàn)細(xì)節(jié)并不盡相同。
COPT 4.0 新增加QP和QCP求解器直取測評第一
COPT 4.0 的QP和QCP功能也提交給了第三方測評機(jī)構(gòu)參與性能評測。由于QP和QCP兩者緊密相關(guān)，因此被共同放在一個(gè)名為Convex Continuous QPLIB的測評榜單之內(nèi)。從測評結(jié)果看來，COPT 4.0不僅可以正確的在時(shí)限之內(nèi)求解全部問題，其平均求解時(shí)間也是第一。值得指出的是，老牌廠商如Gurobi和Mosek均無法在２小時(shí)時(shí)間限制內(nèi)正確求解全部問題，而同樣能解出全部問題的Knitro則平均速度較COPT慢50%以上，這充分說明了此項(xiàng)測評的難度。
COPT 4.0的新輔助功能：計(jì)算IIS
COPT 4.0版本添加了計(jì)算不可行模型最小沖突集（Irreducible Inconsistent Subsystem，簡稱IIS）的分析功能，支持線性規(guī)劃和混合整數(shù)規(guī)劃。
添加這項(xiàng)功能是因?yàn)樵趯?shí)際應(yīng)用中，經(jīng)常因?yàn)橛脩艚５腻e(cuò)誤或給定輸入數(shù)據(jù)本身的沖突，導(dǎo)致構(gòu)建的數(shù)學(xué)規(guī)劃模型無解。一般來說，由于實(shí)際模型規(guī)模較大且約束關(guān)系復(fù)雜，難以人工分析出導(dǎo)致模型無解的原因，因此需要借助計(jì)算機(jī)進(jìn)行輔助分析。該功能允許用戶在給定的時(shí)間內(nèi)找到一個(gè)導(dǎo)致模型不可行的極小沖突集，并且指明根本原因是哪些約束或變量的上/下邊界，用戶可以根據(jù)上述信息修改模型，最終使得模型可行。
例如下列寫成LP格式的線性規(guī)劃問題是一個(gè)不可行的問題（所有的變量X取值為非負(fù)）
盡管它只有8個(gè)變量，11個(gè)約束，但如果要手動(dòng)找到不可行的原因，任然是一個(gè)很難的事情。使用COPT的IIS工具，則可以計(jì)算出它的IIS為：
進(jìn)一步分析這個(gè)小問題，根據(jù)約束ROW1推知X4≤10000-0.8X3≤ 10000，根據(jù)ROW5推知X4≥ 87000+X2≥ 87000，這兩個(gè)矛盾的約束導(dǎo)致原始問題不可行。用戶最終可以選擇增大ROW1的10000或者減少ROW5的87000來修復(fù)不可行性。
注意，不可行模型可能存在多組IIS，COPT每次計(jì)算時(shí)只返回一組IIS，用戶可能需要根據(jù)返回的沖突原因多次修改模型與計(jì)算IIS。
COPT在實(shí)際使用中的效果
過去兩年COPT已經(jīng)累積了上千個(gè)用戶，并且包括了30多家付費(fèi)商業(yè)用戶，橫跨了制造，金融，供應(yīng)鏈，能源，安防，交通等多個(gè)領(lǐng)域。
除了參與公開測評之外，COPT也不斷的從商業(yè)用戶的實(shí)際問題中獲得成長。這些用戶有一部分是本身因美國卡脖子等操作有國產(chǎn)化替代需求，提供給我們算例，我們做針對性的改進(jìn)以確保在國產(chǎn)化替代時(shí)不損失求解性能。另一些則是抱著追趕和學(xué)習(xí)的態(tài)度，結(jié)果發(fā)現(xiàn)COPT在處理實(shí)際問題時(shí)，其求解效果在很多場合其實(shí)并不落后太多甚至優(yōu)于國外廠商。
其中某ICT公司國產(chǎn)化替代需求非常緊迫，他們一項(xiàng)的排產(chǎn)排程項(xiàng)目需要求解大量的大規(guī)模線性規(guī)劃松弛問題。歷經(jīng)兩年的時(shí)間建模求解完成后，又經(jīng)過半年分別針對三類問題做了輕度的參數(shù)調(diào)整開發(fā)。在該公司內(nèi)部平臺(tái)上測試，和Gurobi 9.0進(jìn)行對比時(shí)，求解效果如下表所示：
某ICT公司三類LP算例規(guī)模和求解時(shí)間對比（求解時(shí)間單位：秒）
再如國網(wǎng)某省2020年的時(shí)候有一個(gè)水火電聯(lián)合安全約束機(jī)組組合優(yōu)化問題，需要快速的求解MIP問題，客戶探索用COPT替代Cplex。由于MIP問題的內(nèi)在難度，當(dāng)時(shí)我們很難趕上Cplex多年的積累，可以看出直接求解時(shí)間Cplex可以在1-2分鐘完成，而COPT需要5倍左右的時(shí)間。為了不使國產(chǎn)化替代影響求解時(shí)間，我們積極探索改進(jìn)模型，應(yīng)用了機(jī)器學(xué)習(xí)進(jìn)行提速改進(jìn)。此項(xiàng)改進(jìn)策略下，COPT大幅提升了求解速度，其中COPT在改進(jìn)后的速度達(dá)到或者超過了原始的Cplex求解速度。
某省水火電聯(lián)合安全約束機(jī)組組合優(yōu)化（求解時(shí)間單位：秒）
除了國產(chǎn)化替代等需求之外，也有一些其他的公司嘗試了COPT。例如某生活類電商巨頭近期對比COPT和他們的Gurobi在一些路線規(guī)劃求解問題上的整數(shù)規(guī)劃模型求解。從測試結(jié)果可以看出，COPT的速度和Gurobi相比非常接近，甚至在部分問題上更快。
某生活類電商巨頭公司混合整數(shù)規(guī)劃問題（求解時(shí)間單位：秒）
除了服務(wù)國內(nèi)的客戶之外，我們也積極探索和國外的廠商合作，拓展國內(nèi)外市場。老牌建模語言廠商AMPL、GAMS已經(jīng)主動(dòng)跟我們聯(lián)系，并且達(dá)成官方協(xié)議，由這些廠商官方接入COPT，并將COPT和建模語言打包銷售。此外我們和AIMMS、ODH等也在對方主動(dòng)聯(lián)系后，展開了合作討論。其中一家合作方發(fā)來的，基于早期版本的郵件非常鼓舞我們（應(yīng)要求隱去了合作方的名字）
某國外建模語言合作商測試COPT早期版本后發(fā)來的郵件
COPT 4.0的申請安裝流程極大簡化
根據(jù)此前申請、安裝COPT的一些反饋信息可知，要求用戶使用我們提供的工具，同時(shí)輸入用戶名稱，MAC地址、CPUID等硬件信息非常繁瑣。兩年來從我們1000多個(gè)累計(jì)用戶這里，我們也得到了巨大的幫助。深深感受到了國內(nèi)外運(yùn)籌從業(yè)人員與愛好者對COPT的支持和關(guān)注。
為了回饋社區(qū)，在準(zhǔn)備新版的同時(shí)，我們也簡化了這一流程和延長了試用時(shí)間，用戶申請的時(shí)候只需提供用戶名稱，也就是計(jì)算機(jī)上的username這一項(xiàng)就足夠了。同時(shí)，我們延長了商業(yè)用戶試用期限至6個(gè)月時(shí)間，縮短了申請審核時(shí)間至2個(gè)工作日。將來會(huì)探索學(xué)術(shù)用戶申請?jiān)囉米詣?dòng)發(fā)放的機(jī)制。此外我們還準(zhǔn)備了安裝FAQ頁面，會(huì)收集整理申請、安裝中遇到的問題，及時(shí)更新。供大家參考。
求解器這項(xiàng)專業(yè)工具，和Office等辦公工具不同，它沒有一個(gè)自己的圖形界面。使用求解器一般是從各種編程語言中調(diào)用，或者使用命令行工具等。為此提升求解器的易用性，我們也專門提供了C、C++、C#、Python、Java、AMPL、GAMS、Pyomo、PuLP、CVXPY等十余種編程語言接口，以及大量的示例，方便用戶上手。
