Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

A Direct SDP Approach for Constrained Quadratic Binary Optimization Problems

MilaNedic, Zvmcevap

Published Aug 25, 2026• 0 citations
OpenAlex

Abstract

This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.

Related papers

Beyond binarity: Semidefinite programming for ternary quadratic problems

Frank de Meijer, Veronica Piccialli, Renata Sotirov +1 more

We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in $\{0, \pm 1\}$. While semidefinite programming (SDP) techniques are well established for $\{0,1\}$- and $\{\pm 1\}$-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation for the TQP that forms the basis of an exact solution approach. We derive new theoretical insights in rank-one ternary positive semidefinite matrices, which lead to a basic SDP relaxation that is further strengthened by valid triangle, RLT, split and $k$-gonal inequalities. These are embedded in a tailored branch-and-bound algorithm that iteratively solves strengthened SDPs, separates violated inequalities, applies a ternary branching strategy and computes high-quality feasible solutions. We test our algorithm on TQP variations motivated by practice, including unconstrained, linearly constrained and quadratic ratio problems. Computational results on these instances demonstrate the effectiveness of the proposed algorithm.

arXiv:2603.28979•Mar 30, 2026•0 citations

On Integrality in Semidefinite Programming for Discrete Optimization

Frank de Meijer, Renata Sotirov

Abstract. It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we introduce a generic approach to derive mixed-integer SDP (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadratic matrix programs. Applying a problem-specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem, and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems.

arXiv:2306.09865•SIAM Journal on Optimization•Mar 15, 2024•3 citations

Faster quantum and classical SDP approximations for quadratic binary optimization

Fernando G. S. L. Brandão, Richard Kueng, Daniel Stilck França

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.

arXiv:1909.04613•Quantum•Jan 20, 2022•28 citations

Quadratic Combinatorial Optimization Using Separable Underestimators

Christoph Buchheim, Emiliano Traversi

Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branch-and-bound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems to obtain a tailored coordinate-descent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both CPLEX and the related QCR method as well as the SDP-based software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem.

INFORMS journal on computing•Aug 1, 2018•17 citations

BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints

Nicolò Gusmeroli, Timotej Hrga, Borut Lužar +3 more

We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original problem into an instance of Max-Cut, and then to solve the Max-Cut problem by a branch-and-bound algorithm. All the main ingredients are carefully developed using new semidefinite programming relaxations obtained by strengthening the existing relaxations with a set of hypermetric inequalities, applying the bundle method as the bounding routine and using new strategies for exploring the branch-and-bound tree. Furthermore, an efficient C implementation of a sequential and a parallel branch-and-bound algorithm is presented. The latter is based on a load coordinator-worker scheme using MPI for multi-node parallelization and is evaluated on a high-performance computer. The new solver is benchmarked against BiqCrunch, GUROBI, and SCIP on four families of (linearly constrained) binary quadratic problems. Numerical results demonstrate that BiqBin is a highly competitive solver. The serial version outperforms the other three solvers on the majority of the benchmark instances. We also evaluate the parallel solver and show that it has good scaling properties. The general audience can use it as an on-line service available at http://www.biqbin.eu .

arXiv:2009.06240•ACM Transactions on Mathematical Software•Jun 30, 2022•19 citations

QUBO Dual Bounds via SDP Plane Projection Method

Apostolos Chalkis, Thomas Kleinert, Boro Sofranac

In this paper, we present a new method to solve a certain type of Semidefinite Programming (SDP) problems. These types of SDPs naturally arise in the Quadratic Convex Reformulation (QCR) method and can be used to obtain dual bounds of Quadratic Unconstrained Binary Optimization (QUBO) problems. QUBO problems have recently become the focus of attention in the quantum computing and optimization communities as they are well suited to both gate-based and annealing-based quantum computers on one side, and can encompass an exceptional variety of combinatorial optimization problems on the other. Our new method can be easily warm-started, making it very effective when embedded into a branch-and-bound scheme and used to solve the QUBO problem to global optimality. We test our method in this setting and present computational results showing the effectiveness of our approach.

arXiv:2312.15026•Dec 22, 2023•1 citation
This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.
We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}\{0, \pm 1\}{0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}\{0,1\}{0,1}- and {±1}\{\pm 1\}{±1}-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation for the TQP that forms the basis of an exact solution approach. We derive new theoretical insights in rank-one ternary positive semidefinite matrices, which lead to a basic SDP relaxation that is further strengthened by valid triangle, RLT, split and kkk-gonal inequalities. These are embedded in a tailored branch-and-bound algorithm that iteratively solves strengthened SDPs, separates violated inequalities, applies a ternary branching strategy and computes high-quality feasible solutions. We test our algorithm on TQP variations motivated by practice, including unconstrained, linearly constrained and quadratic ratio problems. Computational results on these instances demonstrate the effectiveness of the proposed algorithm.
Abstract. It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we introduce a generic approach to derive mixed-integer SDP (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadratic matrix programs. Applying a problem-specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem, and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems.
We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.
Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branch-and-bound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems to obtain a tailored coordinate-descent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both CPLEX and the related QCR method as well as the SDP-based software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem.
We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original problem into an instance of Max-Cut, and then to solve the Max-Cut problem by a branch-and-bound algorithm. All the main ingredients are carefully developed using new semidefinite programming relaxations obtained by strengthening the existing relaxations with a set of hypermetric inequalities, applying the bundle method as the bounding routine and using new strategies for exploring the branch-and-bound tree. Furthermore, an efficient C implementation of a sequential and a parallel branch-and-bound algorithm is presented. The latter is based on a load coordinator-worker scheme using MPI for multi-node parallelization and is evaluated on a high-performance computer. The new solver is benchmarked against BiqCrunch, GUROBI, and SCIP on four families of (linearly constrained) binary quadratic problems. Numerical results demonstrate that BiqBin is a highly competitive solver. The serial version outperforms the other three solvers on the majority of the benchmark instances. We also evaluate the parallel solver and show that it has good scaling properties. The general audience can use it as an on-line service available at http://www.biqbin.eu .
In this paper, we present a new method to solve a certain type of Semidefinite Programming (SDP) problems. These types of SDPs naturally arise in the Quadratic Convex Reformulation (QCR) method and can be used to obtain dual bounds of Quadratic Unconstrained Binary Optimization (QUBO) problems. QUBO problems have recently become the focus of attention in the quantum computing and optimization communities as they are well suited to both gate-based and annealing-based quantum computers on one side, and can encompass an exceptional variety of combinatorial optimization problems on the other. Our new method can be easily warm-started, making it very effective when embedded into a branch-and-bound scheme and used to solve the QUBO problem to global optimality. We test our method in this setting and present computational results showing the effectiveness of our approach.