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.

HLEARN
Nov 2021 to Oct 2023
2
2

🧑‍🎓 Project Members

Sebastian Pokutta
Principal Investigator
pokutta (at) zib.de
Antonia Chmiela
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. Example of how to obtain a heuristic schedule from data: The data is shown on the left for three heuristics and nodes and the (optimal) schedule obtained by following the Algorithm proposed by Chmiela et al. is illustrated on the right. 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
conference on neural information processing systems (NeurIPS)

📝 Publications and preprints

  1. Chmiela, A., Gleixner, A., Lichocki, P., and Pokutta, S. (2023). Online Learning for Scheduling MIP Heuristics. Proceedings of the International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 114–123. DOI: 10.1007/978-3-031-33271-5_8 [arXiv]
    [BibTeX]
    @inproceedings{2023_ChmielaGleixnerLichockiPokutta_Onlinelearningscheduling,
  year = {2023},
  booktitle = {Proceedings of the International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research},
  pages = {114-123},
  doi = {10.1007/978-3-031-33271-5_8},
  archiveprefix = {arXiv},
  eprint = {2304.03755},
  primaryclass = {math.OC},
  author = {Chmiela, Antonia and Gleixner, Ambros and Lichocki, Pawel and Pokutta, Sebastian},
  title = {Online Learning for Scheduling MIP Heuristics}
}
  2. Chmiela, A., Khalil, E. B., Gleixner, A., Lodi, A., and Pokutta, S. (2021). Learning to Schedule Heuristics in Branch-and-bound. Proceedings of the Conference on Neural Information Processing Systems, 34, 24235–24246. [URL] [arXiv] [poster]
    [BibTeX]
    @inproceedings{2021_ChmielaEtAl_Heuristicscheduling,
  year = {2021},
  booktitle = {Proceedings of the Conference on Neural Information Processing Systems},
  month = mar,
  volume = {34},
  pages = {24235–24246},
  url = {https://proceedings.neurips.cc/paper_files/paper/2021/file/cb7c403aa312160380010ee3dd4bfc53-Paper.pdf},
  archiveprefix = {arXiv},
  eprint = {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}
}