说到数学规划求解器(Solver,下称“求解器”),如果不是这个专业里的人,很难理解它的含义和作用。但求解器对于解决一些复杂问题却作用巨大。

举个形象的例子,在2018年平昌冬奥会的闭幕式上,中国接棒八分钟展示里出现的无人仓机器人,科技感十足,惊艳了全世界。如何计算这些机器人的运行路线,确保这些机器人不会相互“撞车”,同时又最有效率,要解决这些问题,需要一个最优算法,依靠的就是求解器。



在运筹学里,对于数学规划求解器的定义是,针对多种已经建立的线性、整数及各种非线性规划模型,进行算法优化的求解器,可以看作一个“黑盒子”软件系统。

在过去三十余年的发展中,世界领先的商业求解器掌握在IBM等企业及财团手中,这也让美国、英国等国家在求解器研发领域保持了领先地位。

2015年,上海财经大学教授葛冬冬领衔的科学家团队在服务国内电网需求的过程中遇到了求解器国产化的要求。他开始着手组织团队,尝试着发展国产求解器。

2016年,葛冬冬联合几位当年在斯坦福的博士同学,共同成立了杉数科技,通过为各行企业提供运筹学咨询、开发服务,同时,也把求解器研发作为公司最核心的任务和未来的技术支撑。

杉数科技是一家依托于世界领先的深层次数据优化算法和复杂决策模型的求解能力,致力于为企业提供解决方案的人工智能决策公司。

2019年7月,杉数科技研发3年的COPT发布,在知名第三方测评网站亚利桑那州立大学的Mittelmann教授的公开测试集上把线性规划部分做到了目前的排名第一,这是第一个国内自主研发的商业级别求解器。

“我们现在去做,就是去把坑踩了,(求解器)有很多算法迭代,是一个比较纯粹的数学问题,或者说就是一些纯粹的经验。你没有常年去试,各种反复去试,时间积累不够,是弄不出来,欲速不达,怎么样都没用。”近日,葛冬冬在接受澎湃在内的媒体采访时,谈到为什么要在国内组建自己的团队时如此说到。

为什么要建中国自己的商业求解器

“像国外比较成熟的求解器,像IBM的Cplex,像美国的Gurobi,他们都是积累了几十年经验了,每一个环节都优化到了很难提高的地步。但我们现在只有一个很梗概的算法,里头每个细节怎么实现更高效率,你其实不清楚。”杉数科技副总裁皇甫琦告诉澎湃新闻。

成立杉数科技,是希望借商业公司的力量更好地推动国内求解器的落地应用。“我们一开始依靠学校力量,财大跟杉数一起努力,花了两年去做了一个LEAVES, 后来,我们也意识到这是个远比我们想象要困难的事情,时间长,投入大,需要的专业度很高,又不能发论文。用学校去做的话,基本上是无法跟国外商业成熟软件PK的,所以后来我们把LEAVES做了开源化放出去,主要是为了社区建设。后来,我们又成立公司,目光向外,专门从全世界召集了一支华人里最有经验的团队,又从头开发了Cardinal Optimizer(COPT)。“葛冬冬说。

据皇甫琦介绍,求解器里很多基础的软件,例如操作系统,数据库,仿真系统。这些基础性的软件,它难并不是难在数据上,这数据其实是有的,算法基本框架也有,但中间有很多实现的困难,需要经验和能力去设计好框架,也需要清楚知道细节。这些细节说白了就是坑,这些坑国外这些人走了30年,坑都踩了,人家怎么踩的,专利里论文里都没有,我们只能一个个去踩坑。



谈到团队在实际应用过程中遇到的“坑”。皇甫琦说:“正常情况下,我们写一个方程式,求出一个解,这看起来是个很简单的事,但问题是一个方程,有很多系数。比如,系数有10的7次方,还有10的-7次方,两者差别就很大。这时候你用计算机算的时候,计算机本身就会产生误差,这种误差怎么去处理。其实我们这些做数学的人以前从来不去想这个问题的,做计算机的人也很少碰到这种极端的案例,但在实际应用中,怎么去解决,国外的求解器团队不会告诉你的,就需要自己想办法去解。”

