Accelerate Presolve in Large-Scale Linear Programming via Reinforcement
  Learning
Yufei Kuang Xijun Li Jie Wang Fangzhou Zhu Meng Lu Zhihai Wang Jia Zeng Houqiang Li Yongdong Zhang Feng Wu
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.