Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning
This work addresses the problem of inefficient presolve in LP solvers for industry practitioners, offering a novel machine learning approach that is incremental in applying RL to an existing optimization task.
The paper tackles the challenge of designing high-quality presolve routines for large-scale linear programming (LP) problems, which are critical for efficiency but require expert knowledge and face a large search space. It proposes a reinforcement learning framework (RL4Presolve) that formulates this as a Markov decision process, and experiments on real-world and synthetic benchmarks show it significantly improves solving efficiency, especially for industrial applications, with optimized routines deployed to Huawei's supply chain demonstrating economic and academic potential.
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.