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

arXiv:2005.07030

A Polynomial-Time Algorithm for Unconstrained Binary Quadratic Optimization

Juan Ignacio Mulero-Martínez

Published May 13, 2020• 1 citation
arXivHTMLPDF

Abstract

In this paper, an exact algorithm in polynomial time is developed to solve unrestricted binary quadratic programs. The computational complexity is $O\left( n^{\frac{15}{2}}\right) $, although very conservative, it is sufficient to prove that this minimization problem is in the complexity class $P$. The implementation aspects are also described in detail with a special emphasis on the transformation of the quadratic program into a linear program that can be solved in polynomial time. The algorithm was implemented in MATLAB and checked by generating five million matrices of arbitrary dimensions up to 30 with random entries in the range $\left[ -50,50\right] $. All the experiments carried out have revealed that the method works correctly.

DOI
10.48550/arxiv.2005.07030

Related papers

Polynomial time solvable algorithms to binary quadratic programming problems with Q being a tri-diagonal or five-diagonal matrix

Shenshen Gu

In the field of signal processing, many problems can be formulated as optimization problems. And most of these optimization problem can be further described in a formal form, that is binary quadratic programming problem(BQP). However, solving the BQP is proved to be NP-hard. Due to this reason, many novel algorithms have been proposed in order to improve the efficiency to solve the BQP. In this paper, polynomial algorithms to binary quadratic programming problems with Q being a tri-diagonal or five-diagonal matrix is focused by taking advantage of the basic algorithm proposed in. The basic algorithm is firstly reviewed and then this algorithm is modified to solve binary quadratic programming problems with Q being a tri-diagonal. Furthermore, by improving this algorithm, an algorithm is proposed to solve binary quadratic programming problems with Q being a five-diagonal matrix.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 1, 2010•4 citations

Polynomial unconstrained binary optimisation â part 2

Fred Glover, Jin‐Kao Hao, Gary A. Kochenberger

The class of problems known as quadratic zero-one (binary) unconstrained optimization has provided access to a vast array of combinatorial optimization problems, allowing them to be expressed within the setting of a single unifying model. A gap exists, however, in addressing polynomial problems of degree greater than 2. to bridge this gap, we provide methods for efficiently executing core search processes for the general polynomial unconstrained binary (PUB) optimization problem. A variety of search algorithms for quadratic optimization can take advantage of our methods to be transformed directly into algorithms for problems where the objective functions involve arbitrary polynomials. Part 1 of this paper (Glover, Hao and Kochenberger, 2010) provided fundamental results for carrying out the transformations and described coding and decoding procedures relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In the present Part 2 paper, we provide special algorithms and data structures for taking advantage of the basic results of Part 1. We also disclose how our designs can be used to enhance existing quadratic optimization algorithms.

International Journal of Metaheuristics•Jan 1, 2011•12 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

Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners

Richard J. Forrester, Noah Hunt-Isaak

This paper is concerned with binary quadratic programs (BQPs), which are among the most well-studied classes of nonlinear integer optimization problems because of their wide variety of applications. While a number of different solution approaches have been proposed for tackling BQPs, practitioners need techniques that are both efficient and easy to implement. We revisit two of the most widely used linearization strategies for BQPs and examine the effectiveness of enhancements to these formulations that have been suggested in the literature. We perform a detailed large-scale computational study over five different classes of BQPs to compare these two linearizations with a more recent linear reformulation and direct submission of the nonlinear integer program to an optimization solver. The goal is to provide practitioners with guidance on how to best approach solving BQPs in an effective and easily implemented manner.

Journal of Applied Mathematics•Apr 27, 2020•11 citations

A Polynomial-Time Recursive Algorithm for some Unconstrained Quadratic Optimization Problems.

Walid Ben‐Ameur, José Neto

Consider a quadratic function q : Rn -> R given by: q(x) = xtQx, with Q E Rn×n. An unconstrained (−1, 1)-quadratic optimization problem can be expressed as follows: (QP) Z* = min{q(x) | x E {−1, 1}*}, where {−1, 1}n denotes the set of n-dimensional vectors with entries either equal to 1 or −1.We consider here that the matrix Q is symmetric and given by its spectrum, i.e. the set of its eigenvalues and associated unit pairwise orthogonal eigenvectors. Problem (QP) is a classical combinatorial optimization problem with many applications, e.g. in statistical physics and circuit design [2; 8; 10]. It is well-known that any (0,1)-quadratic problem expressed as: min{xt Ax + ctx | x E {0, 1}n}, A E Rn×n, c E Rn, can be formulated in the form of problem (QP) and conversely [9; 4]. The contribution of this work is 3-fold: (i) We slightly extend the known polynomially solvable cases of (QP) to when the matrix Q has fixed rank and the number of positive diagonal entries is O(log(n)). (ii) We introduce a new (to our knowledge) polynomial-time algorithmfor solving problem (QP) when it corresponds to such a polynomially solvable case. (iii) Preliminary experiments indicate that the proposed method may be computationally efficient

