国产数学规划求解器COPT4.0深度解读

摘要：作为首个全自主研发国产数学规划求解器，时隔四个月，杉数科技发布全新的COPT 4.0。和COPT 3.0相比，此次发布不仅大幅提升了混合整数规划MIP，线性规划LP，和二次锥优化SOCP的求解速度，还新增了凸二次规划QP和凸二次约束规划QCP求解能力，添加了计算不可行模型最小冲突集IIS的功能。另外，为了回馈社区，此次发布也极大简化了申请安装流程。
关键词： 数学规划

作为首个全自主研发国产数学规划求解器，时隔四个月，杉数科技发布全新的COPT 4.0。和COPT 3.0相比，此次发布不仅大幅提升了混合整数规划MIP，线性规划LP，和二次锥优化SOCP的求解速度，还新增了凸二次规划QP和凸二次约束规划QCP求解能力，添加了计算不可行模型最小冲突集IIS的功能。另外，为了回馈社区，此次发布也极大简化了申请安装流程。

COPT 4.0的测评速度提升

新版的COPT求解器分别在3类问题6个项目的测评中实现了大幅的性能提升，并新增了凸二次函数优化。具体数据总结如下表小结所示。

COPT 4.0版求解速度提升以及同行比较 (根据2022年2月17日测评数据)

杉数求解器COPT自从2019年5月首次公开发布起，一直长期占据线性规划LP测评榜首的位置。其中单纯形法Simplex求解器从2019年5月17日起至今32个月里，约70%的时间占据测评第一，占据着统治性地位。而线性规划中相对更快更有优势的Barrier方法，登上榜首以后更是只让王冠外落过于Gurobi一次。

混合整数规划的测评一共有三个项目，分别是MIPLIB 2017 Benchmark，PathologicalMIP和InfeasibleMIP。其中MIPLIB 2017 Benchmark共有240个算例构成，是核心的测试项目，反应混合整数规划求解器的综合实力。PathologicalMIP顾名思义是“不理智的、病态的”算例集，是一些特别难解的混合整数规划问题。InfeasibleMIP是无可行解的问题集，考察的是求解器证明MIP问题不可行性的速度。

在混合整数规划MIP这三个测试项目中，国外老牌求解器Gurobi依然处于领先的位置，COPT在三项测评中均为第二名。如上表所示，COPT 4.0较COPT 3.0在三个测试项目里均有显著的性能提升。其中在MIPLIB 2017 Benchmark这个关键测试集上，和Gurobi相比，相对求解时间从4.92直接降至3.50，COPT的速度提升了41%。此外，两小时内可解算例的数量也从176增加到185个。另外，相比于老牌求解器Xpress下榜前的最后一次记录是可解180个问题，我们基本已经达到了跟他们一个水平线。也有一些学术界的朋友帮我们做了一次内测，实际对比我们求解时间大约为Xpress的1.8倍，也是首次与三大求解器的差距拉到了2倍之内，对我们来说这是一个有着最重要意义的进步。

COPT 4.0测评数据

此外COPT求解大规模二阶锥规划SOCP的性能较上一个版本提升了40%左右。目前较榜上第一名的Mosek还有21%的速度差距。面对差距，我们新的一年将继续努力，下一版本我们的目标将会是世界第一!

COPT 4.0的新求解功能：凸QP和凸QCP求解器

在不断提升已有求解器性能的同时，杉数求解器团队不断拓展求解器的能力范围。COPT4.0新增了凸QP和凸QCP问题的求解能力。

其中二次规划问题QP是指在目标函数内部有如x平方以及xy等二次项的这样的问题。二次规划问题最早在金融领域提出，用来做投资组合优化。二次约束规划问题QCP则是在问题约束之内有二次项。若一个规划问题，同时有二次约束以及二次目标函数，则称之为二次约束二次规划问题，英文简称为QCQP。

和线性规划不同，求解QP、QCP以及QCQP等问题前需要检查该问题是否为凸。如果为凸则可以使用内点法求解，如果非凸则为NP难问题，需要用到分支定界等算法求解。COPT 4.0新增的求解功能为凸QP、QCP和QCQP三项。虽然紧密相关，但其实背后的实现细节并不尽相同。

COPT 4.0 新增加QP和QCP求解器直取测评第一

COPT 4.0 的QP和QCP功能也提交给了第三方测评机构参与性能评测。由于QP和QCP两者紧密相关，因此被共同放在一个名为Convex Continuous QPLIB的测评榜单之内。从测评结果看来，COPT 4.0不仅可以正确的在时限之内求解全部问题，其平均求解时间也是第一。值得指出的是，老牌厂商如Gurobi和Mosek均无法在2小时时间限制内正确求解全部问题，而同样能解出全部问题的Knitro则平均速度较COPT慢50%以上，这充分说明了此项测评的难度。

COPT 4.0的新辅助功能：计算IIS

COPT 4.0版本添加了计算不可行模型最小冲突集(Irreducible Inconsistent Subsystem，简称IIS)的分析功能，支持线性规划和混合整数规划。

添加这项功能是因为在实际应用中，经常因为用户建模的错误或给定输入数据本身的冲突，导致构建的数学规划模型无解。一般来说，由于实际模型规模较大且约束关系复杂，难以人工分析出导致模型无解的原因，因此需要借助计算机进行辅助分析。该功能允许用户在给定的时间内找到一个导致模型不可行的极小冲突集，并且指明根本原因是哪些约束或变量的上/下边界，用户可以根据上述信息修改模型，最终使得模型可行。

