数据魔术师告诉你整数规划COPT5.0离CPLEX还有多远？

COPT5.0：整数规划离CPLEX还有多远？

前言

作为一个长期致力于运筹优化领域研究的团队，我对国产的运筹优化求解器软件的发展非常关注。最近，得知杉数科技即将发布新版的杉数求解器COPT 5.0，我第一时间联系了葛冬冬教授，提前拿到了最新版本。

我最关注的是混合整数规划（MIP）求解器的性能。由于MIP求解器开发难度远远高于线性等其它模块，其应用领域也远多于其它场景，MIP求解器的性能也一直是评估优化求解器的“金标准”。记得世纪初，名声最大的是被IBM收购的CPLEX，其MIP求解性能在工业领域长期一枝独秀，在我们接触到的国企和外企里使用者很多，并拥有大量粉丝。2008年，从CPLEX团队离职的三位核心开发人员共同创办了GUROBI，经过十多年的发展，其计算性能后来居上，也积攒了很多用户。

由美国亚利桑那大学Hans Mittelmann教授维护的优化软件测评榜单是国际公认的优化求解器测评平台。我注意到杉数的MIP求解器自从去年上榜以来，性能一直在提升。从COPT 2.0版到最新的COPT 5.0版，相对第一名GUROBI的求解时间不断改进，比率已经从5.17提高到了2.34。在MIP测评榜单上一直处于第二名的位置。

正如杉数科技一直说的，我们国产的MIP求解器实际上还没真正拿到第二的位置。这是由于上文提到的CPLEX，以及FICO的XPRESS，当时的老二老三，于2018年退出了测评，这让人难以将COPT和CPLEX这一广泛使用的MIP求解器做详细对比。

我一直很好奇CPLEX和COPT的水平到底如何？是否还是有很大差距？

正好，作为高校教师，我们有CPLEX 最新版本的使用授权，我的团队也有个工作站，跟Mittelmann教授测评使用的同款（Intel i7-11700K CPU，64G内存），因此我这次迫不及待地做了一个测试。测试虽然非官方，但是也是在尽量公平和按照Mittelmann教授的测试环境和标准来进行，希望可以把这一缺失的信息补上，供运筹优化领域内的同行参考。

我们在自己的机器上快速地跑了跑COPT 5.0版本在MIPLIB 2017的部分问题，和Mittelmann教授测试的结果基本一致（误差上下浮动基本在1～2%）。因此我将直接使用Mittelmann教授提供的COPT 5.0和GUROBI 9.5版数据。我们自己使用的CPLEX版本是2022年初发布的22.1版。我们首先测试了MIPLIB 2017 Benchmark整个算例集。该算例集共有240个算例，反应MIP求解器的综合实力。在该算例集上的测评结果为：

MIPLIB 2017 Benchmark 测评

按照Mittelmann教授的标准，测评中每个算例允许的求解时间上限为2小时，表格中“求解数量”为该时限内正确完成求解的算例数。“平均求解时间”是各个求解器在全部240个算例上的移动几何平均求解时间，单位为秒，若未完成求解则按照7200秒上限计算。“相对求解时间”是各求解器平均求解时间除以第一名的结果。从测评结果可以看出，无论是可解数量还是平均求解时间，Gurobi还是处在领先地位的。当然COPT与其差距已经快速地缩小了。

在分析对比时，比较吃惊地发现是COPT 5.0和最新版的CPLEX的差距已经非常的小。相对求解时间仅为1.27。这可以理解为COPT在求解常见的MIP问题时，速度比CPLEX仅慢27%！这是我意想不到的结果！

更吃惊的是，我也测试了Infeasibility Detection for MILP Problems这个算例集。这个算例集有32个无可行解的算例，考察的是证明MIP不可行的速度。在该算例集上的测评结果为：

Infeasibility Detection 测评

从测评结果可以看出，在检查MIP问题是否可行方面，COPT已经大步超过了CPLEX，快54%！这结果简直让我震惊了！

当然5.0其它的部分我没有去测，据说其它模块也有全面的改进。其实线性部分很早之前COPT已经遥遥领先，多数时间都是霸榜第一的状态，上次我们团队内部的测试基本比CPLEX快了两三倍。所以已经没有太大的比较意义了。这次COPT贡献了一个新模块SDP，把原来的老大MOSEK直接打到了慢一倍多，出手真够狠的……

结论

综合以上的测评可以看出。杉数的MIP求解器在部分领域已经超过了CPLEX，整体性能上基本接近。根据过去这一年多来的观察，我相信杉数求解器的性能全面超过CPLEX指日可待。在那之后，国产MIP求解器的追赶目标就是GUROBI了。

我把最高的敬意献给他们

COPT团队，加油吧，少年