A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
Abstract
We propose a primal heuristic for quadratic mixed-integer problems. Our method extends the Boscia framework – originally a mixed-integer convex solver leveraging a Frank-Wolfe-based branch-and-bound approach – to address nonconvex quadratic objective functions and constraints. We reformulate nonlinear constraints, introduce preprocessing steps, and a suite of heuristics including rounding strategies, gradient-guided selection, and large neighborhood search techniques that exploit integer-feasible vertices generated during the Frank-Wolfe iterations. Computational results demonstrate the effectiveness of our method in solving challenging MIQCQPs, achieving improvements on QPLIB instances within minutes and winning first place in the Land-Doig MIP Computational Competition 2025.
Related
- Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization
- Global Optimization of Mixed-Integer Bound-Constrained Quadratic Fractional Problems
- On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
- Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization
- Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
BibTeX
@article{mexi2026frankwolfebased,
title = {{A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization}},
author = {Gioni Mexi and Deborah Hendrych and Sébastien Designolle and Mathieu Besançon and Sebastian Pokutta},
journal = {Mathematical Programming Computation},
year = {2026},
month = sep,
doi = {10.1007/s12532-026-00340-3},
url = {https://inria.hal.science/hal-05775584v1},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
AU - Gioni Mexi
AU - Deborah Hendrych
AU - Sébastien Designolle
AU - Mathieu Besançon
AU - Sebastian Pokutta
PY - 2026
DA - 2026/09/03
JO - Mathematical Programming Computation
DO - 10.1007/s12532-026-00340-3
UR - https://inria.hal.science/hal-05775584v1
AB - We propose a primal heuristic for quadratic mixed-integer problems. Our method extends the Boscia framework – originally a mixed-integer convex solver leveraging a Frank-Wolfe-based branch-and-bound approach – to address nonconvex quadratic objective functions and constraints. We reformulate nonlinear constraints, introduce preprocessing steps, and a suite of heuristics including rounding strategies, gradient-guided selection, and large neighborhood search techniques that exploit integer-feasible vertices generated during the Frank-Wolfe iterations. Computational results demonstrate the effectiveness of our method in solving challenging MIQCQPs, achieving improvements on QPLIB instances within minutes and winning first place in the Land-Doig MIP Computational Competition 2025.
SN - 1867-2949
SN - 1867-2957
ER -