除了积累经验,破解求解器的内部“秘密”外,将求解器国产化的另一个重要原因是,在一些军事,基础设施领域里,例如航空、电网运行,使用国产求解器意味着更加安全,当遭遇贸易摩擦等不可抗因素时,对于这些领域涉及的企业,可以拥有更多选择。

另外,求解器国产化的另一个原因是,国产化后,国内的企业可以根据自身的问题进行定制化设计。由于不了解国外求解器系统,此前许多企业遇到许多特定问题时,常常得不到最好的答案。杉数科技将求解器国产化后,破解了“黑匣子”的秘密,就可以根据企业的特殊问题,进行定制化选择。

 求解器如何帮助企业解决问题?

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

除了工厂的排程问题外,在日常的出行中,也有类似的问题需要解决。比如,在打车系统中当乘客发出要车请求,把这位乘客分配给哪个司机,是选择区域最优,分配给离得最近的司机,还是还是做到动态最优?在已知未来几个小时,会有一场演唱会结束,可以预见演唱会周围的地区的用车需求会增加,那么现在的这个乘车请求,在整个城市范围内如何通过决策实现一个均衡状态,让所有人的满意度尽可能地最大化?

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



要让系统落地,最好的方法是找到更多的合作伙伴,在各行业中对求解器进行改进。例如,在上海,永辉超市遇到的问题是如何选择门店地址,保证未来开出的新超市最能捕捉顾客需求,也不会影响到自己原有的超市,不形成恶性竞争?

“永辉在上海现在已经有300多家店。从很早期起,他们就跟杉数合作,用选址软件来做智能选址了。比如今年我计划开50家,明年开100家,后年开150家,利用求解器就就可以算出这50家该怎么开,明年100家怎么开,互相之间不会产生恶性循环。这就需要求解器把这300家门店做全局优化,做一个线性整合规划系统,然后用软件去算,最后算出来就比较接近于全局优化,而不是只是一个局部的东西。”葛冬冬说。

除了智能选址外,求解器在电网,航空,物流等领域也能发挥巨大的作用。例如,电网中的机组组合优化,调度优化,无功优化,甚至现货市场的计算,核心算法基本都需要求解器来驱动。再有就是航空中的飞机,飞行员,空乘的日常排班,紧急情况下排班的调整和重新规划。物流中,送货路线和车辆的的调度和规划,多行业中服务人员的日常路线规划等,都是求解器传统上可能发挥重要作用的领域。

国产化求解器未来的挑战在哪里?

在成立的三年时间里,杉数科技帮助合作伙伴解决了一些问题,但也遇到了很多挑战。

聊到国产化求解器未来的挑战,葛冬冬称,最重要的是时间。“我们成立团队后,发现真正要做可靠的求解器,发现时间是必须要投入的,这东西要日积月累。整数求解器部分我们做了2年以上,但整个预期是3-4年才会有第一版。相比之下,国际上那么多企业,他们做的不光是一版,都是迭代的,大家公认就需要这么长时间。”

但国内在做求解器的过程中,往往等不了这么长的时间。“如果三年时间里,你拿不出东西,你跟你领导说你投入几千万十来个人去做一个软件,但三年后才给一个不能担保的结果,谁会答应你,没有领导会同意你去做这个事情的。所以,真要做这么一件事情,面临的现实压力是很大的。”葛冬冬说,“好在杉数可能一开始起,就把自己的使命定位在了不计成败也要把它做出来,对求解器的开发困难有着足够的预期。”

除了时间投入外,人才也成为制约求解器国产化的因素。皇甫琦认为,开发求解器需要的人才具备三个特点。第一是数学功底好,优化算法功底扎实,第二是代码能力强,有系统工程开发能力。第三是最好具有求解器开发经验。“高校培养的同学,可能最大的问题是学生解决能够多方兼顾能力不太够,求解器里面有哪些坑,他们不知道。而国内企业培养人才又有点急功近利,等不起一个人才慢慢成熟。”皇甫琦说。