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

International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA)

Sufficient optimal conditions for unconstrained quadratic binary problems

Liu Liu, Qiuling Xie, Chunli Liu

Published Jan 1, 2015• 0 citations
Publisher

Abstract

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.
DOI
10.1049/cp.2015.0623

Related papers

Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming

Xiaojin Zheng, Xiaoling Sun, Duan Li +1 more

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.

Mathematics of Operations Research•Nov 1, 2010•11 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 preprocessing technique for quadratic unconstrained binary optimization

Serigne Guèye, Philippe Yves Paul Michelon

To solve combinatorial optimization problems more easily, it can be valuable to identify a set of necessary or sufficient conditions that an optimal solution of the problem must satisfy. For instance, weak and strong duality conditions in linear programming support the development of the well-known optimization algorithms for these problems. Similarly, the Karush–Kuhn–Tucker conditions give necessary and sufficient conditions for optimality in convex quadratic programming that underlie the development of optimization algorithms in this domain. Although such continuous conditions do not exist for integer programming, some necessary conditions can be derived from Karush–Kuhn–Tucker conditions for the Quadratic Unconstrained Binary Optimization (QUBO) problem. We present these conditions and show how they lead to a derivation of well-known criteria for fixing the values of single variables in the QUBO problem. From this, we show how to generalize these criteria to fix a product of any number of p (integer) literals, which also may be viewed as a generalization of the persistency notion, consisting of clauses of a Constraint Satisfaction Problem that the optimal solution must satisfy. We then couple our list of persistencies with state-of-the-art rules not covered by our approach. The resulting integrated set of conditions for fixing values of variables is tested in computational experiments on instances from standard databases available in the literature, showing that we can fix more variables and reduce problems more fully than previous approaches.

Discrete Optimization•Oct 25, 2025•2 citations

Lagrangean decompositions for the unconstrained binary quadratic programming problem

Geraldo Regis Mauri, Luiz Antônio Nogueira Lorena

The unconstrained binary quadratic programming problem (QP) is a classical non-linear problem of optimizing a quadratic objective by a suitable choice of binary decision variables. This paper proposes new Lagrangean decompositions to find bounds for QP. The methods presented treat a mixed binary linear version (LQP) of QP with constraints represented by a graph. This graph is partitioned into clusters of vertices forming a dual problem that is solved by a subgradient algorithm. The subproblems formed by the generated subgraphs are solved by CPLEX. Computational experiments consider a data set formed by several difficult instances with different features. The results show the efficiency of the proposed methods over traditional Lagrangean relaxations and other methods found in the literature.

International Transactions in Operational Research•Dec 4, 2009•11 citations

Heuristic algorithms for the unconstrained binary quadratic programming problem

J. E. Beasley

In this paper we consider the unconstrained binary quadratic programming problem. This is the problem of maximising a quadratic objective by suitable choice of binary (zero-one) variables. We present two heuristic algorithms based upon tabu search and simulated annealing for this problem. Computational results are presented for a number of publically available data sets involving up to 2500 variables. An interesting feature of our results is that whilst for most problems tabu search dominates simulated annealing for the very largest problems we consider the converse is true. This paper typifies a "multiple solution technique, single paper" approach, i.e. an approach that within the same paper presents results for a number of different heuristics applied to the same problem. Issues relating to algorithmic design for such papers are discussed. Keywords: unconstrained binary (zero-one) quadratic programming

•Jan 1, 1998•151 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•7 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.
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.
To solve combinatorial optimization problems more easily, it can be valuable to identify a set of necessary or sufficient conditions that an optimal solution of the problem must satisfy. For instance, weak and strong duality conditions in linear programming support the development of the well-known optimization algorithms for these problems. Similarly, the Karush–Kuhn–Tucker conditions give necessary and sufficient conditions for optimality in convex quadratic programming that underlie the development of optimization algorithms in this domain. Although such continuous conditions do not exist for integer programming, some necessary conditions can be derived from Karush–Kuhn–Tucker conditions for the Quadratic Unconstrained Binary Optimization (QUBO) problem. We present these conditions and show how they lead to a derivation of well-known criteria for fixing the values of single variables in the QUBO problem. From this, we show how to generalize these criteria to fix a product of any number of p (integer) literals, which also may be viewed as a generalization of the persistency notion, consisting of clauses of a Constraint Satisfaction Problem that the optimal solution must satisfy. We then couple our list of persistencies with state-of-the-art rules not covered by our approach. The resulting integrated set of conditions for fixing values of variables is tested in computational experiments on instances from standard databases available in the literature, showing that we can fix more variables and reduce problems more fully than previous approaches.
The unconstrained binary quadratic programming problem (QP) is a classical non-linear problem of optimizing a quadratic objective by a suitable choice of binary decision variables. This paper proposes new Lagrangean decompositions to find bounds for QP. The methods presented treat a mixed binary linear version (LQP) of QP with constraints represented by a graph. This graph is partitioned into clusters of vertices forming a dual problem that is solved by a subgradient algorithm. The subproblems formed by the generated subgraphs are solved by CPLEX. Computational experiments consider a data set formed by several difficult instances with different features. The results show the efficiency of the proposed methods over traditional Lagrangean relaxations and other methods found in the literature.
In this paper we consider the unconstrained binary quadratic programming problem. This is the problem of maximising a quadratic objective by suitable choice of binary (zero-one) variables. We present two heuristic algorithms based upon tabu search and simulated annealing for this problem. Computational results are presented for a number of publically available data sets involving up to 2500 variables. An interesting feature of our results is that whilst for most problems tabu search dominates simulated annealing for the very largest problems we consider the converse is true. This paper typifies a "multiple solution technique, single paper" approach, i.e. an approach that within the same paper presents results for a number of different heuristics applied to the same problem. Issues relating to algorithmic design for such papers are discussed. Keywords: unconstrained binary (zero-one) quadratic programming
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.