A General Large Neighborhood Search Framework for Solving Integer Linear\n Programs

Abstract

This paper studies a strategy for data-driven algorithm design for\nlarge-scale combinatorial optimization problems that can leverage existing\nstate-of-the-art solvers in general purpose ways. The goal is to arrive at new\napproaches that can reliably outperform existing solvers in wall-clock time. We\nfocus on solving integer programs, and ground our approach in the large\nneighborhood search (LNS) paradigm, which iteratively chooses a subset of\nvariables to optimize while leaving the remainder fixed. The appeal of LNS is\nthat it can easily use any existing solver as a subroutine, and thus can\ninherit the benefits of carefully engineered heuristic or complete approaches\nand their software implementations. We show that one can learn a good\nneighborhood selector using imitation and reinforcement learning techniques.\nThrough an extensive empirical validation in bounded-time optimization, we\ndemonstrate that our LNS framework can significantly outperform compared to\nstate-of-the-art commercial solvers such as Gurobi.\n