- Journal
- DISCRETE APPLIED MATHEMATICS
- Année
- 2009
- Volume
- 157
- Numéro
- 6, SI
- Pages
- 1267-1290
- Mois
- MAR 28
- DOI
- 10.1016/j.dam.2007.12.008
Abstract
We present and compare three new compact linearizations for the quadratic 0-1 minimization problem, two of which achieve the same lower bound as does 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 as does Glover's linearization. This is an improvement on the linearization of Adams, Forrester and Glover (2004) which requires n additional variables and 2n additional constraints to reach the same lower bound as does 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. (C) 2008 Elsevier B.V. All rights reserved.