Adaptive Algorithms Through Machine Learning: Exploiting Interactions in Integer Programming completed
The performance of modern mixed-integer program solvers is highly dependent on a number of interdependent individual components. Using tools from machine learning, we intend to develop an integrated framework that is able to capture interactions of individual decisions made in these components with the ultimate goal to improve performance.
🧑‍🎓 Project Members
![](/images/team/antoniachmiela.jpg)
chmiela (at) zib.de
![](/images/team/christophgraczyk.jpg)
graczyk (at) zib.de
![](/images/team/christophspiegel.jpg)
spiegel (at) zib.de
🪙 Funding
This project was being funded by the Berlin Mathematics Research Center MATH+ (project ID EF1-9), itself funded by the German Research Foundation (DFG) under Germany's Excellence Strategy (EXC-2046/1, project ID 390685689) from January 2021 to December 2022.
🔬 Project Description
Modern Mixed Integer Linear Programming solvers are among the most complex algorithms implemented in software today. They commonly rely on a Branch-and-Cut approach: the MILP problem is first relaxed to a Linear Program by dropping integrality requirements. One then iteratively adds additional constraints to the feasible region of the problem that are violated by the current solution of the relaxation but valid for the original problem. These constraints commonly can take the form of simple bounds on non-integral components of the current solution. Both constraints need to be explored, as either could be violated by any actual solution to the original MILP, motivating the Branch part of Branch-and-Cut. The other form of constraints one can add are cutting planes, that is inequalities resulting from the solution of the current iteration of LP relaxation, which are still violated by the current solution of the relaxation, but are guaranteed to be fulfilled by any actual solution to the original MILP. On top of these two basic components, most MIP solvers additionally employ a number of interdependent individual components to improve performance. The most notable of these components are Primal heuristics, targeted at quickly finding good feasible solutions to the problem. The performance of any such solver is therefore highly dependent on individual decisions made at each iteration, that is for the choice of cuts to add, variable to branch on or heuristic to execute.
Over the last decade there has been an explosion of applications in which Machine Learning methods, and in particular Deep Neural Networks, have displayed an almost uncanny ability to learn decision-making in highly complex and dynamic environments. As a result, there has been an increasing yet still nascent interest in using Artificial Intelligence as a tool for tackling the degrees of freedom in many of the algorithmic choices made by MILP solvers. Using tools from Machine Learning, this project is therefore aimed at studying the interaction of individual decisions made in the components of a MIP solver with the ultimate goal to improve performance. The practical implementation of resulting algorithms will also involve the transfer of classic MIP techniques onto modern hardware like GPUs.
In this project, algorithmic and hardware paradigms from the field of machine learning have been exploited to accelerate critical components of solvers for mixed integer programming, not merely for homogeneous test sets as is typical in the community of machine learning, but over heterogeneous test sets for MIP benchmarking. Our GPU-parallel domain propagation is around 10x to 20x faster than previously available sequential implementations, and up to 180x on favorably-large instances. Our scheduling algorithms for primal heuristics manage to reduce the average primal integral by 49% on challenging sets of instances.
đź’¬ 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]
@inproceedings{ChmielaGleixnerLichockiPokutta2023_OnlineLearning, year = {2023}, booktitle = {Proceedings of 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}, author = {Chmiela, Antonia and Gleixner, Ambros and Lichocki, Pawel and Pokutta, Sebastian}, title = {Online Learning for Scheduling MIP Heuristics} }
- Mexi, G., Besançon, M., Bolusani, S., Chmiela, A., Hoen, A., and Gleixner, A. (2023). Scylla: a Matrix-free Fix-propagate-and-project Heuristic for Mixed-integer Optimization. Proceedings of Conference of the Society for Operations Research in Germany.
[arXiv]
[BibTeX]
@inproceedings{scyllaheuristic, year = {2023}, booktitle = {Proceedings of Conference of the Society for Operations Research in Germany}, archiveprefix = {arXiv}, eprint = {2307.03466}, primaryclass = {math.OC}, author = {Mexi, Gioni and Besançon, Mathieu and Bolusani, Suresh and Chmiela, Antonia and Hoen, Alexander and Gleixner, Ambros}, title = {Scylla: a Matrix-free Fix-propagate-and-project Heuristic for Mixed-integer Optimization} }
- 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]
@inproceedings{CKGLP2021, year = {2021}, booktitle = {Proceedings of 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} }