例如下列写成LP格式的线性规划问题是一个不可行的问题(所有的变量X取值为非负)

尽管它只有8个变量，11个约束，但如果要手动找到不可行的原因，任然是一个很难的事情。使用COPT的IIS工具，则可以计算出它的IIS为：

进一步分析这个小问题，根据约束ROW1推知X4≤10000-0.8X3≤ 10000，根据ROW5推知X4≥ 87000+X2≥ 87000，这两个矛盾的约束导致原始问题不可行。用户最终可以选择增大ROW1的10000或者减少ROW5的87000来修复不可行性。

注意，不可行模型可能存在多组IIS，COPT每次计算时只返回一组IIS，用户可能需要根据返回的冲突原因多次修改模型与计算IIS。

COPT在实际使用中的效果

过去两年COPT已经累积了上千个用户，并且包括了30多家付费商业用户，横跨了制造，金融，供应链，能源，安防，交通等多个领域。

除了参与公开测评之外，COPT也不断的从商业用户的实际问题中获得成长。这些用户有一部分是本身因美国卡脖子等操作有国产化替代需求，提供给我们算例，我们做针对性的改进以确保在国产化替代时不损失求解性能。另一些则是抱着追赶和学习的态度，结果发现COPT在处理实际问题时，其求解效果在很多场合其实并不落后太多甚至优于国外厂商。

其中某ICT公司国产化替代需求非常紧迫，他们一项的排产排程项目需要求解大量的大规模线性规划松弛问题。历经两年的时间建模求解完成后，又经过半年分别针对三类问题做了轻度的参数调整开发。在该公司内部平台上测试，和Gurobi 9.0进行对比时，求解效果如下表所示：

某ICT公司三类LP算例规模和求解时间对比(求解时间单位：秒)

再如国网某省2020年的时候有一个水火电联合安全约束机组组合优化问题，需要快速的求解MIP问题，客户探索用COPT替代Cplex。由于MIP问题的内在难度，当时我们很难赶上Cplex多年的积累，可以看出直接求解时间Cplex可以在1-2分钟完成，而COPT需要5倍左右的时间。为了不使国产化替代影响求解时间，我们积极探索改进模型，应用了机器学习进行提速改进。此项改进策略下，COPT大幅提升了求解速度，其中COPT在改进后的速度达到或者超过了原始的Cplex求解速度。

某省水火电联合安全约束机组组合优化(求解时间单位：秒)

除了国产化替代等需求之外，也有一些其他的公司尝试了COPT。例如某生活类电商巨头近期对比COPT和他们的Gurobi在一些路线规划求解问题上的整数规划模型求解。从测试结果可以看出，COPT的速度和Gurobi相比非常接近，甚至在部分问题上更快。

某生活类电商巨头公司混合整数规划问题(求解时间单位：秒)

除了服务国内的客户之外，我们也积极探索和国外的厂商合作，拓展国内外市场。老牌建模语言厂商AMPL、GAMS已经主动跟我们联系，并且达成官方协议，由这些厂商官方接入COPT，并将COPT和建模语言打包销售。此外我们和AIMMS、ODH等也在对方主动联系后，展开了合作讨论。其中一家合作方发来的，基于早期版本的邮件非常鼓舞我们(应要求隐去了合作方的名字)

某国外建模语言合作商测试COPT早期版本后发来的邮件

COPT 4.0的申请安装流程极大简化

根据此前申请、安装COPT的一些反馈信息可知，要求用户使用我们提供的工具，同时输入用户名称，MAC地址、CPUID等硬件信息非常繁琐。两年来从我们1000多个累计用户这里，我们也得到了巨大的帮助。深深感受到了国内外运筹从业人员与爱好者对COPT的支持和关注。

为了回馈社区，在准备新版的同时，我们也简化了这一流程和延长了试用时间，用户申请的时候只需提供用户名称，也就是计算机上的username这一项就足够了。同时，我们延长了商业用户试用期限至6个月时间，缩短了申请审核时间至2个工作日。将来会探索学术用户申请试用自动发放的机制。此外我们还准备了安装FAQ页面，会收集整理申请、安装中遇到的问题，及时更新。供大家参考。

求解器这项专业工具，和Office等办公工具不同，它没有一个自己的图形界面。使用求解器一般是从各种编程语言中调用，或者使用命令行工具等。为此提升求解器的易用性，我们也专门提供了C、C++、C#、Python、Java、AMPL、GAMS、Pyomo、PuLP、CVXPY等十余种编程语言接口，以及大量的示例，方便用户上手。

免责声明：市场有风险，选择需谨慎!此文仅供参考，不作买卖依据。

第三十四届CIO班招生
北达软EXIN网络空间与IT安全基础认证培训
北达软EXIN DevOps Professional认证培训

免责声明：本网站（http://www.ciotimes.com/）内容主要来自原创、合作媒体供稿和第三方投稿，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性，但不保证有关资料的准确性及可靠性，读者在使用前请进一步核实，并对任何自主决定的行为负责。本网站对有关资料所引致的错误、不确或遗漏，概不负任何法律责任。
本网站刊载的所有内容（包括但不仅限文字、图片、LOGO、音频、视频、软件、程序等）版权归原作者所有。任何单位或个人认为本网站中的内容可能涉嫌侵犯其知识产权或存在不实内容时，请及时通知本站，予以删除。