Groupe d’études et de recherche en analyse des décisions


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


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

Ce cahier a été révisé en juillet 2007