Song, Jialin and Lanka, Ravi and Yue, Yisong and Dilkina, Bistra (2020) A General Large Neighborhood Search Framework for Solving Integer Programs. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20200526-151215262
![]() |
PDF
- Accepted Version
See Usage Policy. 548kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200526-151215262
Abstract
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: |
| ||||||||||||||||||
ORCID: |
| ||||||||||||||||||
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. | ||||||||||||||||||
Funders: |
| ||||||||||||||||||
Record Number: | CaltechAUTHORS:20200526-151215262 | ||||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20200526-151215262 | ||||||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||
ID Code: | 103473 | ||||||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||||||
Deposited By: | Tony Diaz | ||||||||||||||||||
Deposited On: | 26 May 2020 22:25 | ||||||||||||||||||
Last Modified: | 22 Dec 2022 18:30 |
Repository Staff Only: item control page