Learning to Schedule Heuristics in IP
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.
IOL Project Members
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.
Publications and preprints
Conference contributions
- Chmiela, A., Gleixner, A., Lichocki, P., and Pokutta, S. (2023). Online Learning for Scheduling MIP Heuristics. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 13884, 114–123.
Associated with CPAIOR 2023.
DOI: 10.1007/978-3-031-33271-5_8
[arXiv]
[BibTeX]
@inproceedings{2023_ChmielaGleixnerLichockiPokutta_Onlinelearningscheduling, year = {2023}, date = {2023-05-23}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, series = {Lecture Notes in Computer Science}, volume = {13884}, publisher = {Springer Science+Business Media}, month = may, pages = {114--123}, doi = {10.1007/978-3-031-33271-5_8}, archiveprefix = {arXiv}, eprint = {2304.03755}, arxiv = {arXiv:2304.03755}, primaryclass = {math.OC}, author = {Chmiela, Antonia and Gleixner, Ambros and Lichocki, Pawel and Pokutta, Sebastian}, title = {Online Learning for Scheduling MIP Heuristics} } - Chmiela, A., Khalil, E. B., Gleixner, A., Lodi, A., and Pokutta, S. (2021). Learning to Schedule Heuristics in Branch-and-Bound. Advances in Neural Information Processing Systems, 34, 24235–24246.
Associated with NeurIPS 2021.
[URL]
[arXiv]
[poster]
[BibTeX]
@inproceedings{2021_ChmielaEtAl_Heuristicscheduling, year = {2021}, booktitle = {Advances in Neural Information Processing Systems}, series = {Advances in Neural Information Processing Systems}, volume = {34}, publisher = {Curran Associates}, month = mar, pages = {24235--24246}, url = {https://proceedings.neurips.cc/paper_files/paper/2021/file/cb7c403aa312160380010ee3dd4bfc53-Paper.pdf}, archiveprefix = {arXiv}, eprint = {2103.10294}, arxiv = {arXiv:2103.10294}, primaryclass = {cs.LG}, author = {Chmiela, Antonia and Khalil, Elias B. and Gleixner, Ambros and Lodi, Andrea and Pokutta, Sebastian}, title = {Learning to Schedule Heuristics in Branch-and-Bound}, poster = {https://pokutta.com/slides/20211120_poster_NeurIPS21_learningheuristics.pdf} }

