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.
🧑🎓 Project Members
🪙 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
- 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{design_of_experiments_boscia_23, 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} }
- 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} }