Timezone: »

 
Poster
Learning to Schedule Heuristics in Branch and Bound
Antonia Chmiela · Elias Khalil · Ambros Gleixner · Andrea Lodi · Sebastian Pokutta

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »

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 problem-dependent, using these general rules for a particular problem might not yield the best performance. In this work, 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 formalize the learning task 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.

Keywords:

Author Information

Antonia Chmiela (Zuse Institute Berlin)
Elias Khalil (University of Toronto)
Ambros Gleixner (Zuse Institute Berlin and HTW Berlin)
Andrea Lodi (École Polytechnique Montréal)
Sebastian Pokutta (Zuse Institute Berlin)

More from the Same Authors