这个跻身世界前列的求解器到底是个什么神器 「hypermesh求解器」

使用COPT求解器的命令行工具求解问题 图片由作者提供

求解器像是运筹学里的“芯片”

什么是求解器？

在2018年平昌冬奥会的闭幕式上，中国接棒八分钟展示里出现的无人仓机器人，科技感十足，惊艳了全世界。

如何计算这些机器人的运行路线，确保这些机器人不会相互“撞车”，同时又最有效率，要解决这些问题，需要一个最优算法，依靠的就是求解器。

“在运筹学里，对于数学规划求解器的定义是，针对多种已经建立的线性、整数及各种非线性规划模型，进行算法优化的求解器，可以看作一个‘黑盒子’软件系统。”中国运筹学会理事长、研究员胡旭东告诉科技日报记者，求解器就像是运筹学里的“芯片”，绝大多数复杂系统的决策问题都需要用到数学规划求解器，来寻求最优化的解决方案。

“求解器就好比是电脑的操作系统，解决不同问题的数学模型就是一个个软件。一个求解器可以衍生出很多垂直的场景，尽管这些场景看上去差别很大，但本质上相通。救护车调度、航班规划、库存优化，这些从数据到决策的转化工作，都可以利用运筹学模型与机器学习将实际问题转化为数学模型求解。”胡旭东说。

但是，在过去三十余年中，这种高精度求解器高度依赖进口。

胡旭东表示，而对于各大企业而言，购买商业求解器的最大问题在于价格高昂且无法做针对性调整。

“以国家发展为例，基础设施建设中的电网、水利系统、铁路、高速公路建设等一系列问题都涉及到类似的大规模优化算法问题，使用国际上成熟的闭源商业求解器就意味着难以做出针对性改良，得到最优结果。此外，军事上的战略资源调度、航空领域的战略部署等关乎国家安全问题，也对自主知识产权的软件有着根本性需求。”胡旭东说。

跻身世界顶尖商业求解器之列

“无论从何种角度，这样的软件，国内必须得有自己的核心技术知识积累。”胡旭东说。

如何在短短数年间跻身世界顶尖商业求解器之列？

胡旭东说，求解器在技术层面要求非常高，将一个数学上高度复杂的系统，以百万行级别的代码工程化地实现出来，是国外求解器基本上走了三十年的求索之路。

计算速度的每一点提升都需要无数的思考和尝试，把真正决定速度差异的“坑”一个一个发掘出来，集合了这个领域最顶级的华人，用了三年的时间，杉数科技自主研发成功国内首个商业求解器平台——“杉数数学规划求解器”。

除了时间投入外，人才也成为制约求解器国产化的因素。杉数科技创始人葛冬冬认为，开发求解器需要的人才具备三个特点。

第一是数学功底好，优化算法功底扎实，第二是代码能力强，有系统工程开发能力。第三是最好具有求解器开发经验。

“高校培养的同学，可能最大的问题是学生解决问题的能力能够多方兼顾的不太多，求解器里面有哪些坑，他们不知道。而国内企业培养人才又有点急功近利，等不起一个人才慢慢成熟。”葛冬冬说。

迫切的需求，使求解器的落地应用速度加快。

超大工厂的排产排程问题，往往会面临着庞大的系统之间生产资源和产能的分配和协调，零部件会大到数万种，车间几百个，生产规划又会需要对未来数周精确到小时级别做规划。“我们帮助国内最大的电子通讯设备厂、汽车类企业等都做过类似的事情。”葛冬冬说。

永辉在上海现在已经有300多家店。此前，他们与杉数合作，用选址软件来做智能选址。

“比如，今年计划开50家，明年开100家，后年开150家，利用求解器就就可以算出这50家该怎么开，明年100家怎么开，互相之间不会产生恶性竞争。这就需要求解器把这300家门店做全局优化，做一个线性整合规划系统，然后用软件去算，最后算出来就比较接近于全局优化，而不是只是一个局部的东西。”葛冬冬说。

胡旭东说，电网中的机组组合优化、调度优化、无功优化、现货市场的计算，核心算法都需要求解器来驱动。再比如，航空中机组的日常排班，紧急情况下航班的调整和重新规划，物流中，送货路线和车辆的的调度和规划、多行业中服务人员的日常路线规划等，都是求解器能发挥重要作用的领域。

“求解器国产化的另一个原因是，国产化后，国内的企业可以根据自身的问题进行定制化设计。由于不了解国外求解器系统，此前许多企业遇到许多特定问题时，常常得不到最好的答案，‘黑匣子’永远是封闭的，甚至不知道数据的传输是否安全。国产化求解器，就可以根据企业的特殊问题，进行定制化调整。”胡旭东说。

“国外研究求解器已经有30多年历史，我们才刚刚起步。而我们线性、整数规划，非线性规划求解器基本成型，现在已有三十多项知识产权，计划一两年后达到百项。”葛冬冬说。

“今年，世界知名求解器公测平台米特尔曼的测试网页显示，我国杉数科技的线性规划求解器占据了榜首的位置，其速度已经比第二名快了40%多。”胡旭东说，由美国亚利桑那州立大学汉斯·米特尔曼教授所维护的这一测试网站，提供了多个商业和开源的数学规划求解器的测评数据。这一测评成为了解和选择求解器的窗口，也被求解器业界奉为软件性能排名的事实标准。

来源：科技日报 文中图片除标注外来自网络

编辑：刘义阳

审核：管晶晶