Header Image

Global Optimization

mixed-integer nonlinear programming; nonconvex optimization; spatial branch-and-bound; SCIP Optimization Suite

Ksenia Bestuzheva

What we are interested in

We aim at developing efficient global optimization methods for convex and nonconvex mixed-integer nonlinear programming (MINLP) problems. MINLP encompasses a wide range of optimization problems arising in chemical engineering, power systems operation and planning, layout design, and water network optimization, to name but a few. The emphasis of our work is on improving the performance of spatial branch-and-bound algorithms, which provide a general-purpose approach to finding global optima and bring together solving techniques such as relaxations, primal heuristics, presolving procedures and others. A particular focus is on creating new relaxation schemes and domain reduction techniques, which provide dual bounds that serve as optimality proofs.

Our research is closely linked with the development of the nonlinear functionality of the constraint integer programming solver SCIP. SCIP implements a spatial branch-and-cut algorithm that can handle general MINLP problems. Its plugin-based structure allows easy addition of new expression types and new solving techniques. SCIP is one of the leading MINLP solvers.

Researchers

Ksenia Bestuzheva
bestuzheva (at) zib.de
Antonia Chmiela
chmiela (at) zib.de
Deborah Hendrych
hendrych (at) zib.de
Hannah Troppens
troppens (at) zib.de
Julian Manns
manns (at) zib.de
Mathieu Besançon
besancon (at) zib.de
Stefan Vigerske
vigerske (at) zib.de

Projects

Publications

  1. 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}
}
  2. 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. [URL] [arXiv]
    [BibTeX]
    @misc{BestuzhevaChmielaMueller2023_GlobalOptimizationOfMixedInteger,
  url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-89348},
  archiveprefix = {arXiv},
  eprint = {2301.00587},
  primaryclass = {math.OC},
  year = {2023},
  author = {Bestuzheva, Ksenia and Chmiela, Antonia and Müller, Benjamin and Serrano, Felipe and Vigerske, Stefan and Wegscheider, Fabian},
  title = {Global Optimization of Mixed-integer Nonlinear Programs with SCIP 8.0}
}
  3. 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]
    @inproceedings{BestuzhevaGleixnerAchterberg2023_EfficientSeparationOfRLT,
  year = {2023},
  booktitle = {Proceedings of Conference on Integer Programming and Combinatorial Optimization},
  pages = {14-28},
  doi = {10.1007/978-3-031-32726-1_2},
  archiveprefix = {arXiv},
  eprint = {2211.13545},
  primaryclass = {math.OC},
  author = {Bestuzheva, Ksenia and Gleixner, Ambros and Achterberg, Tobias},
  title = {Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products}
}
  4. 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]
    @article{BestuzhevaGleixnerVigerske2023,
  year = {2023},
  journal = {Mathematical Programming Computation},
  volume = {15},
  pages = {703-731},
  doi = {10.1007/s12532-023-00246-4},
  url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-81821},
  archiveprefix = {arXiv},
  eprint = {2103.09573},
  primaryclass = {math.OC},
  author = {Bestuzheva, Ksenia and Gleixner, Ambros and Vigerske, Stefan},
  title = {A Computational Study of Perspective Cuts}
}
  5. 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]
    @inproceedings{ChmielaMunozSerrano2023_Monoidal,
  year = {2023},
  booktitle = {Proceedings of Conference on Integer Programming and Combinatorial Optimization},
  url = {https://gonzalomunoz.org/monoidalforMIQCP.pdf},
  author = {Chmiela, Antonia and Muñoz, Gonzalo and Serrano, Felipe},
  title = {Monoidal Strengthening and Unique Lifting in MIQCPs}
}
  6. 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]
    @inproceedings{BestuzhevaGleixnerVoelker2022_StrengtheningSONC,
  year = {2022},
  booktitle = {Proceedings of Proceedings of the Hungarian Global Optimization Workshop HUGO 2022},
  pages = {41-44},
  url = {https://inf.u-szeged.hu/hugo/},
  archiveprefix = {arXiv},
  eprint = {2304.12145},
  primaryclass = {math.OC},
  author = {Bestuzheva, Ksenia and Gleixner, Ambros and Völker, Helena},
  title = {Strengthening SONC Relaxations with Constraints Derived From Variable Bounds}
}
  7. 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]
    @article{ChmielaMunozSerrano2021_Onimplementation,
  year = {2022},
  journal = {Mathematical Programming B},
  volume = {197},
  pages = {549-586},
  doi = {10.1007/s10107-022-01808-5},
  author = {Chmiela, Antonia and Muñoz, Gonzalo and Serrano, Felipe},
  title = {On the Implementation and Strengthening of Intersection Cuts for QCQPs}
}
  8. Hendrych, D., Troppens, H., Besançon, M., and Pokutta, S. (2022). Convex Integer Optimization with Frank-Wolfe Methods. [arXiv] [slides] [code]
    [BibTeX]
    @misc{htbp_cio_22,
  archiveprefix = {arXiv},
  eprint = {2208.11010},
  primaryclass = {math.OC},
  year = {2022},
  author = {Hendrych, Deborah and Troppens, Hannah and Besançon, Mathieu and Pokutta, Sebastian},
  title = {Convex Integer Optimization with Frank-Wolfe Methods},
  code = {https://github.com/ZIB-IOL/Boscia.jl},
  slides = {https://pokutta.com/slides/20220915_boscia.pdf}
}
  9. 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]
    @article{khmbhhpshsgkff_22,
  year = {2022},
  journal = {Frontiers in Artificial Intelligence},
  doi = {10.3389/frai.2022.813842},
  author = {Kossen, Tabea and Hirzel, Manuel A. and Madai, Vince I. and Boenisch, Franziska and Hennemuth, Anja and Hildebrand, Kristian and Pokutta, Sebastian and Sharma, Kartikey and Hilbert, Adam and Sobesky, Jan and Galinovic, Ivana and Khalil, Ahmed A. and Fiebach, Jochen B. and Frey, Dietmar},
  title = {Towards Sharing Brain Images: Differentially Private TOF-MRA Images with Segmentation Labels Using Generative Adversarial Networks}
}
  10. 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}
}
  11. 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]
    @article{RaminBestuzhevaGargalo2021_IncrementalDesignOfWater,
  year = {2021},
  journal = {Science of the Total Environment},
  volume = {751},
  doi = {10.1016/j.scitotenv.2020.141706},
  author = {Ramin, Elham and Bestuzheva, Ksenia and Gargalo, Carina and Ramin, Danial and Schneider, Carina and Ramin, Pedram and Flores-Alsina, Xavier and Andersen, Maj and Gernaey, Krist},
  title = {Incremental Design of Water Symbiosis Networks with Prior Knowledge: the Case of an Industrial Park in Kenya}
}
  12. 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}
}
  13. Goess, A., Martin, A., Pokutta, S., and Sharma, K. Norm-induced Cuts: Optimization with Lipschitzian Black-box Functions. [URL]
    [BibTeX]
    @misc{gmps_nic_23,
  url = {https://opus4.kobv.de/opus4-trr154/files/518/nic_preprint.pdf},
  author = {Goess, Adrian and Martin, Alexander and Pokutta, Sebastian and Sharma, Kartikey},
  title = {Norm-induced Cuts: Optimization with Lipschitzian Black-box Functions}
}