A Caltech Library Service

A General Large Neighborhood Search Framework for Solving Integer Programs

Song, Jialin and Lanka, Ravi and Yue, Yisong and Dilkina, Bistra (2020) A General Large Neighborhood Search Framework for Solving Integer Programs. In: 34th Conference on Neural Information Processing Systems (NeurIPS 2020). Neural Information Processing Foundation , La Jolla, CA, pp. 1-12. ISBN 9781713829546.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


This paper studies how to design abstractions of large-scale combinatorial optimization problems that can leverage existing state-of-the-art solvers in general-purpose ways, and that are amenable to data-driven design. The goal is to arrive at new approaches that can reliably outperform existing solvers in wall-clock time. We focus on solving integer programs and ground our approach in the large neighborhood search (LNS) paradigm, which iteratively chooses a subset of variables to optimize while leaving the remainder fixed. The appeal of LNS is that it can easily use any existing solver as a subroutine, and thus can inherit the benefits of carefully engineered heuristic approaches and their software implementations. We also show that one can learn a good neighborhood selector from training data. Through an extensive empirical validation, we demonstrate that our LNS framework can significantly outperform, in wall-clock time, compared to state-of-the-art commercial solvers such as Gurobi.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemDiscussion Paper
Yue, Yisong0000-0001-9127-1989
Dilkina, Bistra0000-0002-6784-473X
Additional Information:We thank the anonymous reviewers for their suggestions for improvements. Dilkina was supported partially by NSF #1763108, DARPA, DHS Center of Excellence “Critical Infrastructure Resilience Institute”, and Microsoft. This research was also supported in part by funding from NSF #1645832, Raytheon, Beyond Limits, and JPL.
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Department of Homeland SecurityUNSPECIFIED
Raytheon CompanyUNSPECIFIED
Record Number:CaltechAUTHORS:20221222-181855228
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:118581
Deposited By: George Porter
Deposited On:22 Dec 2022 23:51
Last Modified:22 Dec 2022 23:51

Repository Staff Only: item control page