Weimin Huang, Natalie M. Isenberg, Ján Drgoňa, Draguna L Vrabie, Bistra Dilkina

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

Introduction

Efficient primal heuristics for mixed binary quadratic programs using suboptimal rounding guidance. Discover efficient primal heuristics for Mixed Binary Quadratic Programs (MBQPs) using suboptimal rounding guidance. Improves RENS and Undercover, finding high-quality solutions and significantly reducing primal gaps.

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.

Review

This paper addresses the challenging problem of solving Mixed Binary Quadratic Programs (MBQPs), which are known to be NP-hard and arise in diverse high-impact applications ranging from finance to energy systems. Given the computational intractability of exact methods for large-scale instances, the development of effective primal heuristics is crucial for identifying high-quality solutions within practical time limits. The authors propose a novel extension to two well-established rounding-based primal heuristics, RENS and Undercover, aiming to improve their efficiency and solution quality. This work offers a valuable contribution to the field of combinatorial optimization by exploring alternative strategies for primal solution generation. The core of the proposed methodology lies in leveraging suboptimal relaxation solutions as guidance for rounding and subproblem construction, a departure from the conventional use of optimal relaxation solutions. For RENS, the authors propose using a suboptimal relaxation solution to guide variable rounding and define a restricted subproblem where a percentage of binary variables are freed. Similarly, for Undercover, a subset of cover variables is relaxed based on the suboptimal solution, leading to a search over a larger restricted subproblem. This approach subtly re-frames the use of relaxation information, suggesting that a quickly obtainable, albeit suboptimal, relaxation can still provide effective guidance for primal heuristics, potentially leading to faster convergence to good solutions. The evaluation of the proposed methods on both synthetic MBQP benchmarks and real-world wind farm layout optimization problems demonstrates their effectiveness. The results indicate that these extended heuristics are capable of identifying high-quality solutions within tight time limits. Crucially, the paper reports a significant reduction in primal gap and primal integral when compared against the original RENS and Undercover heuristics, as well as against commercial solvers incorporating their own primal heuristics within the Branch-and-Bound framework. This suggests that the suboptimal rounding guidance strategy is a promising avenue for improving the practical performance of primal heuristics for MBQPs, offering a valuable tool for practitioners facing large and complex optimization challenges.

Full Text

Comments

You need to be logged in to post a comment.