杉數(shù)求解器COPT 6.0 亮點

混合整數(shù)二階錐規(guī)劃MISOCP求解器

混合整數(shù)凸二次(約束)規(guī)劃MIQ(C)P求解器

參數(shù)調(diào)優(yōu)工具

大幅提升了半定規(guī)劃求解性能

杉數(shù)科技在2022年10月底正式發(fā)布了杉數(shù)求解器COPT 6.0。這距離COPT 5.0的發(fā)布僅有4個月的時間。很多朋友可能會問，這么短的時間做了哪些更新？本文結(jié)合COPT 6.0參與美國亞利桑那大學(xué)Mittelmann教授所維護(hù)的優(yōu)化軟件測評榜單的結(jié)果，帶大家一探究竟。

混合整數(shù)二階錐規(guī)劃求解器

自從2021年10月的COPT 3.0版推出二階錐規(guī)劃(SOCP)求解器以來，其求解性能比肩國際先進(jìn)廠商。金融、能源、化工等領(lǐng)域的用戶試用過之后表示速度確實很快，但同時也期待能設(shè)定整數(shù)變量，滿足在這些領(lǐng)域?qū)崿F(xiàn)徹底的國產(chǎn)化替代。杉數(shù)科技持續(xù)研發(fā)混合整數(shù)二階錐規(guī)劃(MISOCP)求解功能，與二階錐規(guī)劃求解器時隔一年，如今正式面世。

COPT 6.0混合整數(shù)二階錐規(guī)劃求解性能測評結(jié)果

在美國亞利桑那大學(xué)Mittelmann教授維護(hù)的最新公布的測評榜單可以看到，MISOCP測評榜單上共有四家求解器。除新上榜的COPT外，其中Mosek和Gurobi分別是來自丹麥和美國的老牌商業(yè)求解器廠商，SCIP是德國ZIB研究所發(fā)布的開源求解器。表格里求解器名稱上方的數(shù)據(jù)為一個求解器求解所有測評算例的相對平均時間，以平均時間最小的為1，而下方的數(shù)字是可成功求解的算例數(shù)量。

從測評榜單可以看出，COPT新發(fā)布的混合整數(shù)二階錐規(guī)劃求解性能超越了開源的SCIP和老牌商業(yè)廠商Mosek，平均求解時間和可成功求解的算例數(shù)量均明顯優(yōu)于這兩個軟件。同時我們注意到，和美國廠商Gurobi相比，我們的平均求解時間還有一定的差距，且限定時間內(nèi)可求解的數(shù)量也少1個，還有提升的空間。

但是COPT和Gurobi相比也有自己的優(yōu)勢，Gurobi的求解數(shù)量旁邊加了個*號，Mittelmann教授在頁面的最底部解釋說“* 27 instances with constraint violations > 1e-6”，也就是說有多一半的算例，Gurobi盡管算出來了，但是解并不滿足算例的約束條件，換言之就是那不是嚴(yán)格意義上的可行解。而COPT的解不存在這樣的問題。

混合整數(shù)凸二次(約束)規(guī)劃求解器

和二階錐規(guī)劃緊密相關(guān)的兩類數(shù)學(xué)規(guī)劃問題是凸二次規(guī)劃(QP)和凸二次約束規(guī)劃(QCP)。杉數(shù)科技于2022年初的COPT 4.0版本也新增了這兩個問題類型的求解功能。這兩項功能也和二階錐規(guī)劃一樣受限于無法設(shè)定整數(shù)變量。鑒于其緊密聯(lián)系，我們在開發(fā)整數(shù)二階錐規(guī)劃同時也開展了混合整數(shù)凸二次規(guī)劃(MIQP)和混合整數(shù)凸二次約束規(guī)劃(MIQCP)的開發(fā)，于COPT 6.0一并發(fā)布。

COPT 6.0混合整數(shù)凸二次(約束)規(guī)劃求解性能測評結(jié)果

在Mittelmann教授維護(hù)的測評榜單里，混合整數(shù)凸二次規(guī)劃和整數(shù)凸二次約束規(guī)劃的求解性能比對放在了同一個測評項目Convex Discrete QPLIB里。在這個榜單上，COPT6.0一登場，就明顯壓過了其余9家歐美廠商。和老牌求解器Gurobi相比，可正確求解的數(shù)量同為24個，而COPT的平均求解速度領(lǐng)先43%！這是一個標(biāo)志性的成果，這是我們第一次在混合整數(shù)規(guī)劃的領(lǐng)域超過西方主流求解器！

當(dāng)然，從詳細(xì)的測評數(shù)據(jù)可以看出，全部31個算例，還有7個我們未能完成計算。這里面有部分是其他廠商可以在規(guī)定時間內(nèi)求解，而我們需要花更多時間才能完成求解的。我們的混合整數(shù)凸二次(約束)規(guī)劃求解性能還有進(jìn)步的空間。

大幅提升了半定規(guī)劃的求解能力

自從今年6月COPT 5.0發(fā)布半定規(guī)劃(SDP)求解器以來，由于其性能明顯超過了長期領(lǐng)跑的Mosek，因此受到了來自國內(nèi)外學(xué)術(shù)界和商業(yè)界的廣泛關(guān)注。我們也在這個領(lǐng)域，進(jìn)一步提升COPT半定規(guī)劃的求解性能。

