杉数科技发布数学规划求解器COPT 5.0 ：新增半定规划SDP求解器和FeasRelax辅助功能

时隔四个月,杉数科技正式发布数学规划求解器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发布的用户手册和自带示例。