Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming

📄 arXiv: 2610.01546v1 📥 PDF

作者: Jinhwan Sul, Alex Oshin, Evangelos A. Theodorou

分类: math.OC, cs.AI, cs.LG

发布日期: 2026-10-01

备注: 35 pages, 4 figures

💡 一句话要点

提出GALLOP以加速线性规划的原始-对偶混合梯度方法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 线性规划 强化学习 算法加速 原始-对偶方法 优化技术 大规模计算 机器学习

📋 核心要点

  1. 现有的PDHG方法在处理大规模线性规划时，性能受限于参数协调和重启策略的选择。
  2. GALLOP通过强化学习联合学习算法参数和重启决策，避免了对求解器的微分，提升了效率。
  3. 在六个LP家族的实验中，GALLOP显著减少了迭代次数，并在时间效率上实现了显著加速。

📝 摘要（中文）

原始-对偶混合梯度（PDHG）方法通过GPU友好的矩阵-向量乘法和投影来解决大规模线性规划（LP）问题，但其实际性能依赖于算法参数的协调、加速和重启。本文提出GALLOP，利用强化学习共同学习连续算法参数和离散重启决策，而无需对求解器进行微分。其广义加速PDHG更新结合了独立可调系数的原始和对偶外推、历史修正和重启锚定。我们使用组内近端策略优化目标训练一个维度无关的反馈策略，并在六个LP家族和一个公共物品放置基准上评估GALLOP。实验结果表明，GALLOP在主要评估设置中将迭代次数减少了1.9至5.6倍，并在算法墙钟时间上实现了高达16.0倍的加速。

🔬 方法详解

问题定义：本文旨在解决大规模线性规划（LP）问题中，原始-对偶混合梯度（PDHG）方法在参数协调和重启策略选择上的不足，这些因素直接影响算法的实际性能。

核心思路：GALLOP利用强化学习技术，联合学习算法的连续参数和离散重启决策，避免了对求解器进行微分，从而实现更高效的算法优化。

技术框架：GALLOP的整体架构包括一个强化学习模块，该模块通过组内近端策略优化（PPO）目标进行训练，结合了原始和对偶的外推、历史修正和重启锚定等多个阶段。

关键创新：GALLOP的主要创新在于其通过强化学习实现了算法参数和重启决策的联合优化，这与传统方法的静态参数设置形成鲜明对比，显著提升了算法的适应性和效率。

关键设计：在设计上，GALLOP采用了独立可调的系数来控制原始和对偶的外推过程，同时在重启过渡中排除了非活跃的加速控制，确保了算法的灵活性和高效性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在六个LP家族的主要评估设置中，GALLOP将迭代次数减少了1.9至5.6倍，并在算法墙钟时间上实现了高达16.0倍的加速。此外，训练出的策略在未重新训练的情况下，能够有效推广到更大规模的线性规划实例，显示出良好的泛化能力。

🎯 应用场景

该研究的潜在应用领域包括优化调度、资源分配和网络流量管理等大规模线性规划问题。通过提升PDHG方法的效率，GALLOP能够在实际应用中显著缩短计算时间，提升决策效率，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

Primal-dual hybrid gradient (PDHG) methods solve large-scale linear programs (LPs) using GPU-friendly matrix-vector products and projections, but their practical performance depends on coordinating algorithm parameters, acceleration, and restarts. We introduce GALLOP, which uses reinforcement learning to jointly learn continuous algorithm parameters and discrete restart decisions without differentiating through the solver. Its generalized accelerated PDHG update combines separate primal and dual extrapolation, history corrections, and restart anchoring with independently adjustable coefficients. We train a dimension-agnostic feedback policy using a groupwise proximal policy optimization objective that clips likelihood ratios separately for different control groups and excludes inactive acceleration controls on restart transitions. We evaluate GALLOP on six LP families and a public item-placement benchmark. On the main evaluation settings across the six families, GALLOP reduces iteration counts by factors of $1.9$-$5.6$ and achieves up to a $16.0\times$ speedup in algorithm wall-clock time over MPAX. With one policy trained per family, the learned policies generalize without retraining to within-family LPs $3\times$-$400\times$ larger than the largest training instances, including Transport LPs with $10.24$ million variables.