時隔四個月,杉數(shù)科技正式發(fā)布數(shù)學規(guī)劃求解器COPT 5.0,整數(shù)規(guī)劃模塊繼續(xù)大幅度提高,全面接近CPLEX。與年初COPT 4.0相比,COPT 5.0在保持線性規(guī)劃LP、凸二次規(guī)劃QP等多項性能測評領(lǐng)先的同時,再一次大幅提升了混合整數(shù)規(guī)劃MIP求解速度。同時,COPT 5.0還新增半定規(guī)劃SDP求解器,以及FeasRelax功能。
杉數(shù)優(yōu)化求解器COPT 5.0求解性能一覽
新版的COPT求解器分別在多個類別求解性能測評中占據(jù)領(lǐng)先位置,具體數(shù)據(jù)如下表小結(jié)所示:
(根據(jù)2022年6月19日測評數(shù)據(jù),主要測評數(shù)據(jù)來自Mittelmann測評榜單,兩項Cplex數(shù)據(jù)來自數(shù)據(jù)魔術(shù)師)
杉數(shù)優(yōu)化求解器COPT自從2019年5月首次公開發(fā)布起,一直長期占據(jù)線性規(guī)劃LP測評榜首的位置。其中單純形法Simplex求解器從2019年5月17日起至今的3年多時間里,超過70%的時間占據(jù)測評第一,占據(jù)著統(tǒng)治性地位。而線性規(guī)劃中相對更快更有優(yōu)勢的Barrier方法,登上榜首以后更是只讓王冠外落過于Gurobi一次。
COPT 5.0在Mittelmann平臺測評數(shù)據(jù)
混合整數(shù)規(guī)劃MIP的測評一共有三個項目,分別是MIPLIB 2017 Benchmark,Pathological MIP和Infeasible MIP。其中MIPLIB 2017 Benchmark共有240個算例構(gòu)成,是核心的測試項目,反映混合整數(shù)規(guī)劃求解器的綜合實力。Pathological MIP顧名思義是“不理智的、病態(tài)的”算例集,是一些特別難解的混合整數(shù)規(guī)劃問題。Infeasible MIP是無可行解的算例集,考察的是求解器證明MIP問題不可行性的速度。
在混合整數(shù)規(guī)劃MIP這三個測試項目中,國外老牌求解器Gurobi依然處于領(lǐng)先位置,COPT在三項測評中均為第二名。COPT 5.0較COPT 4.0在三個測試項目里均有顯著的性能提升。其中在MIPLIB 2017 Benchmark這個關(guān)鍵測試集上,和Gurobi相比,相對求解時間從3.50直接降至2.34,COPT的速度提升了50%左右。另外根據(jù)數(shù)據(jù)魔術(shù)師秦虎教授團隊的近期的測試顯示,COPT 5.0版只比三大廠中的Cplex慢27%,進一步縮小了和傳統(tǒng)大廠之間的距離!
COPT 5.0的新求解功能:半正定規(guī)劃(SDP)求解器
在不斷提升已有求解器性能的同時,杉數(shù)求解器團隊也積極拓展求解器的能力范圍。COPT 5.0新增了半定規(guī)劃SDP問題的求解能力。
半定規(guī)劃(SDP)作為凸優(yōu)化問題的重要分支,在極大拓展了傳統(tǒng)線性模型表示能力的同時仍可被數(shù)值算法精確求解,因而具有強大的應(yīng)用能力。半定規(guī)劃在學界與業(yè)界的經(jīng)典應(yīng)用場景包括金融中的投資組合優(yōu)化建模與計算、控制理論中的線性矩陣不等式(LMI)、工程設(shè)計中的結(jié)構(gòu)優(yōu)化、機器學習中的矩陣補全與組合優(yōu)化問題的凸松弛、無線傳感定位問題、以及魯棒優(yōu)化問題的建模等。而近年來,半定規(guī)劃也開始在量子查詢(Quantum Query)等領(lǐng)域得到更多創(chuàng)新的應(yīng)用。
COPT 5.0 新增加SDP求解器,位列榜單第一
COPT 5.0的SDP功能也提交給了第三方測評機構(gòu)參與性能評測。從測評結(jié)果看來,COPT 5.0不僅正確求解算例數(shù)量最多,其平均求解時間也是第一。此次發(fā)布,一舉超越此前性能排行第一的商業(yè)求解器Mosek,領(lǐng)先128%。值得指出的是,榜單上無任何求解器可以完全精確地解出全部 75 個問題,這主要是因為SDP問題不僅數(shù)值難度高,而且計算規(guī)模也特別大。綜合來看,初出茅廬的COPT的SDP求解器還有提升的空間。
在學術(shù)界,半定規(guī)劃長時間以來一直作為有力的數(shù)學模型被運用于各類問題中,而隨著算力與算法的進步,越來越多的領(lǐng)域也正在探索使用半定規(guī)劃求解問題的可行性。杉數(shù)求解器團隊將不斷改進SDP求解模塊,助力這一優(yōu)化工具應(yīng)用于更多的實際問題。
COPT 5.0新輔助功能:FeasRelax功能
FeasRelax是針對無可行解的問題開發(fā)的一項功能。針對這個類型的問題COPT 4.0已提供了IIS計算功能,可以幫助用戶快速計算造成模型不可行的最小沖突集、指出不可行的原因。COPT 5.0提供的Feasibility Relaxation(FeasRelax)功能更進一步,可以幫助用戶直接算出如何做最小的改動,將不可行的問題轉(zhuǎn)化為可行的問題。在FeasRelax計算完成后,用戶可以直接寫出可行化的模型(.relax文件),也可以直接獲取所有變量、約束邊界的所需要做的最小改動。
對于這個“最小改動”的計算,COPT提供了多種衡量準則和計算模式。有關(guān)具體使用方式和衡量準則細節(jié),請參考隨COPT發(fā)布的用戶手冊和自帶示例。
