We develop theory and solution methodologies for linear and nonlinear mixed-integer optimization programs (MIPs). Our primary focus lies in enhancing the efficiency of integer and spatial branch-and-bound algorithms, which provide a general-purpose approach to finding provable global optima and coordinate within one framework components such as relaxations, cutting planes, primal heuristics, presolving procedures, and other solving techniques. Our group works on all these aspects and their interaction within the constraint integer programming solver SCIP. We also work on algorithms combining satisfiability and MIP techniques such as conflict analysis and domain propagation; on exact MIP and linear programming, guaranteeing that solutions are not invalidated by floating-point arithmetic errors; and on polynomial optimization problems.
Members
bestuzheva (at) zib.de
hoen (at) zib.de
chmiela (at) zib.de
hendrych (at) zib.de
iommazzo (at) zib.de
mexi (at) zib.de
troppens (at) zib.de
manns (at) zib.de
runnwerth (at) zib.de
glessen (at) zib.de
eifler (at) zib.de
miskovic (at) zib.de
ghannam (at) zib.de
ebert (at) zib.de
vigerske (at) zib.de
bolusani (at) zib.de
Projects
- Adaptive Algorithms Through Machine Learning: Exploiting Interactions in Integer Programming (MATH+ EF1-9)
- MiniMIP: a Faster, More Reliable, and Easier Way to Maintain and Solve MIP Problems (miniMIP)
- Learning to Schedule Heuristics in IP
- Expanding Merlin-Arthur Classifiers: Interpretable Neural Networks Through Interactive Proof Systems (MATH+ EF1-67)
- Globally Optimal Neural Network Training (SPP 2298, project number 463910157)
- AI-Based High-Resolution Forest Monitoring
Publications
- Bolusani, S., Besançon, M., Bestuzheva, K., Chmiela, A., Dionísio, J., Donkiewicz, T., van Doornmalen, J., Eifler, L., Ghannam, M., Gleixner, A., Graczyk, C., Halbig, K., Hedtke, I., Hoen, A., Hojny, C., van der Hulst, R., Kamp, D., Koch, T., Kofler, K., … Xu, L. (2024). The SCIP Optimization Suite 9.0 (ZIB Report No. 24-02-29). Zuse Institute Berlin.
[URL]
[arXiv]
[code]
[BibTeX]
- Borst, S., Eifler, L., and Gleixner, A. (2024). Certified Constraint Propagation and Dual Proof Analysis in a Numerically Exact MIP Solver.
[arXiv]
[BibTeX]
- Eifler, L., and Gleixner, A. (2024). Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework. SIAM Journal on Optimization, 34(1), 742–763.
DOI: 10.1137/23M156046X
[URL]
[BibTeX]
- Eifler, L., Witzig, J., and Gleixner, A. (2024). Branch and Cut for Partitioning a Graph Into a Cycle of Clusters. Proceedings of International Symposium on Combinatorial Optimization.
[arXiv]
[BibTeX]
- Ghannam, M., Mexi, G., Lam, E., and Gleixner, A. (2024). Branch and Price for the Length-constrained Cycle Partition Problem. Proceedings of INFORMS Optimization Society Conference.
[URL]
[arXiv]
[BibTeX]
- Halbig, K., Hoen, A., Gleixner, A., Witzig, J., and Weninger, D. (2024). A Diving Heuristic for Mixed-integer Problems with Unbounded Semi-continuous Variables.
[arXiv]
[BibTeX]
- Hoen, A., Oertel, A., Gleixner, A., and Nordström, J. (2024). Certifying MIP-based Presolve Reductions for 0-1 Integer Linear Programs. Proceedings of International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research.
[arXiv]
[BibTeX]
- Sharma, K., Hendrych, D., Besançon, M., and Pokutta, S. (2024). Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe. Proceedings of INFORMS Optimization Society Conference.
[arXiv]
[BibTeX]
- Hendrych, D., Besançon, M., and Pokutta, S. (2024). Solving the Optimal Experiment Design Problem with Mixed-integer Convex Methods. Proceedings of Symposium on Experimental Algorithms.
[arXiv]
[BibTeX]
- Göß, A., Martin, A., Pokutta, S., and Sharma, K. (2024). Norm-induced Cuts: Optimization with Lipschitzian Black-box Functions.
[URL]
[arXiv]
[BibTeX]
- Mexi, G., Shamsi, S., Besançon, M., and le Bodic, P. (2024). Probabilistic Lookahead Strong Branching Via a Stochastic Abstract Branching Model. Proceedings of International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research.
[arXiv]
[BibTeX]
- Tjusila, G., Besançon, M., Turner, M., and Koch, T. (2024). How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem. Operations Research Letters.
DOI: 10.1016/j.orl.2024.107105
[URL]
[arXiv]
[BibTeX]
- 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]
- 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]
- Bestuzheva, K., Chmiela, A., Müller, B., Serrano, F., Vigerske, S., and Wegscheider, F. (2023). Global Optimization of Mixed-integer Nonlinear Programs with SCIP 8.0. Journal of Global Optimization.
DOI: 10.1007/s10898-023-01345-1
[URL]
[arXiv]
[BibTeX]
- Bestuzheva, K., Gleixner, A., and Achterberg, T. (2023). Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products. Proceedings of Conference on Integer Programming and Combinatorial Optimization, 14–28.
DOI: 10.1007/978-3-031-32726-1_2
[arXiv]
[BibTeX]
- Bestuzheva, K., Gleixner, A., and Vigerske, S. (2023). A Computational Study of Perspective Cuts. Mathematical Programming Computation, 15, 703–731.
DOI: 10.1007/s12532-023-00246-4
[URL]
[arXiv]
[BibTeX]
- Bolusani, S., Besançon, M., Gleixner, A., Berthold, T., D’Ambrosio, C., Muñoz, G., Paat, J., and Thomopulos, D. (2023). The MIP Workshop 2023 Computational Competition on Reoptimization.
[arXiv]
[BibTeX]
- 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., Muñoz, G., and Serrano, F. (2023). Monoidal Strengthening and Unique Lifting in MIQCPs. Proceedings of Conference on Integer Programming and Combinatorial Optimization.
[URL]
[BibTeX]
- 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
[BibTeX]
- Ghannam, M., and Gleixner, A. (2023). Hybrid Genetic Search for Dynamic Vehicle Routing with Time Windows. Proceedings of Conference of the Society for Operations Research in Germany.
[arXiv]
[BibTeX]
- 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]
- 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]
- Turner, M., Chmiela, A., Koch, T., and Winkler, M. (2023). PySCIPOpt-ML: Embedding Trained Machine Learning Models Into Mixed-integer Programs.
[arXiv]
[BibTeX]
- Eifler, L., Nicolas-Thouvenin, J., and Gleixner, A. (2023). Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization.
[arXiv]
[BibTeX]
- 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]
- 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]
- 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), 280, 27:1–27:19,
DOI: 10.4230/LIPIcs.CP.2023.27
[BibTeX]
- 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]
- van Doornmalen, J., Eifler, L., Gleixner, A., and Hojny, C. (2023). A Proof System for Certifying Symmetry and Optimality Reasoning in Integer Programming.
[arXiv]
[BibTeX]
- 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. (2022). 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]
- Bestuzheva, K., Gleixner, A., and Völker, H. (2022). Strengthening SONC Relaxations with Constraints Derived From Variable Bounds. Proceedings of Proceedings of the Hungarian Global Optimization Workshop HUGO 2022, 41–44.
[URL]
[arXiv]
[BibTeX]
- 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]
- Chmiela, A., Muñoz, G., and Serrano, F. (2022). On the Implementation and Strengthening of Intersection Cuts for QCQPs. Mathematical Programming B, 197, 549–586.
DOI: 10.1007/s10107-022-01808-5
[BibTeX]
- 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]
- 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]
- Iommazzo, G., D’Ambrosio, C., Frangioni, A., and Liberti, L. (2022). Algorithm Configuration Problem. In Encyclopedia of Optimization (pp. 1–8).
DOI: 10.1007/978-3-030-54621-2_749-1
[BibTeX]
- 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]
- 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]
- Hendrych, D., Troppens, H., Besançon, M., and Pokutta, S. (2022). Convex Integer Optimization with Frank-Wolfe Methods.
[arXiv]
[slides]
[code]
[BibTeX]
- Kossen, T., Hirzel, M. A., Madai, V. I., Boenisch, F., Hennemuth, A., Hildebrand, K., Pokutta, S., Sharma, K., Hilbert, A., Sobesky, J., Galinovic, I., Khalil, A. A., Fiebach, J. B., and Frey, D. (2022). Towards Sharing Brain Images: Differentially Private TOF-MRA Images with Segmentation Labels Using Generative Adversarial Networks. Frontiers in Artificial Intelligence.
DOI: 10.3389/frai.2022.813842
[BibTeX]
- 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. (2021). The SCIP Optimization Suite 8.0 (ZIB Report No. 21-41). Zuse Institute Berlin.
[URL]
[code]
[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]
- Bolusani, S., Coniglio, S., Ralphs, T. K., and Tahernejad, S. (2021). A Unified Framework for Multistage Mixed Integer Linear Optimization.
[arXiv]
[BibTeX]
- Ramin, E., Bestuzheva, K., Gargalo, C., Ramin, D., Schneider, C., Ramin, P., Flores-Alsina, X., Andersen, M., and Gernaey, K. (2021). Incremental Design of Water Symbiosis Networks with Prior Knowledge: the Case of an Industrial Park in Kenya. Science of the Total Environment, 751.
DOI: 10.1016/j.scitotenv.2020.141706
[BibTeX]
- 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]
- Turner, M., Berthold, T., Besançon, M., and Koch, T. Branching Via Cutting Plane Selection: Improving Hybrid Branching.
[arXiv]
[BibTeX]