CaltechAUTHORS
  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) https://resolver.caltech.edu/CaltechAUTHORS:20200526-151215262

[img] PDF - Submitted Version
See Usage Policy.

554Kb

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:
URLURL TypeDescription
http://arxiv.org/abs/2004.00422arXivDiscussion Paper
ORCID:
AuthorORCID
Yue, Yisong0000-0001-9127-1989
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:26 May 2020 22:25

Repository Staff Only: item control page