2024 年 9 月 20 日
陆海浩,Google 研究院研究科学家、麻省理工学院助理教授,以及校长 David ApplegateGoogle 研究院科学家
本文介绍了名为 PDLP 的获奖产品,这是一种用于大规模线性规划的基于一阶方法的新型求解器。
自 20 世纪 40 年代末以来,LP 求解已经发生了显着的发展,其中 Dantzig 的单纯形法和各种内点方法是最流行的技术。当今先进的商业 LP 求解器利用这些方法,但由于计算需求而面临着扩展到非常大的实例的挑战。为了克服这一限制,一阶方法 (FOM) 在大规模 LP 问题中获得了关注。
考虑到上述情况,我们引入了我们的求解器 PDLP(Primal-dual Hybrid Gradient Gradient Enhanced for LP)),一种基于 FOM 的新型 LP 求解器,可显着增强我们的 LP 求解能力。PDLP 利用矩阵向量乘法而不是矩阵分解,需要更少的内存,并且与 GPU 和分布式系统等现代计算技术更兼容,提供了一种可扩展的替代方案,可以减轻传统 LP 方法的内存和计算效率低下的问题。PDLP 在 Google 的 OR-Tools 中开源。该项目自 2018 年以来一直在开发中 [1,2,3],我们很自豪地宣布,该项目于 2024 年 7 月在国际数学规划研讨会上共同荣获著名的 Beale Orchard-Hays 奖。这一荣誉是一项殊荣计算优化领域的最高荣誉,由数学优化协会每三年颁发一次。
扩展当今国家使用的方法最先进的 LP 求解器提出了重大挑战。这两种方法的主要计算限制都与求解线性方程所需的矩阵分解有关,随着问题规模的增长,引入了两个关键挑战:
鉴于传统 LP 方法的上述局限性,FOM 已成为解决大规模 LP 问题的有前途的替代方案。与依赖矩阵分解的方法不同,FOM 利用梯度信息迭代更新其解决方案,主要计算要求是矩阵向量乘法。这种区别意味着 FOM 仅需要 LP 实例本身的存储,而不需要额外的内存来存储分解形式。此外,机器学习和深度学习 FOM 的进步增强了它们的可扩展性,使其在 GPU 和分布式计算等现代计算平台上非常高效。这种可扩展性和减少的内存依赖性使 FOM 特别适合传统方法可能会失效的大型复杂 LP 任务。
原始-对偶混合梯度(PDHG)因其在图像处理中的应用而被广泛认可。当应用于 LP 时,PDHG 的主要计算需求涉及矩阵向量乘法,从而消除了矩阵分解的需要。这使得 PDHG 对于大规模计算任务特别有效,但在求解 LP 时并不可靠。例如,在 383 个实例的基准测试中,PDHG 只能以中等精度解决 113 个实例。
为了增强 PDHG 解决 LP 问题的可靠性,我们开发了一种称为重新启动 PDHG 的修改方法。该版本使用双循环结构,其中 PDHG 运行直到触发重新启动条件,然后计算 PDHG 迭代的平均值。然后算法从这个平均点重新开始。该方法如下图所示,其中标准 PDHG 的轨迹用蓝线表示,平均迭代用红线表示,重新启动的 PDHG 用绿线表示。值得注意的是,重新启动的 PDHG 显示出更快地收敛到最优解,这在图中用星号标记。
这种更快收敛背后的直觉是,通过从每个螺旋阶段结束时计算的平均值重新启动,重新启动的PDHG有效地缩短了收敛路径。该策略利用 PDHG 螺旋的循环性质来加快求解过程。
我们在研究中表明,这种重新启动技术可以在理论上和实践中显着加快 LP 的 PDHG 收敛行为。这使得重新启动的 PDHG 成为一种高效且理论上合理的方法,用于解决 LP 挑战,增强其在计算优化中的实用性和有效性。
我们将 PDLP 设计为一个软件包,可以有效解决线性规划问题。PDLP的核心算法基于重新启动的PDHG,我们通过五个改进对其进行了显着增强:
PDLP 是开源的,作为 Google 开源工具 OR-Tools 的一部分。用于优化的软件套件。该求解器易于使用,并且具有 Python、C、Java 和 C# 接口。有关如何使用 PDLP 的更多详细信息和示例,请参阅 OR-Tools 文档。
扩展和加速 LP 可以在此处启用新的应用程序,我们简要提及三个:
自诞生以来PDLP 的发布引起了人们的极大兴趣,从而导致了进一步的增强。以下是一些值得注意的进展: cuPDLP.jl 是 PDLP 的开源 GPU 实现,用 Julia 编写。商业求解器公司 Cardinal Optimizer 已于 2024 年 1 月将 PDLP 纳入其软件 7.1 版本。开源求解器 HiGHS 已于 2024 年 3 月在其软件 V1.7.0 中纳入 PDLP 版本。学术界不断探索和扩展PDLP的理论基础。最近的研究集中在PDHG的新分析、条件数理论、基于轨迹的分析、二次规划和半定规划的扩展等领域。这些努力不仅加深了对PDLP底层力学的理解,而且探索了其潜力应用到更复杂的问题。这些发展反映了 PDLP 对优化领域的重大影响,弥合了理论研究和实际应用之间的差距。随着 PDLP 的不断发展,其影响力预计将不断增长,从而突破计算优化所能实现的界限。
我们感谢我们的合著者 Mateo Diaz、Oliver Hinder、Miles Lubin 和 Warren Schudy,感谢他们的杰出支持和贡献。我们还要感谢我们的经理 Vahab Mirrokni、Jon Orwant 和 Aaron Archer,以及数据中心网络团队、算法团队和运筹研究团队的合作者。