望京留创园在园企业杉数科技继6月发布C轮融资、COPT2.0整数规划求解器升级喜讯后再次迎来佳绩！杉数求解器第三个大版本COPT 3.0版于2021年10月1日国庆节正式发布。
混合整数规划（MIP）的求解性能有了大幅度提升，在用户端给许多用户带来了2~3个数量级的速度提升。
从综合测评信息对比来看，线性规划（LP）求解器的综合性能依然雄踞世界第一。
往期喜讯回顾：企业喜讯｜望京留创园在园企业杉数喜迎2亿C轮融资、整数规划求解器双发布！
（下文出自杉数科技官方公众号）
▼
金秋时节，望京留创园在园企业杉数科技于国庆节前完成了开发和内测，特地选在10月1日进行打包，也是开发组的“小心思”，想在求解器日志里留一个有意义的时间戳为祖国庆生。
回想起2019年5月28日的COPT 1.0版本发布，当晚完成了单纯形法测评，取得第一；随后开放免费试用，揭开了中国商用求解器的大幕。如今COPT 3.0的发布，前后共花了六天时间才完成全部测评，共登上了七个榜单。COPT在提升速度的同时也在默默地扩展求解能力的广度，如本文将介绍的随COPT 3.0首次发布的SOCP求解器。此外，本文也将介绍COPT的MIP求解器近期的性能提升及在解决部分客户问题时从百倍到千倍的速度飞跃。本文最后将综合公开测评数据，对比分析单纯形法和内点法、探讨线性规划（LP）求解器的性能。
▶ 第一个国产商业SOCP求解器发布：二阶锥求解器
这次COPT2.0实现大版本升级至COPT3.0，主要原因是首次发布的二阶锥（SOCP）求解器，这是第一个国产的商业SOCP求解器。二阶锥规划在金融领域有着广泛的应用场景，此外，如二次规划问题（QP）也可以转化为SOCP求解。
根据Hans Mittelmann测评结果，COPT 3.0的SOCP求解器位列第三
SOCP求解器的开发是一项综合性的工程。杉数改进了底层的Cholesky分解算法、实现了高效的SOCP内点法核心算法、针对SOCP的特点拓展了预求解模块、设计了简明易用的用户建模接口、此外还提供了多种建模语言的使用示例。
在测评榜单上，COPT的SOCP求解器能力暂居第三。Mosek和Gurobi经过了数十年的打磨和调优，而杉数也正在新时代的浪潮中迎头赶上。目前杉数正在开发下一个版本其实性能已经有了很大改进，相信在下一次发布时，会有明显的提升。
▶ MIP速度提升19.6%，进击世界前三
混合整数规划（MIP）求解器一直是运筹优化领域皇冠上的明珠。在实际应用场景中，有80%左右的客户申请COPT是为了使用MIP求解器。在公开测评榜上，没有任何求解器可以求解全部240个问题（每个问题两小时时间限制）。相比于其他榜单比速度，MIP求解器关注的更多的是在两个小时内的求解数量。
根据Hans Mittelmann测评结果，COPT的MIP求解器速度排名第二（单线程结果为COPT 2.0的数据，现在单线程测评已经停止更新）
相比于2021年5月底发布的COPT 2.0版，经过四个月的开发COPT 3.0在MIPLIB 2017的求解数量从164个增加为176个。相对于Gurobi的速度从5.41提升为4.52，提升19.6%。
此外，为了提供一个明确的性能对比，杉数把各个参与（过）测评的求解器的可解数量放在一起比较（Cplex、Xpress和SAS-OR选择了他们最后的测评数据）。可以看到COPT 2.0版已经超过了原来位居第4的SAS-OR。而COPT 3.0距离Xpress的最后公开测评数据仅差4个。三大厂，杉数来了！
MIPLIB 2017可求解数量比较（加*号为退出测评前的最后数据）
除了参与公开测评，进行“打榜”之外，杉数在日常开发中也解决了许多实实在在的客户问题。
例如某航空公司提供的算例，COPT的求解速度从2小时无法算出提升为11分钟左右完成求解；某交通运输行业混合整数规划要求快速算到1%的gap，COPT的求解速度从近一小时下降到4分钟之内。这两项的求解效率改进得益于求解器的全方位改进，速度提升均在10倍以上；又如某ICT巨头提供的算例，由于COPT 3.0的启发式算法的改进，求解速度从2小时以上降低为3分钟以内，速度提升超过25倍；还有如某食品公司遇到的实际问题，部分算例极其复杂。通过仔细研究，杉数发现了不存在于公开算例集的预求解改进方向，在新版本中分别将原本需要半小时求解的问题和两小时算不出的问题，分别提升至15秒和3秒完成求解，提速超过1000倍！像这样的例子还有很多……这些实例也再次证明，COPT的MIP求解功能在3.0版本中已实现实质性的效果提升！
COPT 3.0在求解部分用户问题时性能大幅提升
▶ LP求解能力世界第一
除了SOCP的发布和MIP的改进，杉数也改进了COPT的线性规划求解器，包括单纯形法求解器和内点法求解器。杉数注意到国内厂商近期也发布或者更新了线性规划求解器。下文将对比分析单纯形法和内点法两种求解方式，分析线性规划求解器的性能。
早在1940年代提出的单纯形法（Simplex）的求解原理是顺着LP问题的可行域边界逐步改善，从一个顶点走到另一个目标函数值同等或者更好的顶点，直到目标函数值无法再改善，即找到最优解为止。Simplex求解时往往需要较多的循环步数，需要的循环数通常和问题的规模成比例，但是每个循环耗时相对较少。
后来在1980年代内点法（Barrier）的基本原理是在LP问题的可行域内部逐步向最优解迭代靠近。Barrier求解时往往需要的循环步数较少，在几十到上百循环之间，但是每个循环耗时相对较多，每个循环的耗时通常和问题的规模成比例。此外，指出的是，当Barrier完成计算的时候，会停在LP可行域的内部。而在实际的应用，如继续求解MIP问题等场景，则通常需要一个顶点解。此时求解器会使用Crossover算法把内点解转化为顶点解。由于求解LP问题时普遍需要顶点解，因此Crossover算法的时间也算在内点法之内。
Hans Mittelmann教授所维护的LP测评榜共有Simplex和Barrier两个榜单。其中Simplex榜单共选择了40个算例，而Barrier榜单则选择了47个算例，其中包含单纯形法榜单的全部40个算例。这种算例的重合给杉数提供了一个横向对比所有主流厂商所提供的LP求解器的可能性。
国内外厂商的Simplex和Barrier的求解性能横向对比
从上图国内外求解器厂商的单纯形法和内点法的横向对比来看，不难得出在求解同样的问题集时，Gurobi、COPT和MindOpt的内点法均优于各自的单纯形法实现。其中COPT的内点法明显优于其他所有厂商的任意求解器。
杉数科技在此处也做了一个很有说服力的比较，把各个厂商在求解40个共同算例的每个问题使用Simplex和Barrier的最佳表现抽取出来，再做比较。这样的比较显然体现了各个求解器在线性规划上的最佳能力，在这项比较中，COPT的线性规划求解能力也明显优于其他求解器，可以称之为当之无愧的世界第一。
国内外厂商的最佳LP求解性能横向对比
另外杉数科技也做了一个很有意思的比较，将各个求解器的最佳表现综合抽取出来，单独一列(best of all)。可以看出，COPT与之还有15%的差距，这也是杉数未来的努力方向！
未来，望京留创园将始终践行国家创新驱动发展战略，从综合型孵化器向专业孵化器转型，专注数字经济为基础的信息技术产业，利用数字技术推动在孵企业融入产业链，围绕产业链实现资源整合、服务集成和企业融通发展，建立千企千面的产业协同供需体系和服务生态，为更多的优秀新兴产业提供优良的孵化培育平台和定制化、专业化、创新型的数字孵化平台！愿越来越多的企业加入望京留创园，我们愿伴您一路成长，加速腾飞！让智慧在望京创造财富，让理想在望京成为现实！
