Back

G-2006-39

Improved Compact Linearizations for the Unconstrained Quadratic 0-1 Minimization Problem

and

BibTeX reference

We present and compare three new compact linearizations for the quadratic 0-1 minimization problem, two of which achieving the same lower bound than the "standard linearization". Two of the linearizations require the same number of constraints with respect to Glover's one, while the last one requires n additional constraints where n is the number of variables in the quadratic 0-1 problem. All three linearizations require the same number of additional variables than Glover's linearization. This improves on the linearization of Adams, Forrester and Glover (2004) which requires n additional variables and 2n additional constraints to reach the same lower bound than the standard linearization. Computational results show however that linearizations achieving a weaker lower bound at the root node have better global performances than stronger linearizations when solved by Cplex.

, 40 pages

This cahier was revised in July 2007

Research Axis

Research applications

Publication

Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem
and
Discrete Applied Mathematics, 157(6), 1267–1290, 2009 BibTeX reference