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

科技日报记者 马爱平

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

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

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

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

……

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

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

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

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

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

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

什么是求解器?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编辑:刘义阳

审核:管晶晶

主题测试文章,只做测试使用。发布者:觉鸟网,转转请注明出处:https://www.jueniao.cn/n/21337.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022年6月13日 10:54
下一篇 2022年6月13日 10:56

相关推荐

  • 嵌入式人工智能—机器学习以“生态+集成+定制”差异化发展

    随着嵌入式处理器的能力不断提升,超小型化的硬件加速器不断被引入,以及原厂及商业的开发环境和工具不断出现,嵌入式人工智能/机器学习(AI/ML)技术在近几年得到了快速的发展。同时因为这些技术与千姿百态的各种应用需求十分贴近,因此正在进入差异化发展的新空间,未来其增长速度将可以比肩甚至超过需要强大资源体系的、立足良好通信条件的和基于云的人工智能应用。 人工智能并…

    智能科技 2022年6月17日
    3800
  • 进化了百年的洗车机到底哪种才是王道?

    近日,不断接到各种咨询,现在市面上存在的洗车机种类繁多,求解到底哪种才是最符合实际需要的产品?在此小编从专业设备制造以及产品应用的角度,分享一下观点: 如今,世界上主流洗车机产品从洗车方式上主要分为三大类 从洗车方式 分三大类 ①隧道式 隧道式洗车机,一直保持全自动洗车机雏形时流水线作业的形态,可以实现高效连续洗车,采用滚轮轨道传动,可以实现1小时可洗/50…

    2022年6月17日
    3700
  • 奇遇DreamProVR设备仅2499元,打卡300天保底返3000元,倒赚?

    虽然在商场中经常就能见到有售卖VR设备,或者花钱让人们体验VR的设备的摊点,但是VR设备目前来说还是比较小众的,并没有走进千家万户。原因很简单,就是在人们的印象中,VR设备非常的贵,不是一般家庭能买起的,所以也没有太去了解。 VR这种技术,其实已经有了很多年的研发,从最开始VR技术的提出到后来的实现,再到后来有越来越的厂商推出自己的VR设备并且不断更新、研发…

    2022年6月22日
    2500
  • 英特尔历任CEO谱系:谁做的最好?哪位最差?

    作者:湯之上隆 一直推动半导体尖端微型化的英特尔,在2016年未能从14nm向10nm迈进,被台积电和韩国三星超越。… 此外,英特尔在2016年第三季度高达82.5%的处理器市场份额被AMD追赶,从2018年开始将生产外包给台积电最先进的7nm工艺,到2021年第二季度,AMD (44.1%)和英特尔(55.8%)之间的差距已缩小至仅 11.8%…

    2022年6月22日
    2700
  • 比手机还先进!全国首条电动自行车无线充电带落地:比有线充得快

    2月21日消息,据广西广播电视报消息,南宁中关村创新示范基地推出了全球首个电动自行车无线充电站,电动自行车只需停靠在对应位置就能进行无线、隔空充电。 据介绍,电动自行车智能无线充电站由充电主机和智能无线充电带组成,一台主机可以同时为16辆电动自行车进行无线充电。主机铺设在一条智能无线充电带上,任何品牌型号的电动自行车,只需在脚踏板底部安装接收器即可使用无线充…

    2022年6月21日
    2500

发表回复

您的电子邮箱地址不会被公开。

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息

关注微信