Convex Solver Adaptivity for Mixed-integer Optimization ongoing

We will investigate mixed-integer optimization with convex objectives using error-adaptive convex solvers in branch-and-bound. Focusing on improving lower bounds and balancing computational costs, we aim to develop a faster branch-and-bound methodology by leveraging modern MILP techniques and error-adaptive methods. Key aspects include warm-starting and controlled inexactness in early termination.

MATH+ AA3-15
Apr 2023 to Mar 2026
4
2

🧑‍🎓 Project Members

Mathieu Besançon
Principal Investigator
besancon (at) zib.de
Ralf Borndörfer
Principal Investigator
borndoerfer (at) zib.de
Sebastian Pokutta
Principal Investigator
pokutta (at) zib.de
Deborah Hendrych
hendrych (at) zib.de

🪙 Funding

This project is being funded by the Berlin Mathematics Research Center MATH+ (project ID AA3-15), itself funded by the German Research Foundation (DFG) under Germany's Excellence Strategy (EXC-2046/1, project ID 390685689) from April 2023 to March 2026.

🔬 Project Description

In this project, we aim to investigate mixed-integer optimization problems with a convex, differentiable objective. The focus is on solution approaches based on error-adaptive first-order convex solvers, in particular Frank-Wolfe methods, within a branch-and-bound framework. Our primary objective is to enhance lower bound improvements within the solution tree and analyze the trade-off between the increase in lower bounds and the computational costs of strong relaxations. Our research intends to develop a branch-and-bound-based methodology for mixed-integer convex problems, accelerating the solution process by leveraging the specific characteristics of modern mixed-integer linear programming (MILP) techniques and error-adaptive first-order methods. Two key aspects to be developed and exploited are warm-starting strategies in convex and mixed-integer linear optimization, and early termination methods resulting in the controlled inexactness of certain oracles. Over the course of this project, we develop and maintain a new convex mixed-integer solver written in Julia, named Boscia.jl.

📝 Publications and preprints

  1. 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. DOI: 10.4230/LIPIcs.SEA.2024.16 [arXiv] [code]
    [BibTeX]
    @inproceedings{2023_HendrychBesanconPokutta_Optimalexperimentdesign,
  year = {2024},
  booktitle = {Proceedings of Symposium on Experimental Algorithms},
  doi = {10.4230/LIPIcs.SEA.2024.16},
  archiveprefix = {arXiv},
  eprint = {2312.11200},
  primaryclass = {math.OC},
  author = {Hendrych, Deborah and Besançon, Mathieu and Pokutta, Sebastian},
  title = {Solving the Optimal Experiment Design Problem with Mixed-integer Convex Methods},
  code = {https://github.com/ZIB-IOL/OptimalDesignWithBoscia}
}
  2. Hendrych, D., Troppens, H., Besançon, M., and Pokutta, S. (2022). Convex Integer Optimization with Frank-Wolfe Methods. [arXiv] [slides] [code]
    [BibTeX]
    @misc{2022_HendrychTroppensBesanconPokutta_Convexintegerfrankwolfe,
  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}
}