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

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

Alain Billionnet, Sourour Elloumi, Marie-Christine Plateau

Published Jan 1, 2005• 11 citations
OpenAlex

Abstract

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.

Related papers

Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations

Alain Billionnet, Sourour Elloumi, Marie-Christine Plateau

Many combinatorial optimization problems can be formulated as the minimization of a 0–1 quadratic function subject to linear constraints. In this paper, we are interested in the exact solution of this problem through a two-phase general scheme. The first phase consists in reformulating the initial problem either into a compact mixed integer linear program or into a 0–1 quadratic convex program. The second phase simply consists in submitting the reformulated problem to a standard solver. The efficiency of this scheme strongly depends on the quality of the reformulation obtained in phase 1. We show that a good compact linear reformulation can be obtained by solving a continuous linear relaxation of the initial problem. We also show that a good quadratic convex reformulation can be obtained by solving a semidefinite relaxation. In both cases, the obtained reformulation profits from the quality of the underlying relaxation. Hence, the proposed scheme gets around, in a sense, the difficulty to incorporate these costly relaxations in a branch-and-bound algorithm.

RAIRO - Operations Research•Apr 1, 2008•24 citations

Quadratic Convex Reformulation : a Computational Study of the Graph Bisection Problem

Alain Billionnet, Sourour Elloumi, Marie-Christine Plateau

Given an undirected graph G = (V, E), we consider the graph bisection problem, which consists in partitioning the nodes of G in two disjoined sets with p and n − p nodes respectively such that the total weight of edges crossing between subsets is minimal. We apply QCR to it, a general method, presented in [4], which combines semidefinite programming (SDP) and Mixed Integer Quadratic Programming (MIQP). This method solves exactly general 0-1 quadratic programs (called (QP)) with linear constraints. It is composed of two phases: Phase I is devoted to reformulate (QP) into a new problem, equivalent to (QP), with a convex quadratic function; Phase II consists in submitting this new problem to a mixed-integer convex quadratic solver. Computational results reported in this paper show that the present approach is competitive with state-of-the-art methods for the graph bisection problem.

•Jan 1, 2006•9 citations

A unified view of linear and quadratic convex reformulations for binary quadratic programming

Sourour Elloumi

We consider binary quadratic programs (QP) having a quadratic objectivefunction, linear constraints, and binary variables. Many classical solution methods ofthese problems are based on exact reformulation of QP into anequivalent mixed integer linear program. Several linearization methods werestudied in the literature. More recent solution methods alsobuild an exact reformulation but into a problem which objective function isquadratic and convex. A common point of the two approaches is that thecontinuous relaxation of the reformulated problem is a convex optimizationproblem that can be solved in polynomial time. This makes it possible to use a general branch-and-bound framework to solve the reformulated problem and even to rely on the strongness of standard solvers. In this paper, we show that several quadratic convex reformulation methods, as well as classical linearization, can be viewed within a unified framework. This shows the non-surprising result that linearization is a particular quadratic convex reformulation on the one hand. On the other hand, it allows to compare these methods from a theoretical point of view.

•Aug 20, 2012•0 citations

Quadratic Convex Reformulation for discrete quadratic optimization : Basic results and recent extensions

Sourour Elloumi

We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are integer and bounded. This very general problem can model many classical problems in Combinatorial Optimization.A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP'), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP') by an implicit enumeration algorithm based on continuous convex optimization.We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP'). In the case of binary variables, we give a vision of classical linearization as a special case of Convex Quadratic Reformulation.Finally, we illustrate the generality and the computational efficiency of the Quadratic Convex Reformulation approach for several combinatorial optimization problems.

•Oct 28, 2014•0 citations

Convex reformulations for binary quadratic programs

Alain Billionnet, Sourour Elloumi, Amélie Lambert

