Abstract
Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is instance-dependent, using these general rules for a particular problem might not yield the best performance.
We propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We provide a formal description of the problem and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on two classes of challenging instances, the Generalized Independent Set Problem and the Fixed-Charge Multi-Commodity Network Flow Problem.
Joint work with Antonia Chmiela (Zuse Institute Berlin), Ambros Gleixner (Zuse Institute Berlin, HTW Berlin), Andrea Lodi (Polytechnique Montreal), and Sebastian Pokutta (Zuse Institute Berlin, TU Berlin).
Pre-print available at: https://arxiv.org/abs/2103.