Cologne Twente Workshop on Graphs and Combinatorial Optimization•Jan 1, 2009•0 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•19 citations
In this paper, an exact algorithm in polynomial time is developed to solve unrestricted binary quadratic programs. The computational complexity is O(n152)O\left( n^{\frac{15}{2}}\right) O(n215​), although very conservative, it is sufficient to prove that this minimization problem is in the complexity class PPP. The implementation aspects are also described in detail with a special emphasis on the transformation of the quadratic program into a linear program that can be solved in polynomial time. The algorithm was implemented in MATLAB and checked by generating five million matrices of arbitrary dimensions up to 30 with random entries in the range [−50,50]\left[ -50,50\right] [−50,50]. All the experiments carried out have revealed that the method works correctly.
In the field of signal processing, many problems can be formulated as optimization problems. And most of these optimization problem can be further described in a formal form, that is binary quadratic programming problem(BQP). However, solving the BQP is proved to be NP-hard. Due to this reason, many novel algorithms have been proposed in order to improve the efficiency to solve the BQP. In this paper, polynomial algorithms to binary quadratic programming problems with Q being a tri-diagonal or five-diagonal matrix is focused by taking advantage of the basic algorithm proposed in. The basic algorithm is firstly reviewed and then this algorithm is modified to solve binary quadratic programming problems with Q being a tri-diagonal. Furthermore, by improving this algorithm, an algorithm is proposed to solve binary quadratic programming problems with Q being a five-diagonal matrix.
The class of problems known as quadratic zero-one (binary) unconstrained optimization has provided access to a vast array of combinatorial optimization problems, allowing them to be expressed within the setting of a single unifying model. A gap exists, however, in addressing polynomial problems of degree greater than 2. to bridge this gap, we provide methods for efficiently executing core search processes for the general polynomial unconstrained binary (PUB) optimization problem. A variety of search algorithms for quadratic optimization can take advantage of our methods to be transformed directly into algorithms for problems where the objective functions involve arbitrary polynomials. Part 1 of this paper (Glover, Hao and Kochenberger, 2010) provided fundamental results for carrying out the transformations and described coding and decoding procedures relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In the present Part 2 paper, we provide special algorithms and data structures for taking advantage of the basic results of Part 1. We also disclose how our designs can be used to enhance existing quadratic optimization algorithms.
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.
This paper is concerned with binary quadratic programs (BQPs), which are among the most well-studied classes of nonlinear integer optimization problems because of their wide variety of applications. While a number of different solution approaches have been proposed for tackling BQPs, practitioners need techniques that are both efficient and easy to implement. We revisit two of the most widely used linearization strategies for BQPs and examine the effectiveness of enhancements to these formulations that have been suggested in the literature. We perform a detailed large-scale computational study over five different classes of BQPs to compare these two linearizations with a more recent linear reformulation and direct submission of the nonlinear integer program to an optimization solver. The goal is to provide practitioners with guidance on how to best approach solving BQPs in an effective and easily implemented manner.
Consider a quadratic function q : Rn -> R given by: q(x) = xtQx, with Q E Rn×n. An unconstrained (−1, 1)-quadratic optimization problem can be expressed as follows: (QP) Z* = min{q(x) | x E {−1, 1}*}, where {−1, 1}n denotes the set of n-dimensional vectors with entries either equal to 1 or −1.We consider here that the matrix Q is symmetric and given by its spectrum, i.e. the set of its eigenvalues and associated unit pairwise orthogonal eigenvectors. Problem (QP) is a classical combinatorial optimization problem with many applications, e.g. in statistical physics and circuit design [2; 8; 10]. It is well-known that any (0,1)-quadratic problem expressed as: min{xt Ax + ctx | x E {0, 1}n}, A E Rn×n, c E Rn, can be formulated in the form of problem (QP) and conversely [9; 4]. The contribution of this work is 3-fold: (i) We slightly extend the known polynomially solvable cases of (QP) to when the matrix Q has fixed rank and the number of positive diagonal entries is O(log(n)). (ii) We introduce a new (to our knowledge) polynomial-time algorithmfor solving problem (QP) when it corresponds to such a polynomially solvable case. (iii) Preliminary experiments indicate that the proposed method may be computationally efficient
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.