PNNL

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 heuristic algorithms have been developed to quickly identify high-quality solutions to challenging com- binatorial optimization problems. In this paper, we propose an extension for two well-established rounding-based primal heuristics, RENS and Undercover. Instead of starting with the optimal relaxation as in RENS, we use the suboptimal relax- ation of the MBQP as guidance and free a certain percentage of binary variables to improve over the suboptimal rounding in local search. We apply the same idea to the Undercover heuristic that fixes a variable cover based on the rounded re- laxation values and instead relax a subset of cover variables to improve the rounding in the 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 the RENS heuristic, the Undercover heuristic, and solvers with addi- tional primal heuristics integrated inside Branch-and-Bound.