时隔四个月, 杉数科技正式发布数学规划求解器 COPT 5.0, 整数规划模块继续大幅度提高, 全面接近 CPLEX。
时隔四个月, 杉数科技正式发布数学规划求解器 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 发布的用户手册和自带示例。
来源：互联网
