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 Mathematics, Modelling, Simulation and Algorithms (MMSA)

A New Relaxation Method for Binary Quadratic Programming: An Application to Densest k-subgraph

Chuan-Hao Guo, Liping Tang

Published Jan 1, 2018• 2 citations
Publisher

Abstract

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.

DOI
10.2991/mmsa-18.2018.70

Related papers

The equivalence between doubly nonnegative relaxation and semidefinite relaxation for binary quadratic programming problems

Chuan-Hao Guo, Yanqin Bai, Tang, Li-Ping

It has recently been shown (Burer, Math. Program Ser. A 120:479-495, 2009) that a large class of NP-hard nonconvex quadratic programming problems can be modeled as so called completely positive programming problems, which are convex but still NP-hard in general. A basic tractable relaxation is gotten by doubly nonnegative relaxation, resulting in a doubly nonnegative programming. In this paper, we prove that doubly nonnegative relaxation for binary quadratic programming (BQP) problem is equivalent to a tighter semidifinite relaxation for it. When problem (BQP) reduces to max-cut (MC) problem, doubly nonnegative relaxation for it is equivalent to the standard semidifinite relaxation. Furthermore, some compared numerical results are reported.

arXiv:1211.5406•Nov 23, 2012•0 citations

Large-Scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications

Peng Wang, Chunhua Shen, Anton van den Hengel +1 more

In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.

arXiv:1411.7564•IEEE Transactions on Pattern Analysis and Machine Intelligence•Mar 11, 2016•59 citations

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

Cover-Relax-Search: A Primal Heuristic for Binary Quadratic Programs

Weimin Huang, Natalie M. Isenberg, Ján Drgoňa +2 more

