A level-2 reformulation-linearization technique bound for the quadratic assignment problem

This paper studies polyhedral methods for the quadratic assignment problem. Bounds on the objective value are obtained using mixed 0-1 linear representations that result from a reformulation-linearization technique (rlt). The rlt provides different "levels" of representations that give increasing strength. Prior studies have shown that even the weakest level-1 form yields very tight bounds, which in turn lead to improved solution methodologies. This paper focuses on implementing level-2. We compare level-2 with level-1 and other bounding mechanisms, in terms of both overall strength and ease of computation. In so doing, we extend earlier work on level-1 by implementing a Lagrangian relaxation that exploits block-diagonal structure present in the constraints. The bounds are embedded within an enumerative algorithm to devise an exact solution strategy. Our computer results are notable, exhibiting a dramatic reduction in nodes examined in the enumerative phase, and allowing for the exact solution of large instances. (c) 2006 Elsevier B.V. All rights reserved.