ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs

• URL: http://arxiv.org/abs/2604.23053v1
• Date: Fri, 24 Apr 2026 22:47:25 GMT
• Title: ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs
• Abstract summary: This work proposes ML-guided primals for Mixed Binary Quadratic Programs (MBQPs)<n>We introduce a new neural network architecture for MBQP solution prediction and a new training data collection procedure.<n>We extend existing loss functions in solution prediction and propose to combine contrastive and weighted cross-entropy losses.
• Score: 8.418354309955065
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Mitigating Modality Imbalance in Multi-modal Learning via Multi-objective Optimization [57.00656508727821]
  Multi-modal learning (MML) aims to integrate information from multiple modalities, which is expected to lead to superior performance over single-modality learning.<n>Recent studies have shown that MML can underperform, even compared to single-modality approaches, due to imbalanced learning across modalities.<n>We propose a gradient-based algorithm to solve the modified MML problem.
  arXiv  Detail & Related papers  (2025-11-10T04:16:01Z)
• SolverLLM: Leveraging Test-Time Scaling for Optimization Problem via LLM-Guided Search [58.116954449750544]
  We introduce a training-free framework that leverages test-time scaling to solve diverse optimization problems.<n>Rather than solving directly, it generates mathematical formulations and translates them into solver-ready code, guided by a novel Monte Carlo Tree Search strategy.
  arXiv  Detail & Related papers  (2025-10-19T16:21:19Z)
• Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions [1.342834401139078]
  Quantum Annealing (QA) can efficiently solve optimization problems whose objective functions are represented by Quadratic Unconstrained Binary Optimization (QUBO) formulations.<n>We propose quadratization methods for complex problems involving Machine Learning (ML)<n>In this study, we model target functions by the sum of rectified linear unit bases, which have the ability of universal approximation.<n>We design a new black-box optimization scheme, in which ML surrogate regressors are inputted to QA after the quadratization process.
  arXiv  Detail & Related papers  (2025-06-10T04:50:09Z)
• Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs [6.1860817947800655]
  We train an autoencoder for binary variables in an unsupervised learning fashion.<n>We present a strategy to construct a class of cutting plane constraints from the decoder parameters of an offline-trained AE.<n>Their integration into the primal MIP problem leads to a tightened MIP with the reduced feasible region.
  arXiv  Detail & Related papers  (2024-12-23T14:48:32Z)
• RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs [3.3894236476098185]
  We propose RL-SPH, a novel reinforcement learning-based start primal capable of independently generating feasible solutions even for ILP involving non-binary integers.<n> Experimental results demonstrate that RL-SPH rapidly obtains high-quality feasible solutions, achieving average a 44x lower primal gap and a 2.3x lower integral compared to existing primals.
  arXiv  Detail & Related papers  (2024-11-29T07:23:34Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  A machine learning (ML) model is trained to emulate a constrained optimization solver. This paper proposes an alternative approach, in which the ML model is trained to predict dual solution estimates directly. It enables an end-to-end training scheme is which the dual objective is as a loss function, and solution estimates toward primal feasibility, emulating a Dual Ascent method.
  arXiv  Detail & Related papers  (2024-03-06T04:43:22Z)
• An Expandable Machine Learning-Optimization Framework to Sequential Decision-Making [0.0]
  We present an integrated prediction-optimization (PredOpt) framework to efficiently solve sequential decision-making problems. We address the key issues of sequential dependence, infeasibility, and generalization in machine learning (ML) to make predictions for optimal solutions to instances problems.
  arXiv  Detail & Related papers  (2023-11-12T21:54:53Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. We introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. We show that our algorithm provides comparable sublinear regret to the existing works.
  arXiv  Detail & Related papers  (2023-10-10T01:39:04Z)
• AI-enhanced iterative solvers for accelerating the solution of large scale parametrized linear systems of equations [0.0]
  This paper exploits up-to-date ML tools and delivers customized iterative solvers of linear equation systems. The results indicate its superiority over conventional iterative solution schemes.
  arXiv  Detail & Related papers  (2022-07-06T09:47:14Z)
• MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers [13.790116387956703]
  Mixed-integer programming (MIP) technology offers a generic way of formulating and solving optimization problems. MIP-GNN is a general framework for enhancing such solvers with data-driven insights. We integrate MIP-GNN into a state-of-the-art MIP solver, applying it to tasks such as node selection and warm-starting.
  arXiv  Detail & Related papers  (2022-05-27T19:34:14Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed. An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed. We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
  arXiv  Detail & Related papers  (2020-06-15T02:57:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.