Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method

Alain Billionnet, Sourour Elloumi and Marie-Christine Plateau
Publication type:
Paper in peer-reviewed journals
Discrete Applied Mathematics, vol. 157, pp. 1185-1197
Keywords :
Experiments; Task allocation; Densest k-subgraph; Graph bisection; Semidefinite programming; Convex quadratic programming; Quadratic 0-1 programming;
Let View the MathML source be a 0-1 quadratic program which consists in minimizing a quadratic function subject to linear equality constraints. In this paper, we present QCR, a general method to reformulate View the MathML source into an equivalent 0-1 program with a convex quadratic objective function. The reformulated problem can then be efficiently solved by a classical branch-and-bound algorithm, based on continuous relaxation. This idea is already present in the literature and used in standard solvers such as CPLEX. Our objective in this work was to find a convex reformulation whose continuous relaxation bound is, moreover, as tight as possible. From this point of view, we show that QCR is optimal in a certain sense. State-of-the-art reformulation methods mainly operate a perturbation of the diagonal terms and are valid for any {0,1} vector. The innovation of QCR comes from the fact that the reformulation also uses the equality constraints and is valid on the feasible solution domain only. Hence, the superiority of QCR holds by construction. However, reformulation by QCR requires the solution of a semidefinite program which can be costly from the running time point of view. We carry out a computational experience on three different combinatorial optimization problems showing that the costly computational time of reformulation by QCR can however result in a drastically more efficient branch-and-bound phase. Moreover, our new approach is competitive with very specific methods applied to particular optimization problems.
Keywords (translation) :
Bissection graphique; Répartition des tâches; Expériences; Programmation semi-définie; K-sous-graphe plus dense; Quadratique 0-1 programmation; Programmation quadratique convexe;
    author={Alain Billionnet and Sourour Elloumi and Marie-Christine 
           Plateau },
    title={Improving the performance of standard solvers for quadratic 
           0-1 programs by a tight convex reformulation: The QCR method },
    journal={Discrete Applied Mathematics },
    year={2009 },
    volume={157 },