A new reinforcement-learning policy teaches a GPU linear-programming solver when to accelerate and when to stop and restart.
Researchers introduced GALLOP, a method that trains an RL policy to tune the primal-dual hybrid gradient algorithm used to solve large linear programs on GPUs. Rather than hand-tuning acceleration parameters and restart timing, GALLOP learns both using a modified proximal policy optimization objective that treats different control groups separately. Tested on six linear-programming families plus a public item-placement benchmark, it cut iteration counts by 1.9x to 5.6x and sped up wall-clock time by as much as 16x compared with MPAX, an existing GPU solver. A single trained policy generalized to problems 3x to 400x larger than its training data, including a transport problem with 10.24 million variables.
Linear programming runs the unglamorous machinery behind supply-chain routing, ad allocation, and resource scheduling, and the bottleneck lately has been tuning, not theory. Hand-configuring solvers for each new problem type is tedious work that does not scale well. A learned policy that generalizes far beyond its training size hints that reinforcement learning could become a standard part of numerical solvers, not just a trick reserved for game-playing systems and chatbots.
The gains are measured against MPAX, a GPU-native solver. Whether they carry over to the commercial solvers most companies currently run is still untested.