整數規劃求解器全球第二，杉數COPT5.0新增半定規劃SDP求解器

　　時隔四個月,杉數科技正式發布數學規劃求解器COPT 5.0,整數規劃模塊繼續大幅度提高,全面接近CPLEX。與年初COPT 4.0相比,COPT 5.0在保持線性規劃LP、凸二次規劃QP等多項性能測評的同時,再一次大幅提升了混合整數規劃MIP求解速度。同時,COPT 5.0還新增半定規劃SDP求解器,以及FeasRelax功能。

　　杉數優化求解器COPT 5.0求解性能一覽

　　新版的COPT求解器分别在多個類别求解性能測評中占據位置,具體數據如下表小結所示:

　　COPT 5.0版求解性能一覽

　　(根據2022年6月19日測評數據,主要測評數據來自Mittelmann測評榜單,兩項Cplex數據來自數據魔術師)

　　杉數優化求解器COPT自從2019年5月公開發布起,一直長期占據線性規劃LP測評榜首的位置。其中單純形法Simplex求解器從2019年5月17日起至今的3年多時間裡,超過70%的時間占據測評第一,占據着統治性地位。而線性規劃中相對更快更有優勢的Barrier方法,登上榜首以後更是隻讓王冠外落過于Gurobi一次。

　　COPT 5.0在Mittelmann平台測評數據

　　混合整數規劃MIP的測評一共有三個項目,分别是MIPLIB 2017 Benchmark,Pathological MIP和Infeasible MIP。其中MIPLIB 2017 Benchmark共有240個算例構成,是核心的測試項目,反映混合整數規劃求解器的綜合實力。Pathological MIP顧名思義是“不理智的、病态的”算例集,是一些特别難解的混合整數規劃問題。Infeasible MIP是無可行解的算例集,考察的是求解器證明MIP問題不可行性的速度。

　　在混合整數規劃MIP這三個測試項目中,國外老牌求解器Gurobi依然處于位置,COPT在三項測評中均為第二名。COPT 5.0較COPT 4.0在三個測試項目裡均有顯著的性能提升。其中在MIPLIB 2017 Benchmark這個關鍵測試集上,和Gurobi相比,相對求解時間從3.50直接降至2.34,COPT的速度提升了50%左右。另外根據數據魔術師秦虎教授團隊的近期的測試顯示,COPT 5.0版隻比三大廠中的Cplex慢27%,進一步縮小了和傳統大廠之間的距離!

　　COPT 5.0的新求解功能:半正定規劃(SDP)求解器

　　在不斷提升已有求解器性能的同時,杉數求解器團隊也積極拓展求解器的能力範圍。COPT 5.0新增了半定規劃SDP問題的求解能力。

　　半定規劃(SDP)作為凸優化問題的重要分支,在極大拓展了傳統線性模型表示能力的同時仍可被數值算法求解,因而具有強大的應用能力。半定規劃在學界與業界的經典應用場景包括金融中的投資組合優化建模與計算、控制理論中的線性矩陣不等式(LMI)、工程設計中的結構優化、機器學習中的矩陣補全與組合優化問題的凸松弛、無線傳感定位問題、以及魯棒優化問題的建模等。而近年來,半定規劃也開始在量子查詢(Quantum Query)等領域得到更多創新的應用。

　　COPT 5.0 新增加SDP求解器,位列榜單第一

　　COPT 5.0的SDP功能也提交給了第三方測評機構參與性能評測。從測評結果看來,COPT 5.0不僅正确求解算例數量最多,其平均求解時間也是第一。此次發布,一舉超越此前性能排行第一的商業求解器Mosek,128%。值得指出的是,榜單上無任何求解器可以完全地解出全部 75 個問題,這主要是因為SDP問題不僅數值難度高,而且計算規模也特别大。綜合來看,初出茅廬的COPT的SDP求解器還有提升的空間。

　　在學術界,半定規劃長時間以來一直作為有力的數學模型被運用于各類問題中,而随着算力與算法的進步,越來越多的領域也正在探索使用半定規劃求解問題的可行性。杉數求解器團隊将不斷改進SDP求解模塊,助力這一優化工具應用于更多的實際問題。

　　COPT 5.0新輔助功能:FeasRelax功能

　　FeasRelax是針對無可行解的問題開發的一項功能。針對這個類型的問題COPT 4.0已提供了IIS計算功能,可以幫助用戶快速計算造成模型不可行的最小沖突集、指出不可行的原因。COPT 5.0提供的Feasibility Relaxation(FeasRelax)功能更進一步,可以幫助用戶直接算出如何做最小的改動,将不可行的問題轉化為可行的問題。在FeasRelax計算完成後,用戶可以直接寫出可行化的模型(.relax文件),也可以直接獲取所有變量、約束邊界的所需要做的最小改動。

　　對于這個“最小改動”的計算,COPT提供了多種衡量準則和計算模式。有關具體使用方式和衡量準則細節,請參考随COPT發布的用戶手冊和自帶示例。