Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs

Large Neighborhood Search (LNS) is a combinatorial optimization heuristic\nthat starts with an assignment of values for the variables to be optimized, and\niteratively improves it by searching a large neighborhood around the current\nassignment. In this paper we consider a learning-based LNS approach for mixed\ninteger programs (MIPs). We train a Neural Diving model to represent a\nprobability distribution over assignments, which, together with an\noff-the-shelf MIP solver, generates an initial assignment. Formulating the\nsubsequent search steps as a Markov Decision Process, we train a Neural\nNeighborhood Selection policy to select a search neighborhood at each step,\nwhich is searched using a MIP solver to find the next assignment. The policy\nnetwork is trained using imitation learning. We propose a target policy for\nimitation that, given enough compute resources, is guaranteed to select the\nneighborhood containing the optimal next assignment amongst all possible\nchoices for the neighborhood of a specified size. Our approach matches or\noutperforms all the baselines on five real-world MIP datasets with large-scale\ninstances from diverse applications, including two production applications at\nGoogle. It achieves $2\\times$ to $37.8\\times$ better average primal gap than\nthe best baseline on three of the datasets at large running times.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC