.

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

                            

科技日报记者马爱平

几百家便利店应该如何选址,才能覆盖尽可能多的人口?

几百个物流机器人的行进路线该如何实时设计,才能效率最高又不发生碰撞?

在打车系统中当乘客发出要车请求,把这位乘客分配给哪个司机,是选择区域最优,分配给离得最近的实际,还是还是做到动态最优?

在已知未来几个小时,会有一场演唱会结束,可以预见演唱会周围的地区的用车需求会增加,那么现在的这个乘车请求,在整个城市范围内如何通过决策实现一个均衡状态,让所有人的满意度尽可能地最大化?

……

这些问题的解决可能需要一个大的动态规划系统来建模,而最后的求解,往往需要近似求解一个线性整数规划来逼近。求解器就提供了这样的一个计算系统。

而问题求解规模越大,就越依赖求解器,因此物流交通、电网、航空、金融等行业中有大量核心算法更高度依赖求解器这一神秘“黑匣子”。

日前,我国自主研发的杉数数学线性规划求解器在知名第三方测评网站亚利桑那大学米特尔曼教授的测试集上位列第一,成为我国第一个自主研发的商业级别求解器,我国求解器的测试速度跻身世界顶尖商业求解器之列。

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

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

什么是求解器?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

原标题:《这个跻身世界前列的求解器到底是个什么神器?》

    


转载请注明:http://www.abachildren.com/hbyx/5025.html