A linear formulation with O(n2) variables for quadratic assignment problems with Manhattan distance matrices

Abstract

We present O(n2)an integer linear formulation that uses the so-called “distance variables” to solve the quadratic assignment problem (QAP). The formulation performs particularly well for problems with Manhattan distance matrices. It involves O(n2) variables. Valid equalities and inequalities are proposed divided into two families. First, a family of inequalities valid for any quadratic assignment problems, and second, a family valid only for problems with Manhattan distance matrices, for which we exploit metric properties, as well as an algebraic characterization that Mittelman and Peng (SIAM J Opt 2010:20(6), 3408–3426, 2010) recently proved. We numerically tested the lower bound provided by the linear relaxation using instances of the quadratic assignment problem library (QAPLIB) with randomly generated distance matrices, as well as Manhattan distance matrices. Our results are compared with the best known lower bounds. For Manhattan distance matrices, the formulation gives a very competitive lower bound in a short computational time, improving seven best lower bounds of QAPLIB instances for which no optimality proofs exist.

Keywords

• 90-XX
• 90Cxx
• 65K05