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

Mathematics of Operations Research

Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming

Xiaojin Zheng, Xiaoling Sun, Duan Li, Yong Xia

Published Nov 1, 2010• 11 citations
Publisher

Abstract

We investigate in this paper the Lagrangian duality properties of linear equality constrained binary quadratic programming. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP relaxation, using the distance from the set of binary integer points to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the squared norm constraint reformulations are also discussed.

DOI
10.1287/moor.1100.0472

Related papers

Sufficient optimal conditions for unconstrained quadratic binary problems

Liu Liu, Qiuling Xie, Chunli Liu

In this article, we present several sufficient optimal conditions for unconstrained quadratic binary problems, which can be applied in algorithms combining with SDP relaxations in branch-and-bound approaches for the primal problem. These optimal conditions can work for many situations when the Lagrangian duality gap is not zero.

International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA)•Jan 1, 2015•0 citations

A Direct SDP Approach for Constrained Quadratic Binary Optimization Problems

MilaNedic, Zvmcevap

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.

•Aug 25, 2026•0 citations

Solving constrained quadratic binary problems via quantum adiabatic evolution

Pooya Ronagh, Brad Woods, Ehsan Iranmanesh

Quantum adiabatic evolution is perceived as useful for binary quadratic programming problems that are a priori unconstrained. For constrained problems, it is a common practice to relax linear equality constraints as penalty terms in the objective function. However, there has not yet been proposed a method for efficiently dealing with inequality constraints using the quantum adiabatic approach. In this paper, we give a method for solving the Lagrangian dual of a binary quadratic programming (BQP) problem in the presence of inequality constraints and employ this procedure within a branch-and-bound framework for constrained BQP (CBQP) problems.

arXiv:1509.05001•Quantum Information and Computation•Sep 1, 2016•9 citations

Improved SDP Bounds for Binary Quadratic Programming

Baiyi Wu

As a classical combinatorial problem, the binary quadratic programming problem has many applications in finance, statistics, production management, etc. The state-of-the-art solution for solving this problem accurately is based on branch-and-bound frameworks, with the low bound support of a semi-definite programming (SDP) relaxation. This paper generalizes the spectral bounds in the literature and proposes a sequence of improved SDP bounds for the binary quadratic programming problem. Our method relies on the closest binary points to an affine space, which can be found by reverse enumeration technique.

RA Journal Of Applied Research•Jun 27, 2018•0 citations

A benchmark generator for boolean quadratic programming

Xiaojun Zhou, Tingwen Huang

For boolean quadratic programming (BQP), we will show that there is no duality gap between the primal and dual problems under some conditions by using the classical Lagrangian duality. A benchmark generator is given to create random BQP problems which can be solved in polynomial time. Several numerical examples are generated to demonstrate the effectiveness of the proposed method.

arXiv:1406.4812•Chinese Automation Congress•Nov 6, 2020•4 citations

New methods for handling binary constraints

Abhay Yadav, Rajeev Ranjan, Upal Mahbub +1 more

We consider the problem of handling binary constraints in optimization problems. We review methods for solving binary quadratic programs (BQPs), such as the spectral method and semidefinite programming relaxations. We then discuss two new methods for handling these constraints. The first involves the introduction of an extra unconstrained variable along with the alternating direction method of multipliers (ADMM), which has now also appeared in other recent literature. This allows the effect of the binary variables to be decoupled when they are minimized over. The second involves rewarding the one-norm while restricting the infinity-norm, based on a reformulation of the original problem. The piecewise linearity of the negative penalty results in the problem being convex until it hits a critical point, at which point the parameters of this linear term can be changed. These two methods can be applied to any problems which are convex except for binary constraints. In addition to testing them on BQPs, we show the efficacy of these approaches on point segmentation and image segmentation problems.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2016•12 citations
We investigate in this paper the Lagrangian duality properties of linear equality constrained binary quadratic programming. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP relaxation, using the distance from the set of binary integer points to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the squared norm constraint reformulations are also discussed.
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.
Quantum adiabatic evolution is perceived as useful for binary quadratic programming problems that are a priori unconstrained. For constrained problems, it is a common practice to relax linear equality constraints as penalty terms in the objective function. However, there has not yet been proposed a method for efficiently dealing with inequality constraints using the quantum adiabatic approach. In this paper, we give a method for solving the Lagrangian dual of a binary quadratic programming (BQP) problem in the presence of inequality constraints and employ this procedure within a branch-and-bound framework for constrained BQP (CBQP) problems.
As a classical combinatorial problem, the binary quadratic programming problem has many applications in finance, statistics, production management, etc. The state-of-the-art solution for solving this problem accurately is based on branch-and-bound frameworks, with the low bound support of a semi-definite programming (SDP) relaxation. This paper generalizes the spectral bounds in the literature and proposes a sequence of improved SDP bounds for the binary quadratic programming problem. Our method relies on the closest binary points to an affine space, which can be found by reverse enumeration technique.
We consider the problem of handling binary constraints in optimization problems. We review methods for solving binary quadratic programs (BQPs), such as the spectral method and semidefinite programming relaxations. We then discuss two new methods for handling these constraints. The first involves the introduction of an extra unconstrained variable along with the alternating direction method of multipliers (ADMM), which has now also appeared in other recent literature. This allows the effect of the binary variables to be decoupled when they are minimized over. The second involves rewarding the one-norm while restricting the infinity-norm, based on a reformulation of the original problem. The piecewise linearity of the negative penalty results in the problem being convex until it hits a critical point, at which point the parameters of this linear term can be changed. These two methods can be applied to any problems which are convex except for binary constraints. In addition to testing them on BQPs, we show the efficacy of these approaches on point segmentation and image segmentation problems.