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

Abstract

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.