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.
Published May 2006 , 40 pages
This cahier was revised in July 2007