科技日报记者马爱平
数百家便利店应该如何定位,以覆盖尽可能多的人?
如何实时设计数百个物流机器人的行进路线,达到最高效率而不发生碰撞?
在出租车系统中,当乘客发出要车请求时,分配给乘客的是哪个司机,是所选区域中最好的,分配给最近的现实,还是动态优化?
据了解,未来几个小时将有一场音乐会,可以预见,音乐会周边地区的汽车需求将会增加。那么如何通过整个城市的决策来平衡目前乘坐公交车的要求,让大家的满意度尽可能的最大化呢?
……
这些问题的求解可能需要一个大型的动态规划系统来建模,最终的解往往需要用一个线性整数规划来近似。求解器提供了这样的计算系统。
问题解决的规模越大,就越依赖解决者。因此,物流、交通、电网、航空空、金融等行业的大量核心算法都高度依赖于这个神秘的“黑箱”。
近日,国内自主研发的杉数数学线性规划求解器在知名第三方评测网站亚利桑那大学Mitelman教授的测试集中排名第一,成为国内自主研发的首个商用级求解器。中国解算师的测试速度位居世界商业解算师前列。
使用COPT求解器的命令行工具解决问题。图片由作者提供
求解器就像运筹学中的“芯片”
什么是求解器?
2018年平昌冬奥会闭幕式上,无人仓库机器人亮相8分钟的中国接棒展,科技感十足,惊艳全球。
如何计算这些机器人的运行路线,确保这些机器人不会相互“撞车”,同时效率最高。要解决这些问题,需要一个优化算法,依靠求解器。
“在运筹学中,数学规划求解器的定义是,对各种已建立的线性、整数和各种非线性规划模型进行算法优化的求解器,可以看作是一个‘黑箱’软件系统。”中国作战计划学会理事长、研究员胡旭东告诉科技日报记者,求解器就像运筹学中的“芯片”,复杂系统的大多数决策问题都需要用数学规划求解器来寻求最优解。
“Solver就像计算机的操作系统,解决不同问题的数学模型都是软件。许多垂直场景可以从解算器中导出。虽然这些场景看起来很不一样,但本质上是一样的。救护车调度、飞行计划和库存优化,所有这些都可以通过使用运筹学模型和机器学习将实际问题转化为数学模型。”胡旭东说。
然而,在过去的三十年里,这种高精度求解器高度依赖进口。
胡旭东说,对于大企业来说,购买商业解决方案最大的问题是价格高,无法进行针对性调整。
“以国家发展为例,电网、水利系统、铁路、高速公路建设等基础设施建设中的一系列问题,都涉及到类似的大规模优化算法。使用国际上成熟的闭源商业求解器,意味着很难进行针对性的改进,获得最佳效果。此外,航空领域的军事战略资源调度和战略部署空关系到国家安全问题,对具有自主知识产权的软件也有根本性需求。”胡旭东说。
位列世界顶级商业解决者
“无论从什么角度来看,这样的软件在国内都必须有自己的核心技术知识积累。”胡旭东说。
如何在短短几年内成为世界顶尖的商业解决者之一?
胡旭东说,解算器对技术水平有很高的要求,国外解算器实现数百万行代码的数学复杂系统已经是30年前的事情了。
计算速度的每一次提升,都需要无数的思考和尝试,把真正决定速度差异的“坑”一个个挖出来,把这个领域的顶尖中国人聚到一起。三年间,山书科技自主研发了国内首个商用求解器平台——“山书数学规划求解器”。
除了时间投入,人才也成为制约解决者本土化的因素。山书科技创始人葛冬冬认为,培养解决者所需的人才有三个特点。
一是有良好的数学和优化算法基础;二是具有较强的代码能力和系统工程开发能力。第三,最好有规划求解开发经验。
“对于在高校培养的学生来说,最大的问题可能就是学生解决问题的能力不过分,不知道解算器里有什么坑。但是国内企业在培养人才上有点急功近利,不能等一个人才慢慢成熟。”葛冬冬说。
迫切的需求加速了规划求解器的落地应用。
超大型工厂的调度问题往往面临着生产资源和生产能力在庞大系统之间的分配和协调,拥有上万个零件和数百个车间,生产计划需要在未来几周内制定到小时级别。“我们已经帮助中国最大的电子通信设备厂和汽车企业做了类似的事情。”葛冬冬说。
永辉在上海有300多家门店。此前,他们与山书合作,用选址软件做智能选址。
“比如,计划今年开50家,明年开100家,明年开150家。使用求解器,您可以计算出如何打开这50个家庭,以及如何在明年打开100个家庭,而不会出现它们之间的恶性竞争。这就需要求解器对这300家门店进行全局优化,做一个线性集成规划系统,然后用软件计算出来。最后,它更接近全局优化,而不仅仅是局部的事情。”葛冬冬说。
胡旭东表示,电网中机组组合优化、调度优化、无功优化、现货市场计算等核心算法都需要求解器驱动。比如航空空中机组的日常调度,紧急情况下航班的调整和重新规划,物流中配送路线和车辆的调度和规划,多行业服务人员的日常路线规划,都是求解器可以发挥重要作用的领域。
“解决器国产化的另一个原因是国产化后,国内企业可以根据自己的问题进行定制设计。由于不了解国外的求解器系统,很多企业在遇到很多具体问题时,往往得不到最好的答案。“黑匣子”总是关着,他们甚至不知道数据传输是否安全。本地化解决方案可以根据企业的特殊问题进行定制。”胡旭东说。
“国外对求解器的研究已经有30多年的历史,我们才刚刚起步。我们的线性、整数规划和非线性规划求解器已经基本成型。现在有30多项知识产权,计划一两年达到100项。”葛冬冬说。
“今年全球知名求解器公测平台Mitelman的测试页面显示,中国山书科技的线性规划求解器占据榜首位置,其速度已经比第二名快了40%以上。”胡旭东说,这个由美国亚利桑那州立大学的汉斯·米特曼教授维护的测试网站提供了几个商业和开源数学规划者的评估数据。这种评估已经成为理解和选择求解器的窗口,也被求解器行业视为软件性能排名的事实标准。