Binary Quadratic Programs (BQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and logistics. These problems are challenging to solve due to the combinatorial search space and nonlinearity. In fact, this class of optimization problems is so challenging that, in many instances, standard algorithms struggle to identify feasible solutions within a reasonable time. Primal heuristic algorithms have been developed to quickly identify feasible solutions to BQPs. In this paper, we propose Cover-Relax-Search, an efficient primal heuristic for BQPs. This approach is inspired by multiple local search algorithms, including Undercover. We evaluate the \emph{Cover-Relax-Search} algorithm on multiple BQP benchmarks and show that our proposed heuristic identifies high-quality solutions at a faster speed and significantly reduces the primal integral compared to state-of-the-art solvers and other local search baselines.

arXiv:2501.05052•Jan 9, 2025•0 citations

A COMPUTATIONAL STUDY ON THE GLOBAL SOLUTION OF NONCONVEX QUADRATIC CONSTRAINTS AND QUADRATIC PROGRAMMING PROBLEMS

Nirakar Sahoo, Rupaj Kumar Nayak

ABSTRACT Quadratically constrained quadratic programming (QCQP) problems appear in a wide range of engineering fields, including computer science, communication engineering, and finance. A key difficulty in solving these problems lies in efficiently finding global solutions, especially for large-scale and nonconvex instances. To address this, Wen & Yin (2013) proposed a method that reformulates semidefinite programming (SDP) relaxations of QCQPs into a nonlinear and nonconvex low-rank problem. This reformulated problem can be efficiently solved using a curvilinear search method combined with Barzilai-Borwein (BB) steps, known as the CSBB algorithm. In this study, we compare two approaches for solving QCQPs: the conventional convex SDP relaxation and the nonconvex low-rank reformulation introduced by Wen and Yin. We propose a set of general QCQP models that are compatible with the low-rank framework and conduct a series of numerical experiments to evaluate their performance. This study evaluates performance using several classes of NP-hard problems, including Binary Integer Quadratic (BIQ) problems, Max-Cut problems, Boolean Least Squares (BLS) problems, and 0-1 Quadratic Knapsack Problems (QKP). The results demonstrate that the low-rank approach offers competitive performance and shows strong potential for solving large-scale QCQPs more efficiently than traditional convex methods.

Pesquisa Operacional•Jan 1, 2025•0 citations

Convex Quadratic Programming for Exact Solution of 0-1 Quadratic Programs

Alain Billionnet, Sourour Elloumi, Marie-Christine Plateau

Let (QP) be a 0-1 quadratic program which consists in minimizing a quadratic function subject to linear constraints. In this paper, we present a general method to solve (QP) by reformulation of the problem into an equivalent 0-1 program with a convex quadratic objective function, followed by the use of a standard mixed integer quadratic programming solver. Our convexification method, which is the best in a certain sense, uses the equality constraints of (QP) and requires the solution of a semidefinite program. We apply it to the densest k-subgraph problem and report experimental results showing that, for this graph problem, the approach outperforms existing methods.

•Jan 1, 2005•11 citations
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.
It has recently been shown (Burer, Math. Program Ser. A 120:479-495, 2009) that a large class of NP-hard nonconvex quadratic programming problems can be modeled as so called completely positive programming problems, which are convex but still NP-hard in general. A basic tractable relaxation is gotten by doubly nonnegative relaxation, resulting in a doubly nonnegative programming. In this paper, we prove that doubly nonnegative relaxation for binary quadratic programming (BQP) problem is equivalent to a tighter semidifinite relaxation for it. When problem (BQP) reduces to max-cut (MC) problem, doubly nonnegative relaxation for it is equivalent to the standard semidifinite relaxation. Furthermore, some compared numerical results are reported.
In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.
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.
Binary Quadratic Programs (BQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and logistics. These problems are challenging to solve due to the combinatorial search space and nonlinearity. In fact, this class of optimization problems is so challenging that, in many instances, standard algorithms struggle to identify feasible solutions within a reasonable time. Primal heuristic algorithms have been developed to quickly identify feasible solutions to BQPs. In this paper, we propose Cover-Relax-Search, an efficient primal heuristic for BQPs. This approach is inspired by multiple local search algorithms, including Undercover. We evaluate the \emph{Cover-Relax-Search} algorithm on multiple BQP benchmarks and show that our proposed heuristic identifies high-quality solutions at a faster speed and significantly reduces the primal integral compared to state-of-the-art solvers and other local search baselines.
ABSTRACT Quadratically constrained quadratic programming (QCQP) problems appear in a wide range of engineering fields, including computer science, communication engineering, and finance. A key difficulty in solving these problems lies in efficiently finding global solutions, especially for large-scale and nonconvex instances. To address this, Wen & Yin (2013) proposed a method that reformulates semidefinite programming (SDP) relaxations of QCQPs into a nonlinear and nonconvex low-rank problem. This reformulated problem can be efficiently solved using a curvilinear search method combined with Barzilai-Borwein (BB) steps, known as the CSBB algorithm. In this study, we compare two approaches for solving QCQPs: the conventional convex SDP relaxation and the nonconvex low-rank reformulation introduced by Wen and Yin. We propose a set of general QCQP models that are compatible with the low-rank framework and conduct a series of numerical experiments to evaluate their performance. This study evaluates performance using several classes of NP-hard problems, including Binary Integer Quadratic (BIQ) problems, Max-Cut problems, Boolean Least Squares (BLS) problems, and 0-1 Quadratic Knapsack Problems (QKP). The results demonstrate that the low-rank approach offers competitive performance and shows strong potential for solving large-scale QCQPs more efficiently than traditional convex methods.
Let (QP) be a 0-1 quadratic program which consists in minimizing a quadratic function subject to linear constraints. In this paper, we present a general method to solve (QP) by reformulation of the problem into an equivalent 0-1 program with a convex quadratic objective function, followed by the use of a standard mixed integer quadratic programming solver. Our convexification method, which is the best in a certain sense, uses the equality constraints of (QP) and requires the solution of a semidefinite program. We apply it to the densest k-subgraph problem and report experimental results showing that, for this graph problem, the approach outperforms existing methods.