Solving large-scale linear programming (LP) problems is an important task in
various areas such as communication networks, power systems, finance and
logistics. Recently, two distinct approaches have emerged to expedite LP
solving: (i) First-order methods (FOMs); (ii) Learning to optimize (L2O). In
this work, we propose an FOM-unrolled neural network (NN) called PDHG-Net, and
propose a two-stage L2O method to solve large-scale LP problems. The new
architecture PDHG-Net is designed by unrolling the recently emerged PDHG method
into a neural network, combined with channel-expansion techniques borrowed from
graph neural networks. We prove that the proposed PDHG-Net can recover PDHG
algorithm, thus can approximate optimal solutions of LP instances with a
polynomial number of neurons. We propose a two-stage inference approach: first
use PDHG-Net to generate an approximate solution, and then apply PDHG algorithm
to further improve the solution. Experiments show that our approach can
significantly accelerate LP solving, achieving up to a 3$\times$ speedup
compared to FOMs for large-scale LP problems.

通过提出一种名为 PDHG-Net 的 FOM 展开神经网络并结合学习优化的方法，以及两阶段的 L2O 方法，我们在解决大规模 LP 问题方面取得了显著加速并获得多项式级神经元数的近似最优解。

PDHG-Unrolled 学习优化方法用于大规模线性规划

PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear  Programming

Large-scale LP problems from industry usually contain much redundancy that
severely hurts the efficiency and reliability of solving LPs, making presolve
(i.e., the problem simplification module) one of the most critical components
in modern LP solvers. However, how to design high-quality presolve routines --
that is, the program determining (P1) which presolvers to select, (P2) in what
order to execute, and (P3) when to stop -- remains a highly challenging task
due to the extensive requirements on expert knowledge and the large search
space. Due to the sequential decision property of the task and the lack of
expert demonstrations, we propose a simple and efficient reinforcement learning
(RL) framework -- namely, reinforcement learning for presolve (RL4Presolve) --
to tackle (P1)-(P3) simultaneously. Specifically, we formulate the routine
design task as a Markov decision process and propose an RL framework with
adaptive action sequences to generate high-quality presolve routines
efficiently. Note that adaptive action sequences help learn complex behaviors
efficiently and adapt to various benchmarks. Experiments on two solvers
(open-source and commercial) and eight benchmarks (real-world and synthetic)
demonstrate that RL4Presolve significantly and consistently improves the
efficiency of solving large-scale LPs, especially on benchmarks from industry.
Furthermore, we optimize the hard-coded presolve routines in LP solvers by
extracting rules from learned policies for simple and efficient deployment to
Huawei's supply chain. The results show encouraging economic and academic
potential for incorporating machine learning to modern solvers.

大规模线性规划问题中的预处理程序设计是现代线性规划求解器中最关键的组成部分之一，由于需要专家知识和大搜索空间的广泛需求，如何设计高质量的预处理程序仍然是一项具有挑战性的任务。因此，我们提出了一个简单而有效的强化学习框架（RL4Presolve），通过自适应动作序列生成高质量的预处理程序，从而同时解决了预处理程序的选择、执行顺序和停止准则的问题。通过在不同基准测试中的实验证明，RL4Presolve 显著而一致地提高了解决大规模线性规划问题的效率，特别是在工业领域的基准测试中取得了显著的改进。此外，我们还通过从学习的策略中提取规则来优化线性规划求解器中的硬编码预处理程序，以便在华为供应链中进行简单高效的部署，展示了将机器学习应用于现代求解器中的潜力。