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

Alain Billionnet, Sourour Elloumi, Marie-Christine Plateau

Published Jan 1, 2005• 9 citations

Abstract

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.

Related papers

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, 200511 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, 20090 citations

Recent advances in solving some optimization problems in graphs by quadratic programming

Sourour Elloumi, Amélie Lambert

We review Quadratic Convex Reformulation (QCR) for quadratic pro-grams with general integer variables. This solution 2-phase approachconsist in first reformulating the quadratic program into an equivalentother problem having a convex ob jective function. The second phaserelies on MIP solvers that solve the reformulated problem by standardbranch-and-b ound. Then, we consider some graph partitioning problemsthat can be formulated as quadratic programs with binary variables. Weshow many enhancements of the standard QCR method that efficientlysolve graph partitioning problems

Jul 7, 20140 citations

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 ResearchApr 1, 200822 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, 20140 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, 20120 citations