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.