科技焦点网

新增混合整数二阶锥规划和凸二次规划求解,杉数求解器COPT 6.0正式发布

2022-11-03 10:54   来源: 互联网

2022年10月底,杉数科技正式发布优化求解器COPT 6.0。杉数求解器COPT 6.0增加混合整数二阶锥规划MISOCP和混合整数凸二次(约束)规划MIQ(C)P求解功能,以及增加了参数调优工具,大幅提升半定规划求解性能。

混合整数二阶锥规划求解器

自从2021年10月杉数求解器COPT 3.0版推出二阶锥规划(SOCP)以来,其求解性能比肩国际先进厂商,同时为了支持设定整数变量,实现在金融、能源、化工等领域的国产化替代。历经一年研发,杉数科技正式推出混合整数二阶锥规划(MISOCP)求解器。

COPT 6.0混合整数二阶锥规划求解性能测评结果

据美国亚利桑那大学Mittelmann平台公布的测评榜单数据显示,MISOCP测评榜单上共有四款求解器。除新杉数优化求解器COPT外,其中Mosek和Gurobi分别是来自丹麦和美国的老牌商业求解器厂商,SCIP是德国ZIB研究所发布的开源求解器。测试表里求解器名称上方的数据为一个求解器求解所有测评算例的相对平均时间,以平均时间最小的为1,而下方的数字是可成功求解的算例数量。

从测评榜单可以看出,COPT新发布的混合整数二阶锥规划求解性能超越了开源的SCIP和老牌商业厂商Mosek,平均求解时间和可成功求解的算例数量均明显优于这两个软件。同时我们注意到,和美国厂商Gurobi相比,COPT的平均求解时间还有一定的差距,且限定时间内可求解的数量也少1个,仍有提升空间。

但是COPT和Gurobi相比也有自己的优势,Gurobi的求解数量旁边加了个*号,Mittelmann教授在页面的最底部解释说“* 27 instances with constraint violations > 1e-6”,也就是说有多一半的算例,Gurobi尽管成功求解,但是解并不满足算例的约束条件,换言之那不是严格意义上的可行解。

混合整数凸二次(约束)规划求解器

和二阶锥规划紧密相关的两类数学规划问题是凸二次规划(QP)和凸二次约束规划(QCP)。鉴于其紧密联系,杉数科技在开发整数二阶锥规划同时也开展了混合整数凸二次规划(MIQP)和混合整数凸二次约束规划(MIQCP)的研发,于COPT 6.0一并发布。

COPT 6.0混合整数凸二次(约束)规划求解性能测评结果

在Mittelmann测评榜单中,混合整数凸二次规划和整数凸二次约束规划的求解性能比对放在了同一个测评项目Convex Discrete QPLIB里。在这个榜单上,杉数求解器COPT6.0取得非常好的成绩。和老牌求解器Gurobi相比,可正确求解的数量同为24个,而COPT的平均求解速度领先43%!这是一个标志性的成果,这是我们第一次在混合整数规划的领域超过欧美主流求解器!

半定规划的求解能力大幅提升

自从今年6月COPT 5.0推出半定规划(SDP)求解器以来,由于性能优势受到来自国内外学术界和商业界的广泛关注。杉数也在该求解领域,进一步提升COPT半定规划的求解性能。

COPT 6.0半定规划求解性能测评结果

从Mittelmann测评榜单上可以得出,新发布的COPT 6.0实现了全部75个问题的正确求解,且求解速度也明显提升,和COPT 5.0相比,COPT 6.0相对Mosek 10.0的速度领先优势从64%扩大为254%。

参数调优工具

除了求解功能之外,COPT 6.0增加参数调优工具(tuner) 新功能。参数调优是使用求解器时的一项常见操作,尤其是在求解混合整数规划(MIP)时非常重要。COPT混合整数规划求解器实现了多种启发式、割平面算法。有时候对某个问题,往往某个割平面多多益善;而对另一个问题,可能全靠某一种启发式算法寻找最优解。尽管我们在开发求解器时,已经充分参考公开和客户算例,设定了各类启发式算法和割平面算法的最佳强度等参数。但这很难做到兼顾所有的情况。因此在面对某一特定类别的混合整数规划问题的时候,往往需要调参数,实现最佳求解效果。杉数科技过去帮助很多客户通过专业知识调参数,找到了最合适参数。而在COPT 6.0,我们推出用户可以自行使用的自动参数调优工具。例如求解MIPLIB 2017中的app1-2这个算例,根据Mittelmann测试榜单中MIPLIB的详细对比可知,COPT 6.0默认需要166秒才能完成求解,尽管明显比其他开源求解器的10-20分钟快,但是依然落后于Gurobi的19秒求解时间。通过使用工具,我们可以找到一组改进参数。

参数调优工具针对app1-2这个算例找到的一组改进参数

这组参数调低了割平面的强度,关闭了启发式算法和预求解模块,还适当增加了分支定界部分的割平面强度,最终实现了18.4秒求解这个算例,提升幅度超过8倍。有关参数调优工具的各种参数,如提升调参稳定性的TunePermutes和设定调参目标的TuneMode等,请参考COPT的文档试用。此外我们后续会在杉数运筹与智能决策教学平台https://coridm.d2d.ai/的COPT求解器教程专区推出参数调优工具的视频使用介绍。敬请关注。

关于杉数优化求解器COPT

杉数求解器COPT (Cardinal Optimizer),是杉数自主研发的针对大规模优化问题的高效数学规划求解器套件,也是支撑杉数端到端供应链平台的核心组件。COPT是目前同时具备大规模混合整数规划MIP、线性规划LP、半定规划SDP、(混合整数)二阶锥规划(MI)SOCP、以及(混合整数)凸二次规划Convex (MI)QP和(混合整数)凸二次约束规划Convex (MI)QCP问题求解能力的综合性能数学规划求解器,为企业应对高性能求解的需求提供了更多选择。

COPT支持所有主流操作系统,如Windows、MacOS、Linux (包括苹果自研芯片和arm64芯片)。您可以从多种语言及建模工具使用COPT,包括基于数据的C语言接口,面向对象的Python、C++、C#、Java接口,以及AIMMS、AMPL、GAMS、Julia、Pyomo、PuLP、CVXPY等第三方建模工具。

此外COPT支持多种部署方式。除了个人电脑、服务器之外,我们还提供浮动授权和计算集群等部署方式,方便学校实验室和公司生产环境等场景的使用。欢迎通过杉数科技官网(shanshu.ai/copt)申请免费的个人试用版本。如需试用服务器版、浮动授权或计算集群版本,请与我们取得联系coptsales@shanshu.ai。


责任编辑:Linda
分享到:
0
【慎重声明】凡本站未注明来源为"科技焦点网"的所有作品,均转载、编译或摘编自其它媒体,转载、编译或摘编的目的在于传递更多信息,并不代表本站赞同其观点和对其真实性负责。如因作品内容、版权和其他问题需要同本网联系的,请在30日内进行!