-Let (QP) be a binary quadratic program that consists in minimizing a quadratic function subject to linear constraints. To solve (QP) we reformulate it into an equivalent program with a convex objective function. Our reformulation, that we call EQCR (Extended Quadratic Convex Reformulation), is optimal from the continuous relaxation bound point of view. We show that this best reformulation can be deduced from the solution of a semidefinite relaxation of (QP) and that EQCR outperforms QCR. We carry out computational experiments on Max-Cut and on the k-cluster problem.

•Jul 1, 2009•0 citations

Global solution of non-convex quadratically constrained quadratic programs

Sourour Elloumi, Amélie Lambert

The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.

Optimization methods & software•Jul 28, 2017•26 citations
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.
Many combinatorial optimization problems can be formulated as the minimization of a 0–1 quadratic function subject to linear constraints. In this paper, we are interested in the exact solution of this problem through a two-phase general scheme. The first phase consists in reformulating the initial problem either into a compact mixed integer linear program or into a 0–1 quadratic convex program. The second phase simply consists in submitting the reformulated problem to a standard solver. The efficiency of this scheme strongly depends on the quality of the reformulation obtained in phase 1. We show that a good compact linear reformulation can be obtained by solving a continuous linear relaxation of the initial problem. We also show that a good quadratic convex reformulation can be obtained by solving a semidefinite relaxation. In both cases, the obtained reformulation profits from the quality of the underlying relaxation. Hence, the proposed scheme gets around, in a sense, the difficulty to incorporate these costly relaxations in a branch-and-bound algorithm.
Given an undirected graph G = (V, E), we consider the graph bisection problem, which consists in partitioning the nodes of G in two disjoined sets with p and n − p nodes respectively such that the total weight of edges crossing between subsets is minimal. We apply QCR to it, a general method, presented in [4], which combines semidefinite programming (SDP) and Mixed Integer Quadratic Programming (MIQP). This method solves exactly general 0-1 quadratic programs (called (QP)) with linear constraints. It is composed of two phases: Phase I is devoted to reformulate (QP) into a new problem, equivalent to (QP), with a convex quadratic function; Phase II consists in submitting this new problem to a mixed-integer convex quadratic solver. Computational results reported in this paper show that the present approach is competitive with state-of-the-art methods for the graph bisection problem.
We consider binary quadratic programs (QP) having a quadratic objectivefunction, linear constraints, and binary variables. Many classical solution methods ofthese problems are based on exact reformulation of QP into anequivalent mixed integer linear program. Several linearization methods werestudied in the literature. More recent solution methods alsobuild an exact reformulation but into a problem which objective function isquadratic and convex. A common point of the two approaches is that thecontinuous relaxation of the reformulated problem is a convex optimizationproblem that can be solved in polynomial time. This makes it possible to use a general branch-and-bound framework to solve the reformulated problem and even to rely on the strongness of standard solvers. In this paper, we show that several quadratic convex reformulation methods, as well as classical linearization, can be viewed within a unified framework. This shows the non-surprising result that linearization is a particular quadratic convex reformulation on the one hand. On the other hand, it allows to compare these methods from a theoretical point of view.
We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are integer and bounded. This very general problem can model many classical problems in Combinatorial Optimization.A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP'), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP') by an implicit enumeration algorithm based on continuous convex optimization.We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP'). In the case of binary variables, we give a vision of classical linearization as a special case of Convex Quadratic Reformulation.Finally, we illustrate the generality and the computational efficiency of the Quadratic Convex Reformulation approach for several combinatorial optimization problems.
-Let (QP) be a binary quadratic program that consists in minimizing a quadratic function subject to linear constraints. To solve (QP) we reformulate it into an equivalent program with a convex objective function. Our reformulation, that we call EQCR (Extended Quadratic Convex Reformulation), is optimal from the continuous relaxation bound point of view. We show that this best reformulation can be deduced from the solution of a semidefinite relaxation of (QP) and that EQCR outperforms QCR. We carry out computational experiments on Max-Cut and on the k-cluster problem.
The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.