ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs
Weimin Huang, Natalie M. Isenberg, Ján Drgoňa, Draguna L Vrabie, Bistra Dilkina · 2026
Read ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs by Weimin Huang, Natalie M. Isenberg, Ján Drgoňa, Draguna L Vrabie, Bistra Dilkina (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23053.txt.
Introduction
Huang and four colleagues propose machine-learning-guided primal heuristics for mixed binary quadratic programs, adapting methods previously focused on mixed-integer linear programs. A new neural network architecture predicts solutions, with a new training data collection procedure and extended loss functions combining contrastive and weighted cross-entropy losses. On standard and real-world benchmarks, the machine-learning-guided methods clearly beat existing primal heuristics and the best current solvers. Models trained with the combined losses also generalize better across regions on a real-world wind farm layout problem.
Catalog record
| CREATOR | Weimin Huang, Natalie M. Isenberg, Ján Drgoňa, Draguna L Vrabie, Bistra Dilkina |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40248 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.23053
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs Weimin Huang, Natalie M. Isenberg, Ján Drgoňa, Draguna L Vrabie, Bistra Dilkina Abstract Mixed Binary Quadratic Programs (MBQPs) are an important and complex set of problems in combinatorial optimization. As solving large-scale combinatorial optimization problems is challenging, primal heuristics have been developed to quickly identify high-quality solutions within a short amount of time. Recently, a growing body of research has also used machine learning to accelerate solution methods for challenging combinatorial optimization problems. Despite the increasing popularity of these ML-guided methods, a large body of work has focused on Mixed-Integer Linear Programs (MILPs). MBQPs are challenging to solve due to the combinatorial complexity coupled with nonlinearities. This work proposes ML-guided primal heuristics for Mixed Binary Quadratic Programs (MBQPs) by adapting and extending existing work on ML-guided MILP solution prediction to MBQPs. We introduce a new neural network architecture for MBQP solution prediction and a new training data collection procedure. Moreover, we extend existing loss functions in solution prediction and propose to combine contrastive and weighted cross-entropy losses. We evaluate the methods on standard and real-world MBQP benchmarks and show that the developed ML-guided methods significantly outperform existing primal heuristics and state-of-the-art solvers. Furthermore, models trained with our proposed extension with combined losses outperform other ML-based methods adapted from MILPs and improve generalization in cross-regional inference on a real-world wind farm layout optimization problem. Introduction Mixed Binary Quadratic Programs (MBQPs) are discrete optimization problems with quadratic terms in the objective function subject to a set of linear constraints. MBQPs encode many important problems in Combinatorial Optimization (CO) ( 27 ; 35 ; 23 ) and cover a wide range of applications, including finance ( 33 ) , machine learning ( 6 ) , as well as chemical ( 31 ) and energy systems ( 39 ) . A significant body of research on CO algorithms has focused on primal heuristics , which are algorithms designed to find good feasible solutions quickly and without optimality guarantees ( 5 ) . Despite development in solvers and heuristics, solving large-scale COs remains challenging. In recent years, Machine Learning (ML) has been proposed to accelerate solution methods for CO problems. Motivated by the fact that CO problems that share similar structures are solved repeatedly in many applications ( 21 ; 37 ) , a growing body of research uses ML to guide algorithmic policies or to build new policies customized to instances that appear in specific applications. For example, 19 ; 32 ; 20 ; 13 proposed ML-guided primal heuristics for Mixed Integer Linear Programs (MILPs), wherein they predict the optimal assignment for a subset of the variables. While prior work on ML-guided CO methods has shown success across multiple algorithmic components on many challenging CO problems, existing work in this area has mainly focused on MILPs. A small body of research has used ML to advance solution methods for general nonlinear programming problems ( 9 ; 1 ; 17 ; 14 ; 38 ; 14 ) , but ML-guided methods in this space are not as well developed as in MILPs. MBQPs are even more challenging to solve than MILPs due to the combinatorial nature ( 29 ) coupled with nonlinearities. In this work, we develop ML-guided primal heuristics for MBQPs by adapting and extending existing work on ML-guided MILP solution methods. We adapt the Weighted Cross-Entropy-based and Contrastive Learning-based methods which are used in MILP solution prediction to MBQPs. To adapt to MBQPs, we propose a novel neural network architecture that extracts input features and a new data collection procedure that generates high-quality solutions as ground truth training data for large-scale MBQPs. Furthermore, we extend existing loss functions used in CO solution prediction and propose to combine Cross-Entropy and Contrastive losses. Computational results show that the adapted and extended ML methods outperform existing primal heuristics and state-of-the-art solvers on standard and real-world MBQP benchmarks. Furthermore, we show that solution prediction models trained with our proposed extended loss function outperform other ML-guided methods adapted from MILPs in in-domain testing and improve generalization in cross-regional inference on a real-world wind farm layout optimization problem. Background and Related Works Mixed Binary Quadratic Programs A Mixed Binary Quadratic Program (MBQP) with n decision variables is defined as \min x^{T}Hx+c^{T}x\quad\text{s.t.}\;Ax\leq b\;\text{and}\;x_{j}\in\{0,1\},\forall j\in B (1) where H\in\mathbb{R}^{n\times n} , c\in\mathbb{R}^{n} , A\in\mathbb{R}^{m\times n} , and b\in\mathbb{R}^{m} . H is a real symmetric matrix that encodes quadratic terms in the objective function and is not necessarily positive semidefinite, allowing for nonconvex objective functions. B\subseteq\{1,...,n\} is the set of binary decision variables. Solution Methods MBQPs are NP-hard in general ( 34 ) . The Branch-and-Bound (BnB) algorithm is an exact tree search algorithm to solve MILPs, MBQPs and more general Mixed-Integer Nonlinear Programming (MINLP) problems. As large-scale MBQPs are challenging to solve with exact methods, a significant body of research has focused on primal heuristics , which are algorithms designed to quickly identify high-quality feasible solutions for a given optimization problem without optimality guarantees ( 5 ) . These heuristics typically involve solving a relaxation of the original problem and then creating a subproblem by fixing a subset of integer variables by rounding the relaxation values to the nearest integer values, such as RENS ( 5 ) , Undercover ( 3 ) , and Relax-Search ( 22 ) . Solution Prediction for MILPs Previous work on using ML to accelerate solving CO problems has been focused on Mixed Integer Linear Programming (MILP). An MILP can be viewed as the subclass of MBQPs in Eqn. ( 1 ) where the quadratic term matrix H is the zero matrix. The goal of an MILP is to find x such that c^{T}x is minimized, subject to Ax\leq b and integrality constraints x_{j}\in\{0,1\},\forall j\in B . A large body of ML-guided primal heuristics for MILPs are based on predicting partial solutions ( 32 ; 19 ; 20 ; 13 ) . Solution Prediction 32 and 19 use Weighted Cross-Entropy (WCE) loss to learn the probability distribution of the solution space of an MILP instance M . The goal is to learn from a set of multiple solutions, weighted by the quality of the solution. Specifically, for a solution x , the energy function E(x;M) is defined as c^{T}x if x is feasible, or \infty otherwise, assuming minimization. Given M , the conditional distribution of a solution x is modeled as \displaystyle P(x|M)\equiv\frac{\text{exp}(-E(x;M))}{\sum_{x^{\prime}}\text{exp}(-E(x^{\prime};M))} (2) , so that solutions with better objective values have a higher probability. The learning task is to train a model p(x|\theta,M) parameterized by \theta that approximates p(x|M) . To collect training data, 32 and 19 obtain the set of solutions by running state-of-the-art MILP solvers for a large amount of time. Instead of using WCE loss, 20 learn p(x|\theta,M) using Contrastive Learning (CL). The CL-based method makes discriminative predictions by contrasting the positive samples (i.e., good solutions) and negative samples (i.e., bad solutions). Positive samples are obtained by running MILP solvers, similar to ( 32 ) and ( 19 ) . Negative samples are obtained by solving another MILP that searches for bad variable assignments within some Hamming distance of the good solutions. Inference Since the full prediction might not be feasible, ML-guided primal