Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem (Q1025992)

In this paper the authors present three new compact linearizations for the quadratic 0-1 problem. First they review some of the linearizations of the literature: standard linearization, Glover's compact linearization and the modification proposed by Adams, Forrester and Glover. After that, the authors present three new related compact linearizations that differ from each other by the inclusion of additional constrains. Two of these, CL2 and CL3, achieve the same lower bound as does the standard linearization. For achieve this lower bound the linearizations proposed are constructed from a best posiform. The first linearization, CL1, the linearization with the smallest number of constrains, yields a weaker lower bound. However the computational results, which are presented in the last part of the paper, show that the first linearization, CL1, performs the best in terms of computational time, when solved by Cplex.