AdaptMIO MATH+ AA3-15 completed

Convex Solver Adaptivity for Mixed-Integer Optimization

This project investigates mixed-integer optimization with convex objectives using error-adaptive convex solvers in branch-and-bound. The goal is to develop a faster branch-and-bound methodology by leveraging modern MILP techniques and error-adaptive methods, with key aspects including warm-starting and controlled inexactness in early termination.

IOL Project Members

Sebastian PokuttaTU/PR/Dominic Simon
Sebastian Pokutta Principal Investigator
Mathieu Besançon
Mathieu Besançon Project Member · Alumni

External Project Members

Ralf Borndörfer
Ralf Borndörfer Principal Investigator

Funding

This project was 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.

Talks and posters

Conference and workshop talks

Jun 2026
Integer Frank-Wolfe for Optimal Experiment Design by Deborah Hendrych
SIAM conference on optimization (SIAMOP), Edinburgh
Jun 2026
Exact Solutions for the Graph Isomorphism with Convex Mixed Integer Optimization by Wenjie Xiao
SIAM conference on optimization (SIAMOP), Edinburgh
May 2026
The Graph Isomorphism Problem From a Mixed-Integer Convex Optimization Perspective by Wenjie Xiao
23rd CPAIOR Conference, Rabat
Sep 2025
Optimal Experiment Design with Mixed-Integer Convex Methods by Deborah Hendrych
16th Global Optimization Workshop (STOGO), Stockholm
Jul 2025
Solving the Optimal Design Problem with Mixed-Integer Convex Methods by Deborah Hendrych
22nd Conference on Advances in Continuous Optimization (EUROPT), Southampton
Jul 2024
Solving the Optimal Design Problem with Mixed-Integer Convex Methods by Deborah Hendrych
22nd Symposium on Experimental Algorithms (SEA), Vienna

Research seminar talks

Mar 2025
Decomposition-Invariant Frank-Wolfe Method in Mixed-Integer Convex Optimization with an Application to Graph Isomorphism by Wenjie Xiao
IOL Research Seminar (IOL), Berlin
Nov 2024
Solving the Optimal Design Problem with Mixed-Integer Convex Methods by Deborah Hendrych
GHOST Research Seminar (GHOST), Grenoble
Jul 2024
Solving the Optimal Design Problem with Mixed-Integer Convex Methods by Deborah Hendrych
NASPDE Seminar, Berlin
May 2024
Solving the Optimal Design Problem with Mixed-Integer Convex Methods by Deborah Hendrych
MATH+ Spotlight talks, Berlin

Poster presentations

Jul 2026
Recent Improvements on the Integer Frank-Wolfe Framework by Deborah Hendrych
ICOML Conference, Taipei
Jul 2026
Recent Improvements on the Integer Frank-Wolfe Framework by Deborah Hendrych
8th DOxML Conference, Ookayama

Publications and preprints

