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

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

Sourour Elloumi

Published Oct 28, 2014• 0 citations
OpenAlex

Abstract

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.

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

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

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

Tutoriel : Reformulation Quadratique Convexe pour l'optimisation Quadratique discrète : résultats de base et extensions récentes

Sourour Elloumi

Nous considérons le problème (QP) de la minimisation d'une fonction quadratique sous des contraintes linéaires ou quadratiques. Les variables sont entières et bornées. Ce problème très général permet de modéliser de nombreux problèmes classiques en Optimisation Combinatoire et constitue une première généralisation de la programmation linéaire en nombres entiers. Une différence majeure entre (QP) et les programmes linéaires en nombres entiers réside dans le fait que, en général, sa relaxation continue fournit un problème lui aussi NP-difficile. Pour contourner cette difficulté, la reformulation quadratique convexe transforme (QP) en un problème (QP') équivalent mais dont la relaxation continue est un problème convexe. Afin de calculer une solution optimale de (QP), on peut alors résoudre (QP') par un algorithme d'énumération implicite basé sur l'optimisation continue convexe. Nous faisons un tour d'horizon de développements récents de cette approche. Nous montrons en particulier comment les relaxations semi-définies positives permettent de construire les problèmes équivalents (QP') les plus intéressants. Dans le cas des variables binaires, nous donnons une vision des linéarisations classiques comme un cas particulier de reformulation quadratique convexe. Enfin, nous illustrons la généralité et l'efficacité expérimentale de la résolution exacte par reformulation quadratique convexe sur différents problèmes d'Optimisation Combinatoire. Références A. Billionnet et S. Elloumi. Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem . Mathematical Programming, 109(1): 55-68, 2007. A. Billionnet, S. Elloumi et M.-C. Plateau. Improving standard solvers convex reformulation for constrained quadratic 0-1 programs: the QCR method. Discrete Applied Math, vol. 157(6), 2009, pp. 1185-1197. A. Billionnet, S. Elloumi et A. Lambert. Extending the QCR method to general mixed-integer programs. Mathematical Programming, vol. 131(1), 2012, pp.381-401

•Feb 26, 2014•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

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
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.
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.
-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.
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.
Nous considérons le problème (QP) de la minimisation d'une fonction quadratique sous des contraintes linéaires ou quadratiques. Les variables sont entières et bornées. Ce problème très général permet de modéliser de nombreux problèmes classiques en Optimisation Combinatoire et constitue une première généralisation de la programmation linéaire en nombres entiers. Une différence majeure entre (QP) et les programmes linéaires en nombres entiers réside dans le fait que, en général, sa relaxation continue fournit un problème lui aussi NP-difficile. Pour contourner cette difficulté, la reformulation quadratique convexe transforme (QP) en un problème (QP') équivalent mais dont la relaxation continue est un problème convexe. Afin de calculer une solution optimale de (QP), on peut alors résoudre (QP') par un algorithme d'énumération implicite basé sur l'optimisation continue convexe. Nous faisons un tour d'horizon de développements récents de cette approche. Nous montrons en particulier comment les relaxations semi-définies positives permettent de construire les problèmes équivalents (QP') les plus intéressants. Dans le cas des variables binaires, nous donnons une vision des linéarisations classiques comme un cas particulier de reformulation quadratique convexe. Enfin, nous illustrons la généralité et l'efficacité expérimentale de la résolution exacte par reformulation quadratique convexe sur différents problèmes d'Optimisation Combinatoire. Références A. Billionnet et S. Elloumi. Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem . Mathematical Programming, 109(1): 55-68, 2007. A. Billionnet, S. Elloumi et M.-C. Plateau. Improving standard solvers convex reformulation for constrained quadratic 0-1 programs: the QCR method. Discrete Applied Math, vol. 157(6), 2009, pp. 1185-1197. A. Billionnet, S. Elloumi et A. Lambert. Extending the QCR method to general mixed-integer programs. Mathematical Programming, vol. 131(1), 2012, pp.381-401
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.
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.