Integer Optimization
mixed-integer programming; exact linear programming; learning for combinatorial optimization; cutting planes in integer optimizatio; warm starting; SCIP Optimization Suite
What we are interested in
We investigate theory and solution methods for mixed-integer optimization problems (MIPs). MIPs are challenging problems for which exact solution methods integrate several algorithmic components such as relaxations, separation through cutting planes, primal heuristics, conflict analysis, and pricing for column generation. Our group works on all these aspects and on their interaction within the constraint integer programming solver SCIP, which is based on a branch-cut-and-price algorithm. We also work on algorithms combining satisfiability and mixed-integer optimization techniques such as conflict analysis and domain propagation, and on exact MIP and linear programming solving, guaranteeing and certifying that solutions are not invalidated by floating-point arithmetic errors.
Researchers
Mathieu Besançon
besancon (at) zib.de
besancon (at) zib.de
Suresh Bolusani
bolusani (at) zib.de
bolusani (at) zib.de
Alexander Hoen
hoen (at) zib.de
hoen (at) zib.de
Christoph Graczyk
graczyk (at) zib.de
graczyk (at) zib.de
Fabian Frickenstein
frickenstein (at) zib.de
frickenstein (at) zib.de
Gabriele Iommazzo
iommazzo (at) zib.de
iommazzo (at) zib.de
Gioni Mexi
mexi (at) zib.de
mexi (at) zib.de
Herman Appelgren
appelgren (at) zib.de
appelgren (at) zib.de
Julian Manns
manns (at) zib.de
manns (at) zib.de
Leon Eifler
eifler (at) zib.de
eifler (at) zib.de
Mohammed Ghannam
mohammed.ghannam (at) htw-berlin.de
mohammed.ghannam (at) htw-berlin.de
Projects
Publications
- Berthold, T., Mexi, G., and Salvagnin, D. (2023). Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump. EURO Journal on Computational Optimization, 11.
DOI: 10.1016/j.ejco.2023.100066
[BibTeX]
@article{BertholdMexiSalvagnin2023, year = {2023}, journal = {EURO Journal on Computational Optimization}, volume = {11}, doi = {10.1016/j.ejco.2023.100066}, author = {Berthold, Timo and Mexi, Gioni and Salvagnin, Domenico}, title = {Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump} } - Bestuzheva, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., Gottwald, L., Graczyk, C., Halbig, K., Hoen, A., Hojny, C., van der Hulst, R., Koch, T., Lübbecke, M., Maher, S. J., … Witzig, J. (2023). Enabling Research Through the SCIP Optimization Suite 8.0. ACM Transactions on Mathematical Software.
DOI: 10.1145/3585516
[arXiv]
[BibTeX]
@article{BestuzhevaBesanconEtal2023, year = {2023}, journal = {ACM Transactions on Mathematical Software}, doi = {10.1145/3585516}, archiveprefix = {arXiv}, eprint = {2303.07101}, primaryclass = {math.OC}, author = {Bestuzheva, Ksenia and Besançon, Mathieu and Chen, Wei-Kun and Chmiela, Antonia and Donkiewicz, Tim and van Doornmalen, Jasper and Eifler, Leon and Gaul, Oliver and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Leona and Graczyk, Christoph and Halbig, Katrin and Hoen, Alexander and Hojny, Christopher and van der Hulst, Rolf and Koch, Thorsten and Lübbecke, Marco and Maher, Stephen J. and Matter, Frederic and Mühmer, Erik and Müller, Benjamin and Pfetsch, Marc and Rehfeldt, Daniel and Schlein, Steffan and Schlösser, Franziska and Serrano, Felipe and Shinano, Yuji and Sofranac, Boro and Turner, Mark and Vigerske, Stefan and Wegscheider, Fabian and Wellner, Philipp and Weninger, Dieter and Witzig, Jakob}, title = {Enabling Research Through the SCIP Optimization Suite 8.0} } - 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} } - Eifler, L., and Gleixner, A. (2023). A Computational Status Update for Exact Rational Mixed Integer Programming. Mathematical Programming, 197, 793–812.
DOI: 10.1007/s10107-021-01749-5
[URL]
[BibTeX]
@article{EiflerGleixner2023_Acomputational, year = {2023}, journal = {Mathematical Programming}, volume = {197}, pages = {793-812}, doi = {10.1007/s10107-021-01749-5}, url = {https://link.springer.com/article/10.1007/s10107-021-01749-5}, author = {Eifler, Leon and Gleixner, Ambros}, title = {A Computational Status Update for Exact Rational Mixed Integer Programming} } - Gleixner, A., Gottwald, L., and Hoen, A. (2023). PaPILO: a Parallel Presolving Library for Integer and Linear Programming with Multiprecision Support. INFORMS Journal on Computing.
DOI: 10.1287/ijoc.2022.0171
[arXiv]
[BibTeX]
@article{HoenGottwaldGleixner2023_PaPILO, year = {2023}, journal = {INFORMS Journal on Computing}, doi = {10.1287/ijoc.2022.0171}, archiveprefix = {arXiv}, eprint = {2206.10709}, primaryclass = {math.OC}, author = {Gleixner, Ambros and Gottwald, Leona and Hoen, Alexander}, title = {PaPILO: a Parallel Presolving Library for Integer and Linear Programming with Multiprecision Support} } - Liberti, L., Iommazzo, G., Lavor, C., and Maculan, N. (2023). Cycle-based Formulations in Distance Geometry. Open Journal of Mathematical Optimization, 4(1).
DOI: 10.5802/ojmo.18
[arXiv]
[BibTeX]
@article{LIL+23, year = {2023}, journal = {Open Journal of Mathematical Optimization}, volume = {4}, number = {1}, doi = {10.5802/ojmo.18}, archiveprefix = {arXiv}, eprint = {2006.11523}, primaryclass = {math.OC}, author = {Liberti, Leo and Iommazzo, Gabriele and Lavor, Carlile and Maculan, Nelson}, title = {Cycle-based Formulations in Distance Geometry} } - Turner, M., Berthold, T., and Besançon, M. (2023). A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming. Proceedings of Conference of the Society for Operations Research in Germany.
[arXiv]
[BibTeX]
@inproceedings{context_cutsel_23, year = {2023}, booktitle = {Proceedings of Conference of the Society for Operations Research in Germany}, archiveprefix = {arXiv}, eprint = {2307.07322}, primaryclass = {math.OC}, author = {Turner, Mark and Berthold, Timo and Besançon, Mathieu}, title = {A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming} } - Turner, M., Berthold, T., Besançon, M., and Koch, T. (2023). Cutting Plane Selection with Analytic Centers and Multiregression. Proceedings of International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research.
[BibTeX]
@inproceedings{cutsel_acenter_22, year = {2023}, booktitle = {Proceedings of International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, author = {Turner, Mark and Berthold, Timo and Besançon, Mathieu and Koch, Thorsten}, title = {Cutting Plane Selection with Analytic Centers and Multiregression} } - Mexi, G., Berthold, T., Gleixner, A., and Nordström, J. (2023). Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning. Proceedings of 29th International Conference on Principles and Practice of Constraint Programming (CP 2023).
[BibTeX]
@inproceedings{mexi2023improving, year = {2023}, booktitle = {Proceedings of 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)}, author = {Mexi, Gioni and Berthold, Timo and Gleixner, Ambros and Nordström, Jakob}, title = {Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning} } - 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} } - Bolusani, S., and Ralphs, T. K. (2022). A Framework for Generalized Benders’ Decomposition and Its Applications to Multilevel Optimization. Mathematical Programming, 196, 389–426.
DOI: 10.1007/s10107-021-01763-7
[arXiv]
[BibTeX]
@article{BolRal22, year = {2022}, journal = {Mathematical Programming}, volume = {196}, pages = {389-426}, doi = {10.1007/s10107-021-01763-7}, archiveprefix = {arXiv}, eprint = {2104.06496}, primaryclass = {math.OC}, author = {Bolusani, Suresh and Ralphs, Ted K.}, title = {A Framework for Generalized Benders' Decomposition and Its Applications to Multilevel Optimization} } - Eifler, L., Gleixner, A., and Pulaj, J. (2022). A Safe Computational Framework for Integer Programming Applied to Chvátal’s Conjecture. ACM Transactions on Mathematical Software, 48(2), 1–12.
DOI: 10.1145/3485630
[BibTeX]
@article{EiflerGleixnerPulaj2022_Asafecomputational, year = {2022}, journal = {ACM Transactions on Mathematical Software}, volume = {48}, number = {2}, pages = {1-12}, doi = {10.1145/3485630}, author = {Eifler, Leon and Gleixner, Ambros and Pulaj, Jonad}, title = {A Safe Computational Framework for Integer Programming Applied to Chvátal's Conjecture} } - Hoppmann-Baum, K., Burdakov, O., Mexi, G., Casselgren, C. J., and Koch, T. (2022). Length-Constrained Cycle Partition with an Application to UAV Routing. Optimization Methods and Software.
DOI: 10.1080/10556788.2022.2053972
[BibTeX]
@article{HoppmannBaumBurdakovMexietal.2022, year = {2022}, journal = {Optimization Methods and Software}, doi = {10.1080/10556788.2022.2053972}, author = {Hoppmann-Baum, Kai and Burdakov, Oleg and Mexi, Gioni and Casselgren, Carl Johan and Koch, Thorsten}, title = {Length-Constrained Cycle Partition with an Application to UAV Routing} } - Iommazzo, G., D’Ambrosio, C., Frangioni, A., and Liberti, L. (2022). The Algorithm Configuration Problem. In Encyclopedia of Optimization (pp. 1–8).
DOI: 10.1007/978-3-030-54621-2_749-1
[BibTeX]
@incollection{IDF+22, year = {2022}, booktitle = {Encyclopedia of Optimization}, pages = {1-8}, doi = {10.1007/978-3-030-54621-2_749-1}, author = {Iommazzo, Gabriele and D'Ambrosio, Claudia and Frangioni, Antonio and Liberti, Leo}, title = {The Algorithm Configuration Problem} } - Sofranac, B., Gleixner, A., and Pokutta, S. (2022). Accelerating Domain Propagation: An Efficient GPU-parallel Algorithm Over Sparse Matrices. Parallel Computing, 109, 102874.
DOI: 10.1016/j.parco.2021.102874
[arXiv]
[summary]
[BibTeX]
@article{SofranacGleixnerPokutta2022_Accelerating, year = {2022}, journal = {Parallel Computing}, volume = {109}, pages = {102874}, doi = {10.1016/j.parco.2021.102874}, archiveprefix = {arXiv}, eprint = {2009.07785}, primaryclass = {cs.DC}, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating Domain Propagation: An Efficient GPU-parallel Algorithm Over Sparse Matrices}, summary = {https://pokutta.com/blog/research/2020/09/20/gpu-prob.html} } - Sofranac, B., Gleixner, A., and Pokutta, S. (2022). An Algorithm-independent Measure of Progress for Linear Constraint Propagation. Constraints, 27, 432–455.
DOI: 10.1007/s10601-022-09338-9
[arXiv]
[BibTeX]
@article{SofranacGleixnerPokutta2022_AnAlgorithm-IndependentMeasure, year = {2022}, journal = {Constraints}, volume = {27}, pages = {432-455}, doi = {10.1007/s10601-022-09338-9}, archiveprefix = {arXiv}, eprint = {2106.07573}, primaryclass = {math.OC}, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-independent Measure of Progress for Linear Constraint Propagation} } - Gasse, M., Bowly, S., Cappart, Q., Charfreitag, J., Charlin, L., Chételat, D., Chmiela, A., Dumouchelle, J., Gleixner, A., Kazachkov, A. M., Khalil, E., Lichocki, P., Lodi, A., Lubin, M., Maddison, C. J., Christopher, M., Papageorgiou, D. J., Parjadis, A., Pokutta, S., … Kun, M. (2021). The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights. Proceedings of Conference on Neural Information Processing Systems, 176, 220–231.
[URL]
[arXiv]
[BibTeX]
@inproceedings{GasseEtal2022_ML4CO, year = {2021}, booktitle = {Proceedings of Conference on Neural Information Processing Systems}, month = jun, volume = {176}, pages = {220–231}, url = {https://proceedings.mlr.press/v176/gasse22a.html}, archiveprefix = {arXiv}, eprint = {2203.02433}, primaryclass = {cs.LG}, author = {Gasse, Maxime and Bowly, Simon and Cappart, Quentin and Charfreitag, Jonas and Charlin, Laurent and Chételat, Didier and Chmiela, Antonia and Dumouchelle, Justin and Gleixner, Ambros and Kazachkov, Aleksandr M. and Khalil, Elias and Lichocki, Pawel and Lodi, Andrea and Lubin, Miles and Maddison, Chris J. and Christopher, Morris and Papageorgiou, Dimitri J. and Parjadis, Augustin and Pokutta, Sebastian and Prouvost, Antoine and Scavuzzo, Lara and Zarpellon, Giulia and Yang, Linxin and Lai, Sha and Wang, Akang and Luo, Xiaodong and Zhou, Xiang and Huang, Haohan and Shao, Shengcheng and Zhu, Yuanming and Zhang, Dong and Quan, Tao and Cao, Zixuan and Xu, Yang and Huang, Zhewei and Zhou, Shuchang and Binbin, Chen and Minggui, He and Hao, Hao and Zhiyu, Zhang and Zhiwu, An and Kun, Mao}, title = {The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights} } - 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} } - Bolusani, S., Coniglio, S., Ralphs, T. K., and Tahernejad, S. (2021). A Unified Framework for Multistage Mixed Integer Linear Optimization.
[arXiv]
[BibTeX]
@misc{BolConRalTah20, archiveprefix = {arXiv}, eprint = {2104.09003}, primaryclass = {math.OC}, year = {2021}, author = {Bolusani, Suresh and Coniglio, Stefano and Ralphs, Ted K. and Tahernejad, Sahar}, title = {A Unified Framework for Multistage Mixed Integer Linear Optimization} } - Hoppmann-Baum, K., Mexi, G., Burdakov, O., Casselgren, C. J., and Koch, T. (2020). Minimum Cycle Partition with Length Requirements. Proceedings of International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 12296, 273–282.
DOI: 10.1007/978-3-030-58942-4_18
[BibTeX]
@inproceedings{HoppmannBaumMexiBurdakovetal.2020, year = {2020}, booktitle = {Proceedings of International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, volume = {12296}, pages = {273-282}, doi = {10.1007/978-3-030-58942-4_18}, author = {Hoppmann-Baum, Kai and Mexi, Gioni and Burdakov, Oleg and Casselgren, Carl Johan and Koch, Thorsten}, title = {Minimum Cycle Partition with Length Requirements} } - Bestuzheva, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., Gottwald, L., Graczyk, C., Halbig, K., Hoen, A., Hojny, C., van der Hulst, R., Koch, T., Lübbecke, M., Maher, S. J., … Witzig, J. The SCIP Optimization Suite 8.0.
[URL]
[code]
[BibTeX]
@misc{BestuzhevaBesanconEtal2021, url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-85309}, author = {Bestuzheva, Ksenia and Besançon, Mathieu and Chen, Wei-Kun and Chmiela, Antonia and Donkiewicz, Tim and van Doornmalen, Jasper and Eifler, Leon and Gaul, Oliver and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Leona and Graczyk, Christoph and Halbig, Katrin and Hoen, Alexander and Hojny, Christopher and van der Hulst, Rolf and Koch, Thorsten and Lübbecke, Marco and Maher, Stephen J. and Matter, Frederic and Mühmer, Erik and Müller, Benjamin and Pfetsch, Marc and Rehfeldt, Daniel and Schlein, Steffan and Schlösser, Franziska and Serrano, Felipe and Shinano, Yuji and Sofranac, Boro and Turner, Mark and Vigerske, Stefan and Wegscheider, Fabian and Wellner, Philipp and Weninger, Dieter and Witzig, Jakob}, title = {The SCIP Optimization Suite 8.0}, code = {https://scipopt.org} } - Eifler, L., and Gleixner, A. Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework.
[URL]
[BibTeX]
@misc{EiflerGleixner2023_Safeandverified, url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-90159}, author = {Eifler, Leon and Gleixner, Ambros}, title = {Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework} } - Ghannam, M., and Gleixner, A. Hybrid Genetic Search for Dynamic Vehicle Routing with Time Windows.
[arXiv]
[BibTeX]
@misc{HGSforDVRPTW, archiveprefix = {arXiv}, eprint = {2307.11800}, primaryclass = {cs.NE}, author = {Ghannam, Mohammed and Gleixner, Ambros}, title = {Hybrid Genetic Search for Dynamic Vehicle Routing with Time Windows} } - Turner, M., Berthold, T., Besançon, M., and Koch, T. Branching Via Cutting Plane Selection: Improving Hybrid Branching.
[arXiv]
[BibTeX]
@misc{branching_cutsel_23, archiveprefix = {arXiv}, eprint = {2306.06050}, primaryclass = {math.OC}, author = {Turner, Mark and Berthold, Timo and Besançon, Mathieu and Koch, Thorsten}, title = {Branching Via Cutting Plane Selection: Improving Hybrid Branching} } - Tjusila, G., Besançon, M., Turner, M., and Koch, T. How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem.
[arXiv]
[BibTeX]
@misc{sudoku_clues_23, archiveprefix = {arXiv}, eprint = {2305.01697}, primaryclass = {math.OC}, author = {Tjusila, Gennesaret and Besançon, Mathieu and Turner, Mark and Koch, Thorsten}, title = {How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem.} }