杉数于过年期间发布了COPT 7.1版本，新增了能在GPU上运行的LP求解器，我年后复工第一时间便要来尝鲜。看到能在GPU上丝滑运行，求解很多此前无法求解的超大LP问题，不得不感慨杉数总能带来惊喜![]()
![]()
![]()
。
其实我一直以来主要关注的还是MIP问题，去年底遇到了几个实际问题用COPT求解比Gurobi慢，我问COPT团队的葛冬冬老师如何提速。葛老师给我推荐了COPT自带的调参器。我先试了手头的一个小问题，通过几分钟的时间，调参器找出了能从15秒提升到8秒的参数组合。在另一个大规模的问题上则是花了一晚上，找出的参数组合可以从默认1小时解不出提升到300秒之内完成求解。对于这个结果，葛老师解释说：这是由于MIP求解器内的各种启发式和割平面等模块实在是太多了，开发求解器时很难把每个模块的状态都调到最优。如果给全部的模块都开到最大强度，那些不起作用的模块就会拖慢整体的求解速度；反之如果降低强度则又可能影响求解效果，例如减少割平面的数量或轮次，则可能影响MIP的对偶边界的收敛速度。因此商业求解器一般的做法是将启发式、割平面以及预求解等强度预先设置在一个较为“适中”的程度，通过调参数来找到针对客户问题的最佳配置。由于客户模型往往结构相同，只是规模上有区别，或者是每次求解数据不太一样，因此对同一个客户来说，往往一套参数能用很长时间。在MIP领域调参数是将求解器和实际模型适配的一个重要步骤。听完了葛老师的解答，我忍不住问了个略显刁钻的问题：那MIP打榜的240个算例，是不是也能通过调参找到更好的参数呢？杉数是不是已经给每个问题都调到最优了？葛老师告诉我说：按照通行惯例，COPT和国际几个大的求解器都没这么做，也是大家默认竞争的一个基础。通过打榜是想展示求解器面对客户问题的真实实力，而不是每个MIP问题都调到最优的结果。其实一些其他厂商一直以为国产求解器打榜就是这样做的，但我们是真的没有。不信拿COPT调参器试试看就知道了。听了这番话，我刻意选了一个MIPLIB榜单里面，COPT已经是最快的算例co-100来试试看。根据Hans Mittelmann教授测评榜单的信息：COPT求解这个问题需要166秒，而Gurobi需要292秒，所有其他求解器均需要10分钟以上。结果COPT的调参器花了不到两个小时，便找出了改进参数HeurLevel=0和 TreeCutLevel=3。在和Hans Mittelmann同配置的台式机上 (配置为Intel 11700K，64G内存)，COPT的求解时间从166秒缩减到了121秒，速度提升达37%之多。葛老师说有这个结果一点都不奇怪。因为一个正常的MIP求解器就是这样，针对每一个具体问题，调调参数往往都能找到更好的选择。他进一步说：其实杉数内部会每隔一段时间都会对收集到的算例进行一次调参，看看能不能从调参数的结果中发现一些可以解的更快的客户问题，以及辅助研究如何更优化的配置各项算法的默认强度等。葛老师说最近一次大规模的调参数正是春节假期，其中MIPLIB测评集上240个问题，有80%都能找到比默认更好的参数。我有点不太敢相信，便问葛老师把这套参数要来，在我的和Mittelmann同配置的台式机上验证了一下。可能由于使用了最佳参数，一个周末就全验算完了。我统计了结果，惊讶的发现，调参后的版本，不仅比榜单上的默认版本能多求解5个算例，平均求解时间更是从103.8大幅下降到了62.6，快于gurobi榜单上的72.1，求解速度领先达15.2%！！这真是太难以置信了！！(完整的求解时间和改进参数有兴趣的读者可以联系我或者葛老师)![]()
MIPLIB 2017 测评集5个COPT 7.1通过调参能解出的算例
再一步提升求解能力
葛老师开玩笑的说，如果我们也claim一个机器学习嵌套的求解器，用这个作弊的话，很容易就显得比Gurobi好的挺多了，似乎就世界第一了，其实意义不大。COPT和Gurobi、Cplex、Xpress现在大家都还是处在一个良性竞争的环境，大家互相竞争，也默守着这些不成文的规定。面对我的惊讶，葛老师却告诉我说：其实这个只是调了十余个相对宏观的公开参数的结果。如果允许调其他上百个未公开的参数，则总体效果会更上一个台阶。他说：比如就割平面而言，公开的参数一共有三个CutLevel、 RootCutLevel 和 TreeCutLevel，分别用于指定全局，根节点和分支定界时的割平面强度。然而，COPT内部有几十种割平面可供选择，如果一个问题通过调割平面能把求解器速度调快，那完全可以进一步只选出那些起作用的割平面算法，关闭不起作用的，这样还能更快。同理，百种启发式算法，和几十种不同的预求解模块也各有单独的参数控制其强度和开关，这些都可以更深入的调整。杉数在拿到客户算例时，一般都会协助精调这些参数，帮助客户把求解器和模型适配到最佳状态。![]()
葛老师来了兴致，他继续说：你看Gurobi默认可以求解229个问题，而我们默认能求解220个，调参数版能解出225个。实事求是的说，COPT和对方还是有一定差距的，总还是有一部分问题，Gurobi能较快解的出，我们调参数也很吃力。这种时候我们就会组织开发的力量集体攻坚。目前看来，都能搞定。最近一年需要解决的客户问题比较多，不太有时间关注MIPLIB榜单。但是我们发现解决了客户的实际问题时，最终新增的模块或者改进后的算法实现，往往对MIPLIB这样的榜单又有速度提升的帮助。这属于是无心插柳了。当然也不是所有的客户都愿意分享他们的算例，有些客户尤其是国外客户，拿COPT和现在用的其他国外商业求解器一比，发现COPT慢也往往不联系我们协助调参。针对这种情况，我们也在想办法，比如目前我们正在研究如何通过机器学习的办法，针对实际问题，预先推荐一套参数，让COPT默认就能跑的更好。这项工作其实还挺有挑战性的，我们也欢迎感兴趣的同行一起参与，期盼机器学习领域的专家能加入到这项工作中来。他在上海交大刚成立的智能计算研究院团队，将和叶荫宇，何斯迈等著名学者一起，攻坚GPU大规模加速、机器学习和优化算法融合、以及大模型的建模决策路径等前沿问题，也欢迎有志于此方向的年轻学子报考他们的博士（今年秋天就可以入学）。
