# Efficient Primal Heuristics for Mixed Binary Quadratic Programs Using Suboptimal Rounding Guidance

arXiv: https://arxiv.org/abs/2501.05052 · HTML: https://mlsanity.com/paper/2501.05052/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jan 2025.

## Built on by (most cited first, 3 of 3)

- [Accelerating Evolution: Integrating PSO Principles into Real-Coded Genetic Algorithm Crossover](https://mlsanity.com/paper/2505.03217/) (2025)
- [Learning to Solve Constrained Bilevel Control Co-Design Problems](https://mlsanity.com/paper/2507.09050/) (2025)
- [ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs](https://mlsanity.com/paper/2604.23053/) (2026)

## Abstract (arXiv)

Mixed Binary Quadratic Programs (MBQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and chemical and energy systems. Large-scale MBQPs are challenging to solve with exact algorithms due to the combinatorial search space and nonlinearity. Primal heuristics have been developed to quickly identify high-quality solutions to challenging combinatorial optimization problems. In this paper, we propose an extension for two well-established rounding-based primal heuristics, RENS and Undercover. Instead of using the optimal solution to a relaxation for variable rounding and search as in RENS, we use a suboptimal relaxation solution of the MBQP as the basis for rounding and guidance for searching over a restricted subproblem where a certain percentage of binary variables are free. We apply a similar idea to the Undercover heuristic that fixes a variable cover to the rounded relaxation values. Instead, we relax a subset of the cover variables based on the suboptimal relaxation and search over a larger restricted subproblem. We evaluate our proposed methods on synthetic MBQP benchmarks and real-world wind farm layout optimization problem instances. The results show that our proposed heuristics identify high-quality solutions within a small time limit and significantly reduce the primal gap and primal integral compared to RENS, Undercover, and solvers with additional primal heuristics integrated inside Branch-and-Bound.