Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs

  • 2021-07-21 16:43:46
  • Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, Vinod Nair
  • 7

Abstract

Large Neighborhood Search (LNS) is a combinatorial optimization heuristicthat starts with an assignment of values for the variables to be optimized, anditeratively improves it by searching a large neighborhood around the currentassignment. In this paper we consider a learning-based LNS approach for mixedinteger programs (MIPs). We train a Neural Diving model to represent aprobability distribution over assignments, which, together with an existing MIPsolver, generates an initial assignment. Formulating the subsequent searchsteps as a Markov Decision Process, we train a Neural Neighborhood Selectionpolicy to select a search neighborhood at each step, which is searched using aMIP solver to find the next assignment. The policy network is trained usingimitation learning. We propose a target policy for imitation that, given enoughcompute resources, is guaranteed to select the neighborhood containing theoptimal next assignment across all possible choices for the neighborhood of aspecified size. Our approach matches or outperforms all the baselines on fivereal-world MIP datasets with large-scale instances from diverse applications,including two production applications at Google. At large running times itachieves $2\times$ to $37.8\times$ better average primal gap than the bestbaseline on three of the datasets.

 

Quick Read (beta)

loading the full paper ...