Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.03.051 Byline: Warren P. Adams (a), Monique Guignard (b), Peter M. Hahn (c), William L. Hightower (d) Keywords: Combinatorial optimization; Assignment; Branch and bound; Quadratic assignment problem; Reformulation-linearization technique Abstract: 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. Author Affiliation: (a) Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975, USA (b) OPIM Department, The University of Pennsylvania, Philadelphia, PA 19104-6340, USA (c) Department of Electrical and Systems Engineering, The University of Pennsylvania, Philadelphia, PA 19104-6315, USA (d) Mathematics and Computer Science, High Point University, High Point, NC 27262, USA Article History: Received 16 October 2003; Accepted 27 March 2006

The quadratic assignment problem (QAP) is an extremely challenging NP-hard combinatorial optimization program. Due to its difficulty, a research emphasis has been to identify special cases that are polynomially solvable. Included within this emphasis are instances which are linearizable ; that is, which can be rewritten as a linear assignment problem having the property that the objective function value is preserved at all feasible solutions. Various known sufficient conditions for identifying linearizable instances have been explained in terms of the continuous relaxation of a weakened version of the level-1 reformulation-linearization-technique (RLT) form that does not enforce nonnegativity on a subset of the variables. Also, conditions that are both necessary and sufficient have been given in terms of decompositions of the objective coefficients. The main contribution of this paper is the identification of a relationship between polyhedral theory and linearizability that promotes a novel, yet strikingly simple, necessary and sufficient condition for identifying linearizable instances; specifically, an instance of the QAP is linearizable if and only if the continuous relaxation of the same weakened RLT form is bounded. In addition to providing a novel perspective on the QAP being linearizable, a consequence of this study is that every linearizable instance has an optimal solution to the (polynomially-sized) continuous relaxation of the level-1 RLT form that is binary. The converse, however, is not true so that the continuous relaxation can yield binary optimal solutions to instances of the QAP that are not linearizable. Another consequence follows from our defining a maximal linearly independent set of equations in the lifted RLT variable space; we answer a recent open question that the theoretically best possible linearization-based bound cannot improve upon the level-1 RLT form. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem is an NP-hard discrete optimization program that has been extensively studied for over 50 years. It has a variety of applications in many fields, but has proven itself extremely challenging to solve. As a result, an area of research has been to identify special cases which admit efficient solution strategies. This paper examines four such cases, and shows how each can be explained in terms of the dual region to the continuous relaxation of a classical linear reformulation of the problem known as the level-1 RLT representation. The explanations allow for simplifications and/or generalizations of the conditions defining the special cases. [ABSTRACT FROM AUTHOR]