arXiv：cs.LG（机器学习，全量分类）· Jinhwan Sul, Alex Oshin, Evangelos A. Theodorou·· 15 小时前AI 评分39
GALLOP：用强化学习加速线性规划的原始-对偶混合梯度法
Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming
AI 导读
GALLOP 用强化学习联合学习连续算法参数与离散重启决策，无需对求解器求导，其广义加速 PDHG 更新结合了原始与对偶外推、历史校正和重启锚定。在六个 LP 家族和公开物品放置基准上，GALLOP 将迭代次数减少 1.9-5.6 倍，算法墙钟时间较 MPAX 最高加速 16.0 倍。
正文
Abstract: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.
| Comments: | 35 pages, 4 figures |
| Subjects: | Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.01546 [math.OC] |
| (or arXiv:2610.01546v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.01546 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Jinhwan Sul [view email]
[v1]
Thu, 1 Oct 2026 12:15:39 UTC (3,740 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org