正文内容 评论(0)
近日,继斩获AI顶会NeurIPS 2021 ML4CO求解器超参优化赛道冠军之后,华为云天筹AI求解器又迎来新的突破。华为云EI创新孵化Lab与华为2012实验室中央研究院理论研究部联合团队(以下简称“华为联合团队”)在网络线性规划求解器关键技术上实现突破,助力天筹AI求解器在国际权威求解器测评——Hans Mittelmann教授的大规模网络线性规划榜单中登顶TOP1,性能领先第二名11%。
华为云天筹AI求解器登顶国际权威Hans Mittelmann
大规模网络线性规划榜单(2022.6.16)
网络线性规划应用场景丰富 助力高效求得问题最优解
网络线性规划是网络流理论与算法的核心,本质上是要充分利用和有效提升现有网络资源的能力,使系统的流量达到最大并有效运行。如今网络线性规划已广泛应用在网络规划、调度优化、物理运输等现实场景,覆盖通讯、交通、物流、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。
例如,在交通网络中,控制中心可以通过网络线性规划来调度车流,实现高峰期拥塞路段的流量疏导,提高城市路面通勤效率。在电力网络中,中央控制器通过网络线性规划来调度能源,能够实现对能源曲线的削峰填谷,保障能源输出的平稳供应。
再如,下图是一个连接某物资产地Vs(例如兰州)至销地Vt(例如上海)的铁路运输网,弧上的数字表示该路段的最大通过能力。如果要制定一个运输方案,使从产地Vs运到销地Vt的物资数量最多,通过网络线性规划能够快速得出最优解。
基于网络线性规划求解铁路运输网的最大通过能力
求解网络线性规划问题可实现成本开销最小化、有限资源配置最优、发挥网络传输能力最大化的目的。随着业务的不断增大,企业将会面对越来越多关于网络结构的决策优化问题,如何在大规模的变量和约束条件下求得最优解,是企业提升运营效率的关键。
两大新技术加持 华为云天筹AI求解器再次突破求解性能
本次打榜主要比拼基于大规模变量和约束条件的问题求解速度。华为联合团队提出了基于网络拓扑特征的自适应稀疏度优化技术和基于网络线性规划问题理论性质的底层优化及并行化技术,在榜单的25个问题中实现高效求解,性能领先第二名11%。两大技术充分利用网络线性规划问题的结构化特征,极大提升华为云天筹AI求解器在网络线性规划问题上的性能。
基于网络拓扑特征的“自适应稀疏度优化”技术
华为联合团队提出了一种全新的调节迭代过程稀疏性的方法,并基于问题的代数特征恢复物理拓扑并结合网络节点度分布等信息自适应选择最优策略,从而实现整体求解时间的大幅下降。
基于网络单纯形理论性质的“底层优化及并行化”技术
对于大规模网络线性规划问题,特别是实际场景中涉及千万甚至上亿规模的问题,底层实现也是求解器性能的瓶颈所在。华为联合团队利用网络线性规划问题的理论性质,大幅优化了矩阵库等基础模块的底层实现,并利用并行化技术大幅加速求解过程,使得华为云天筹AI求解器能够支持亿级规模网络线性规划的高效求解。
如今“自适应稀疏度优化”和“底层优化及并行化”两项技术已经集成到华为云天筹AI求解器中,极大提升在网络线性规划问题上的算法性能,能快速求解与网络结构相关的网络规划、调度优化、物理运输等问题。在大规模通信网络结构优化问题中,网络优化平台基于全网流量规律,通过网络线性规划分配网络资源,提升用户体验。在大规模云资源调度问题中,云调度平台结合各个区域资源,在满足客户算力、带宽和存储需求的条件下,结合预测规划和网络线性规划方法使得计算资源供需平衡、支撑业务弹性和满足业务波动等需求。未来,网络线性规划求解器还将应用在华为数字能源能量优化调度问题上,帮助分钟级完成问题求解,提升能源利用率、降低碳排放。
随着华为运筹优化技术的发展和优化理论的突破,更多创新技术将会落地天筹AI求解器。未来,华为联合团队将持续从运筹优化理论和算法层面进行难题攻坚,不断优化天筹AI求解器性能,提升求解器领域技术竞争力,为客户创造更大价值。