SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs
This work addresses performance limitations in neural LNS solvers for combinatorial optimization, offering an incremental improvement for researchers and practitioners in optimization and AI.
The paper tackled the problem of local optima and sample inefficiency in neural network-based Large Neighborhood Search (LNS) for solving Integer Linear Programs (ILPs), resulting in SPL-LNS, which substantially surpasses prior neural LNS solvers across various ILP problems.
Large Neighborhood Search (LNS) is a common heuristic in combinatorial optimization that iteratively searches over a large neighborhood of the current solution for a better one. Recently, neural network-based LNS solvers have achieved great success in solving Integer Linear Programs (ILPs) by learning to greedily predict the locally optimal solution for the next neighborhood proposal. However, this greedy approach raises two key concerns: (1) to what extent this greedy proposal suffers from local optima, and (2) how can we effectively improve its sample efficiency in the long run. To address these questions, this paper first formulates LNS as a stochastic process, and then introduces SPL-LNS, a sampling-enhanced neural LNS solver that leverages locally-informed proposals to escape local optima. We also develop a novel hindsight relabeling method to efficiently train SPL-LNS on self-generated data. Experimental results demonstrate that SPL-LNS substantially surpasses prior neural LNS solvers for various ILP problems of different sizes.