Learning to Schedule Heuristics in IP completed
Heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). However, the question of how to manage multiple MIP heuristics in a solver has not received sufficient attention. This project addresses the strategic management of primal heuristics in MIP solvers, aiming to replace static, hard-coded rules with dynamic, self-improving procedures.
π§βπ Project Members
chmiela (at) zib.de
πͺ Funding
This project was being funded by the Google Research Collabs Program from November 2021 to October 2022.
This project was being funded by the Google Research Collabs Program from November 2022 to October 2023.
π¬ Project Description
Primal heuristics play a crucial role in solvers for Mixed Integer Programming (MIP), especially for the primal side of the optimization process. Although 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. Since the performance of heuristics is highly problem-dependent and most of them can be very costly, it is necessary to handle them strategically. However, state-of-the-art solvers are still relying on hard-coded rules derived from empirical testing resulting in less-than-optimal performance. To address this problem, this project aims to replace the conventional static methods with dynamic, self-improving procedures. Heuristic scheduling can be approached as either an offline or online learning problem. The offline approach seeks to develop a data-driven framework trained on specific problem types, resulting in methods tailored o those characteristics. Conversely, the online approach aims to dynamically adapt heuristic application to the unique features of the current problem instance, without prior training. With our recent publications, we have made first steps to tackle both ways of looking at the heuristic scheduling problem and are actively working on improving our methods even further.
π¬ Talks and posters
Poster presentations
- Dec 2021
- Learning to Schedule Heuristics in Branch-and-Bound by Antonia Chmiela
NeurIPS Conference
<π Publications and preprints
- Chmiela, A., Gleixner, A., Lichocki, P., and Pokutta, S. (2023). Online Learning for Scheduling MIP Heuristics. Proceedings of International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 114β123.
DOI: 10.1007/978-3-031-33271-5_8
[BibTeX]
- Chmiela, A., Khalil, E. B., Gleixner, A., Lodi, A., and Pokutta, S. (2021). Learning to Schedule Heuristics in Branch-and-bound. Proceedings of Conference on Neural Information Processing Systems, 34, 24235β24246.
[URL]
[arXiv]
[poster]
[BibTeX]