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

混合整數(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個(gè)月的時(shí)間。很多朋友可能會(huì)問(wèn)，這么短的時(shí)間做了哪些更新？本文結(jié)合COPT 6.0參與美國(guó)亞利桑那大學(xué)Mittelmann教授所維護(hù)的優(yōu)化軟件測(cè)評(píng)榜單的結(jié)果，帶大家一探究竟。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

COPT 簡(jiǎn)介

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

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

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

如果您在申請(qǐng)、使用求解器的過(guò)程中遇到任何問(wèn)題，請(qǐng)寫(xiě)郵件到coptsupport@shanshu.ai或加入COPT求解器QQ群811049651討論。