A revised reformulation-linearization technique for the quadratic assignment problem

The Reformulation Linearization Technique (RLT) applied to the Quadratic Assignment Problem yields mixed 0–1 programming problems whose linear relaxations provide a strong bound on the objective value. Nevertheless, in the high level RLT representations the computation requires much effort. In this paper we propose a new compact reformulation for each level of the RLT representation exploiting the structure of the problem. Computa- tional results on some benchmark instances indicate the potential of the new RLT repre- sentations as the level of the RLT increases.