Oracle-Based Primal Heuristics for Mixed-Integer Nonlinear Programming
This project develops oracle-based primal heuristic strategies for mixed-integer nonlinear programming (MINLP). Rather than relying on expensive interior-point solves, the approach leverages fast first-order oracles—Frank-Wolfe, conditional gradient, and proximal methods—to generate high-quality primal solutions within an MINLP branch-and-cut framework, targeting problems where traditional nonlinear solvers become prohibitively expensive.
IOL Project Members
Funding
This project is being funded by the Berlin Mathematics Research Center MATH+ (project ID AA-Mobil-4), itself funded by the German Research Foundation (DFG) under Germany's Excellence Strategy (EXC-2046/1, project ID 390685689) from October 2026 to September 2029.
Project Description
Mixed-integer nonlinear programming (MINLP) remains one of the most challenging classes of optimization problems. While Branch-and-Bound and spatial branching frameworks have made progress for convex and mildly nonconvex problems, the bottleneck is often generating high-quality primal solutions early in the search, which is essential for effective pruning, variable fixing, and node selection.
This project investigates oracle-based primal heuristics that replace expensive nonlinear solves with fast first-order methods. By leveraging Frank-Wolfe, conditional gradient, and related proximal oracles, we aim to build heuristics that:
- Scale to large instances where interior-point methods are infeasible;
- Exploit problem structure through tailored oracles (e.g., linear minimization over feasible sets);
- Integrate seamlessly into existing MINLP solvers as callbacks and decomposition plugins.
- Combine with rounding, feasibility pumps, and sub-MIP heuristics to improve primal bound quality across benchmark and real-world instances.
The project builds on recent advances in first-order methods for integer optimization and aims to establish oracle-based heuristics as a standard tool in the MINLP solver toolbox.
Talks and posters
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, Tokyo
Publications and preprints
Full articles
- 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}, journal = {Mathematical Programming Computation}, date = {2026-09-03}, 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} }