2024-09-20 20:22:24 英文原文

利用 PDLP 扩展线性规划

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 的一阶方法

扩展当今国家使用的方法最先进的 LP 求解器提出了重大挑战。这两种方法的主要计算限制都与求解线性方程所需的矩阵分解有关，随着问题规模的增长，引入了两个关键挑战：

• 内存溢出：使用单纯形法的 LP 求解器（例如 Google 的GLOP）采用 LU 分解，而使用内点法的求解器则使用 Cholesky 分解。对于这两种方法，结果分解使用的内存比 LP 实例本身多得多。
• 硬件相关的挑战：这两种方法都面临着利用现代计算架构（例如 GPU 或分布式系统）的困难，因为稀疏矩阵分解步骤通常需要高度连续的操作。

鉴于传统 LP 方法的上述局限性，FOM 已成为解决大规模 LP 问题的有前途的替代方案。与依赖矩阵分解的方法不同，FOM 利用梯度信息迭代更新其解决方案，主要计算要求是矩阵向量乘法。这种区别意味着 FOM 仅需要 LP 实例本身的存储，而不需要额外的内存来存储分解形式。此外，机器学习和深度学习 FOM 的进步增强了它们的可扩展性，使其在 GPU 和分布式计算等现代计算平台上非常高效。这种可扩展性和减少的内存依赖性使 FOM 特别适合传统方法可能会失效的大型复杂 LP 任务。

重新启动 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 设计为一个软件包，可以有效解决线性规划问题。PDLP的核心算法基于重新启动的PDHG，我们通过五个改进对其进行了显着增强：

• 预求解：此过程在求解之前简化了LP问题。它涉及检测不一致的边界、检测重复行、收紧边界等。这些步骤降低了复杂性并提高了求解器的效率。
• 预处理：PDLP 中的预处理器重新调整 LP 实例内的变量和约束。这种调整有助于通过优化问题的数值条件来加速算法，从而提高收敛速度。
• 不可行性检测：在现实场景中，LP问题通常可能是不可行或无界的。我们的方法利用 PDHG 的迭代，它对有关问题的可行性和有界性的信息进行编码，无需额外的计算工作即可进行检测。我们的 SIAM Journal 论文详细介绍了该方法的理论。
• 自适应重启：该技术涉及策略性地决定何时最佳地重启 PDHG 算法，以提高其效率，特别是加快收敛到高精度的速度。
• 自适应步长：我们引入了一种自适应方法来选择 PDHG 中的步长，这显着减少了手动调整的需要。这种方法根据问题的特征和算法的性能动态调整步长，从而促进更快的收敛。

PDLP 是开源的，作为 Google 开源工具 OR-Tools 的一部分。用于优化的软件套件。该求解器易于使用，并且具有 Python、C、Java 和 C# 接口。有关如何使用 PDLP 的更多详细信息和示例，请参阅 OR-Tools 文档。

应用

扩展和加速 LP 可以在此处启用新的应用程序，我们简要提及三个：

• 数据中心网络流量工程（博客文章、论文）：Google 的数据中心依靠动态优化的流量工程来实现高性能效率。优化网络流量路由的挑战作为大规模 LP 问题定期得到解决。以前，不可能足够快地解决这个大问题，这导致了分区启发法的发展。这些启发式方法将问题分解为许多较小规模的线性规划，这些规划可以同时解决，尽管是以牺牲最优性为代价的。随着PDLP的引入，我们现在可以有效地优化整个数据中心网络的流量路由，有效地节省整个网络中大量的机器资源。该解决方案自 2023 年 5 月起已部署在 Google 的生产环境中。
• 集装箱运输优化（博客文章）：全球航运供应链依赖于优化船舶访问港口的顺序以及集装箱在港口的放置情况。船只。由于现实世界实例的规模极大，直接解决方案通常很棘手。因此，人们提出了各种启发式方法来提高解决这一复杂优化问题的效率和实用性。该问题可以表述为一种称为大规模整数两层多商品流动问题的优化问题。PDLP 能够解决该公式的线性松弛问题，从而量化启发式的质量。
• 旅行商问题：旅行商问题 (TSP) 提出了一个经典问题：给定城市列表及其距离，什么是遍历每个城市一次并返回起点的最短路线？这个问题非常具有挑战性，在理论计算机科学和运筹学中具有重要意义。PDLP 通过解决现实世界中大规模的 TSP 下界 LP 实例（包含约束矩阵中多达 120 亿个非零条目）来展示其强大功能。这种能力远远超过了当今最先进的商业求解器的能力，展示了 PDLP 解决大规模 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，以及数据中心网络团队、算法团队和运筹研究团队的合作者。