Preprints and reports

  1. Sharma, K., Hendrych, D., Besançon, M., and Pokutta, S. (2024). Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe. [arXiv]
    [BibTeX]
    @misc{2024_SharmaHendrychBesanconPokutta_NetworkdesignMicoFrankwolfe,
      archiveprefix = {arXiv},
      eprint = {2402.00166},
      arxiv = {arXiv:2402.00166},
      primaryclass = {math.OC},
      author = {Sharma, Kartikey and Hendrych, Deborah and Besançon, Mathieu and Pokutta, Sebastian},
      title = {Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe},
      date = {2024-01-31}
    }
  2. Xiao, W., Hendrych, D., Besançon, M., and Pokutta, S. (2025). Boscia.jl: A review and tutorial. [arXiv]
    [BibTeX]
    @misc{2025_XiaoHendrychBesanconPokutta_Bosciaminlp_2511-01479,
      archiveprefix = {arXiv},
      eprint = {2511.01479},
      arxiv = {arXiv:2511.01479},
      primaryclass = {math.OC},
      author = {Xiao, Wenjie and Hendrych, Deborah and Besançon, Mathieu and Pokutta, Sebastian},
      title = {Boscia.jl: A review and tutorial},
      date = {2025-11-03}
    }
  3. Zimmer, M., Roux, C., Wagner, M., Hendrych, D., and Pokutta, S. (2025). SparseSwaps: Tractable LLM Pruning Mask Refinement at Scale. [arXiv]
    [BibTeX]
    @misc{2025_ZimmerEtAl_Sparseswapspruning_2512-10922,
      archiveprefix = {arXiv},
      eprint = {2512.10922},
      arxiv = {arXiv:2512.10922},
      primaryclass = {cs.LG},
      author = {Zimmer, Max and Roux, Christophe and Wagner, Moritz and Hendrych, Deborah and Pokutta, Sebastian},
      title = {SparseSwaps: Tractable LLM Pruning Mask Refinement at Scale},
      date = {2025-12-11}
    }
  4. Hendrych, D., Besançon, M., and Pokutta, S. (2026). Discrete eigenvalue optimization from entropic smoothing and first-order methods. [arXiv] [code]
    [BibTeX]
    @misc{2026_HendrychBesanconPokutta_DiscreteEigenvalueOptimization_2608-27024,
      archiveprefix = {arXiv},
      eprint = {2608.27024},
      arxiv = {arXiv:2608.27024},
      primaryclass = {math.OC},
      author = {Hendrych, Deborah and Besançon, Mathieu and Pokutta, Sebastian},
      title = {Discrete eigenvalue optimization from entropic smoothing and first-order methods},
      code = {https://github.com/ZIB-IOL/OptimalDesignWithBoscia},
      date = {2026-08-27}
    }

Conference contributions

  1. Xiao, W., Besançon, M., Gelß, P., Hendrych, D., Klus, S., and Pokutta, S. (2026). Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order Methods. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 16595, 614–630. Associated with CPAIOR 2026. DOI: 10.1007/978-3-032-27242-3_36 [arXiv]
    [BibTeX]
    @inproceedings{2025_XiaoEtAl_GraphisomorphismOptimization_2512-17417,
      year = {2026},
      booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research},
      series = {Lecture Notes in Computer Science},
      volume = {16595},
      publisher = {Springer Science+Business Media},
      pages = {614--630},
      doi = {10.1007/978-3-032-27242-3_36},
      archiveprefix = {arXiv},
      eprint = {2512.17417},
      arxiv = {arXiv:2512.17417},
      primaryclass = {math.OC},
      author = {Xiao, Wenjie and Besançon, Mathieu and Gelß, Patrick and Hendrych, Deborah and Klus, Stefan and Pokutta, Sebastian},
      title = {Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order Methods}
    }
  2. Troppens, H., Besançon, M., Wilken, S. E., and Pokutta, S. (2025). Mixed-Integer Optimization for Loopless Flux Distributions in Metabolic Networks. 23rd International Symposium on Experimental Algorithms (SEA 2025), 338, 26:1–26:18. Associated with SEA 2025. DOI: 10.4230/LIPIcs.SEA.2025.26 [arXiv]
    [BibTeX]
    @inproceedings{2025_TroppensBesanconWilkenPokutta_Mixedintegerloopless,
      year = {2025},
      booktitle = {23rd International Symposium on Experimental Algorithms (SEA 2025)},
      series = {Leibniz International Proceedings in Informatics},
      volume = {338},
      publisher = {Schloss Dagstuhl – Leibniz Center for Informatics},
      month = apr,
      pages = {26:1--26:18},
      doi = {10.4230/LIPIcs.SEA.2025.26},
      archiveprefix = {arXiv},
      eprint = {2502.00807},
      arxiv = {arXiv:2502.00807},
      primaryclass = {math.OC},
      author = {Troppens, Hannah and Besançon, Mathieu and Wilken, St. Elmo and Pokutta, Sebastian},
      title = {Mixed-Integer Optimization for Loopless Flux Distributions in Metabolic Networks}
    }
  3. Hendrych, D., Besançon, M., and Pokutta, S. (2024). Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods. 22nd International Symposium on Experimental Algorithms (SEA 2024), 301, 16:1–16:22. Associated with SEA 2024. DOI: 10.4230/LIPIcs.SEA.2024.16 [arXiv] [code]
    [BibTeX]
    @inproceedings{2023_HendrychBesanconPokutta_Optimalexperimentdesign,
      year = {2024},
      booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)},
      series = {Leibniz International Proceedings in Informatics},
      volume = {301},
      publisher = {Schloss Dagstuhl – Leibniz Center for Informatics},
      month = apr,
      pages = {16:1--16:22},
      doi = {10.4230/LIPIcs.SEA.2024.16},
      archiveprefix = {arXiv},
      eprint = {2312.11200},
      arxiv = {arXiv: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}
    }
  4. Sharma, K., Hendrych, D., Besançon, M., and Pokutta, S. (2024). Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe. Accepted at INFORMS Optimization Society Conference. [arXiv]
    [BibTeX]
    @misc{2024_SharmaHendrychBesanconPokutta_NetworkdesignMicoFrankwolfe:1,
      howpublished = {Accepted at INFORMS Optimization Society Conference},
      year = {2024},
      archiveprefix = {arXiv},
      eprint = {2402.00166},
      arxiv = {arXiv:2402.00166},
      primaryclass = {math.OC},
      author = {Sharma, Kartikey and Hendrych, Deborah and Besançon, Mathieu and Pokutta, Sebastian},
      title = {Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe}
    }

