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. . (Unpublished)

[img] PDF - Accepted Version
See Usage Policy.


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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper ItemConference 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
Microsoft ResearchUNSPECIFIED
Raytheon CompanyUNSPECIFIED
Record Number:CaltechAUTHORS:20200526-151215262
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:103473
Deposited By: Tony Diaz
Deposited On:26 May 2020 22:25
Last Modified:22 Dec 2022 18:30

Repository Staff Only: item control page