1.85 数据魔术师告诉你整数编程COPT5.0距离CPLEX还有多远？

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

前言

作为一个长期致力于运筹学和优化领域研究的团队，我非常关注国内运筹学优化求解器软件的发展。近日，获悉山数科技即将发布山数求解器COPT 5.0新版本。我立即联系了葛东东教授，提前拿到了最新版本。

我最关心的是混合整数规划 (MIP) 求解器的性能。由于MIP求解器的开发难度远高于线性等其他模块，而且其应用领域也远超其他场景，因此MIP求解器的性能一直是评价优化求解器的“金标准”。记得世纪初的时候，最著名的就是CPLEX，后来被IBM收购了。其MIP求解性能长期以来在工业领域表现突出。它在我们接触到的国企和外企中有很多用户1.85，拥有大量的粉丝。它由从 CPLEX 团队辞职的三名核心开发人员于 2008 年共同创立。经过十多年的发展，其计算性能已经超越后来者，也积累了众多用户。

由亚利桑那大学教授维护的优化软件评估列表是国际公认的优化求解器评估平台。我注意到，山书的MIP求解器自去年上市以来，性能一直在进步。从COPT 2.0版本到最新的COPT 5.0版本，求解时间相对之一名不断提高，比值从5.17提高到2.34。一直在MIP评测榜上排名第二。

正如杉树科技一直说的，我们国产的MIP求解器实际上还没有达到第二的位置。这是因为上面提到的 CPLEX，以及当时第二、第三老的 FICO 在 2018 年退出了评估，这使得 COPT 和广泛使用的 MIP 求解器 CPLEX 之间很难进行详细比较。

我一直很好奇CPLEX和COPT的水平如何？差距还很大吗？

巧合的是，作为大学教师，我们拥有使用最新版本CPLEX的许可证。我的团队也有一台工作站，和教授评估时使用的型号相同（Intel i7-CPU，64G内存），所以这次我迫不及待地做了测试。虽然测试是非官方的，但它是尽可能公平地、按照教授的测试环境和标准进行的。希望这些缺失的信息能够被运筹学和优化领域的同行们补充参考。

我们很快在自己的机器上运行了2017年COPT 5.0版本的一些问题，结果与教授的测试基本一致（误差在1%到2%之间波动）。因此我会直接使用教授提供的COPT 5.0和9.5版本的数据。我们自己使用的CPLEX版本是2022年初发布的22.1版本。我们首先测试了整个2017年的示例集。本计算算例集共有240个计算算例，体现了MIP求解器的综合实力。该计算算例集的评估结果为：

解算器名称

9.5

复合体22.1

科普5.0

求解数量

224

206

195

平均求解时间

91.39

168.65

214.04

相对求解时间

1.00

1.85

2.34

评估

按照教授的标准，评估中每个计算例允许的解题时间上限为2小时。表中的“解数”是指在限定时间内正确解出的计算例数。 “平均求解时间”是每个求解器在所有 240 个计算实例上的移动几何平均求解时间，以秒为单位。若未解完，则按照上限7200秒计算。相对求解时间是每个求解器的平均求解时间除以之一名的求解器。从评测结果可以看出，在求解数量和平均求解时间方面仍然处于领先地位。当然，COPT与COPT之间的差距已经迅速缩小。

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

更令人惊讶的是，我还测试了MILP的计算示例集。本套计算算例有32个无可行解的例子，测试的目的是考察证明MIP不可行的速度。该计算算例集的评估结果为：

解算器名称

9.5

复合体22.1

科普5.0

求解数量

平均求解时间

12.07

24.45

16.83

相对求解时间

1.00

2.03

1.39

评估

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

当然5.0的其他部分我没有测试过。据说其他模块也得到了全面改进。事实上，在线性部分，COPT 长期以来一直遥遥领先，并且大部分时间都占据了榜单的主导地位。我们团队上次内部测试基本上比CPLEX快两三倍。所以已经没有太大的比较意义了。这次COPT贡献了一个新模块SDP，直接把原来的老大MOSEK打败了两倍以上的速度。实在是太无情了……

综上所述

从上面的评价就可以看出。的MIP求解器在某些方面已经超越了CPLEX，整体性能基本接近。根据我过去一年多的观察，我相信在不久的将来，求解器的性能将超越CPLEX。此后，国产MIP求解器的目标就是迎头赶上。

我向他们致以更高的敬意

COPT 团队，加油，男孩