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 Conference on Wireless Communications and Signal Processing (WCSP)

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

Shenshen Gu

Published Oct 1, 2010• 4 citations
Publisher

Abstract

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.

DOI
10.1109/wcsp.2010.5632199

Related papers

New approximation methods for solving binary quadratic programming problem

Rui Yang

In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\epsilon) approximation ratio to the reformulated clustering problem.

•Jun 22, 2010•2 citations

A Polynomial-Time Algorithm for Unconstrained Binary Quadratic Optimization

Juan Ignacio Mulero-Martínez

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.

arXiv:2005.07030•May 13, 2020•1 citation

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

A Polynomial Time Solvable Algorithm to Binary Quadratic Programming Problems with Q Being a Seven-Diagonal Matrix and Its Neural Network Implementation

Shenshen Gu, Peng Jiao, Rui Cui

Lecture notes in computer science•Jan 1, 2014•2 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 New Relaxation Method for Binary Quadratic Programming: An Application to Densest k-subgraph

Chuan-Hao Guo, Liping Tang

Binary quadratic programming (BQP) problem was an NP-hard problem and had a large number of applications.In this paper, a new relaxation method, that was doubly nonnegative relaxation, was proposed for solving BQP problem.Moreover, we prove that the doubly nonnegative relaxation for BQP is equivalent to a new tighter semidifinite relaxation.When BQP problem reduces to densest k-subgraph problem, the doubly nonnegative relaxation is equivalent to a tighter semidifinite relaxation.Finally, some comparative numerical results are reported to show that the efficiency of the doubly nonnegative relaxation is more promising than that of semidefinite relaxation for solving some specific BQP problems.

International Conference on Mathematics, Modelling, Simulation and Algorithms (MMSA)•Jan 1, 2018•2 citations
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.
In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\epsilon) approximation ratio to the reformulated clustering problem.
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 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 $\left[ -50,50\right] $. All the experiments carried out have revealed that the method works correctly.
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
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.
Binary quadratic programming (BQP) problem was an NP-hard problem and had a large number of applications.In this paper, a new relaxation method, that was doubly nonnegative relaxation, was proposed for solving BQP problem.Moreover, we prove that the doubly nonnegative relaxation for BQP is equivalent to a new tighter semidifinite relaxation.When BQP problem reduces to densest k-subgraph problem, the doubly nonnegative relaxation is equivalent to a tighter semidifinite relaxation.Finally, some comparative numerical results are reported to show that the efficiency of the doubly nonnegative relaxation is more promising than that of semidefinite relaxation for solving some specific BQP problems.