COPT 6.0半定規(guī)劃求解性能測評結(jié)果

從Mittelmann教授維護(hù)的測評榜單上可以看到，新發(fā)布的COPT 6.0實現(xiàn)了全部75個問題的正確求解。且求解速度也明顯提升，和COPT 5.0相比，COPT 6.0相對Mosek 10.0的速度領(lǐng)先優(yōu)勢從64%擴(kuò)大為254%。

參數(shù)調(diào)優(yōu)工具

除了求解功能之外COPT 6.0還發(fā)布了新的功能：參數(shù)調(diào)優(yōu)工具(tuner)。

參數(shù)調(diào)優(yōu)是使用求解器時的一項常見操作，尤其是在求解混合整數(shù)規(guī)劃(MIP)時非常重要。COPT的混合整數(shù)規(guī)劃求解器實現(xiàn)了多種啟發(fā)式、割平面算法。有時候?qū)δ硞€問題，往往某個割平面多多益善；而對另一個問題，可能全靠某一種啟發(fā)式算法尋找最優(yōu)解。盡管我們在開發(fā)求解器時，已經(jīng)充分參考公開和客戶算例，設(shè)定了各類啟發(fā)式算法和割平面算法的最佳強度等參數(shù)。但這很難做到兼顧所有的情況。因此在面對某一特定類別的混合整數(shù)規(guī)劃問題的時候，往往需要調(diào)參數(shù)，實現(xiàn)最佳求解效果。我們在過去幫助很多客戶通過專業(yè)知識調(diào)參數(shù)，找到了最合適參數(shù)。而在COPT 6.0，我們發(fā)布了客戶可以自行使用的自動參數(shù)調(diào)優(yōu)工具。

例如求解MIPLIB 2017中的app1-2這個算例，根據(jù)Mittelmann測試榜單中MIPLIB的詳細(xì)對比可知，COPT 6.0默認(rèn)需要166秒才能完成求解，盡管明顯比其他開源求解器的10-20分鐘快，但是依然落后于Gurobi的19秒求解時間。通過使用tuner，我們可以找到一組改進(jìn)參數(shù)

參數(shù)調(diào)優(yōu)工具針對app1-2這個算例找到的一組改進(jìn)參數(shù)

這組參數(shù)調(diào)低了割平面的強度，關(guān)閉了啟發(fā)式算法和預(yù)求解模塊，另適當(dāng)增加了分支定界部分的割平面強度，最終實現(xiàn)了18.4秒求解這個算例，提升幅度超過8倍，最終求解時間也超過了Gurobi。

有關(guān)tuner的各種參數(shù)，如提升調(diào)參穩(wěn)定性的TunePermutes和設(shè)定調(diào)參目標(biāo)的TuneMode等，請參考COPT的文檔試用。此外我們后續(xù)會在杉數(shù)運籌與智能決策教學(xué)平臺https://coridm.d2d.ai/的COPT求解器教程專區(qū)推出參數(shù)調(diào)優(yōu)工具的視頻使用介紹。敬請關(guān)注。

COPT 簡介

杉數(shù)求解器COPT (Cardinal Optimizer)，是杉數(shù)自主研發(fā)的針對大規(guī)模優(yōu)化問題的高效數(shù)學(xué)規(guī)劃求解器套件，也是支撐杉數(shù)端到端供應(yīng)鏈平臺的核心組件。COPT是目前同時具備大規(guī)?；旌险麛?shù)規(guī)劃MIP、線性規(guī)劃LP、半定規(guī)劃SDP、(混合整數(shù))二階錐規(guī)劃(MI)SOCP、以及(混合整數(shù))凸二次規(guī)劃Convex (MI)QP和(混合整數(shù))凸二次約束規(guī)劃Convex (MI)QCP問題求解能力的綜合性能數(shù)學(xué)規(guī)劃求解器，為企業(yè)應(yīng)對高性能求解的需求提供了更多選擇。

COPT支持所有主流操作系統(tǒng)，如Windows、MacOS、Linux (包括蘋果自研芯片和arm64芯片)。您可以從多種語言及建模工具使用COPT，包括基于數(shù)據(jù)的C語言接口，面向?qū)ο蟮腜ython、C++、C#、Java接口，以及AIMMS、AMPL、GAMS、Julia、Pyomo、PuLP、CVXPY等第三方建模工具。

此外COPT支持多種部署方式。除了個人電腦、服務(wù)器之外，我們還提供浮動授權(quán)和計算集群等部署方式，方便學(xué)校實驗室和公司生產(chǎn)環(huán)境等場景的使用。歡迎通過shanshu.ai/copt申請免費的個人試用版本。如需試用服務(wù)器版、浮動授權(quán)或計算集群版本，請與我們?nèi)〉寐?lián)系coptsales@shanshu.ai。

如果您在申請、使用求解器的過程中遇到任何問題，請寫郵件到coptsupport@shanshu.ai或加入COPT求解器QQ群811049651討論。