Articles, chapters and books

  1. Mexi, G., Hendrych, D., Designolle, S., Besançon, M., and Pokutta, S. (2026). A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization. Mathematical Programming Computation. DOI: 10.1007/s12532-026-00340-3 [URL] [arXiv] [code]
    [BibTeX]
    @article{2025_MexiEtAl_Frankwolfeheuristic_2508-01299,
      year = {2026},
      date = {2026-09-03},
      journal = {Mathematical Programming Computation},
      month = sep,
      doi = {10.1007/s12532-026-00340-3},
      url = {https://link.springer.com/article/10.1007/s12532-026-00340-3},
      archiveprefix = {arXiv},
      eprint = {2508.01299},
      arxiv = {arXiv:2508.01299},
      primaryclass = {math.OC},
      author = {Mexi, Gioni and Hendrych, Deborah and Designolle, Sébastien and Besançon, Mathieu and Pokutta, Sebastian},
      title = {A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization},
      code = {https://github.com/GioniMexi/FW-MIQCQP-Heuristic}
    }
  2. Hendrych, D., Troppens, H., Besançon, M., and Pokutta, S. (2025). Convex mixed-integer optimization with Frank–Wolfe methods. Mathematical Programming Computation, 17(4), 731–757. DOI: 10.1007/s12532-025-00288-w [URL] [arXiv] [slides] [code]
    [BibTeX]
    @article{2022_HendrychTroppensBesanconPokutta_Convexintegerfrankwolfe,
      year = {2025},
      date = {2025-06-28},
      journal = {Mathematical Programming Computation},
      month = dec,
      volume = {17},
      number = {4},
      pages = {731--757},
      doi = {10.1007/s12532-025-00288-w},
      url = {https://link.springer.com/article/10.1007/s12532-025-00288-w},
      archiveprefix = {arXiv},
      eprint = {2208.11010},
      arxiv = {arXiv:2208.11010},
      primaryclass = {math.OC},
      author = {Hendrych, Deborah and Troppens, Hannah and Besançon, Mathieu and Pokutta, Sebastian},
      title = {Convex mixed-integer optimization with Frank–Wolfe methods},
      code = {https://github.com/ZIB-IOL/Boscia.jl},
      slides = {https://pokutta.com/slides/20220915_boscia.pdf}
    }