THE QUADRATIC ASSIGNMENT PROBLEM USING A GENERALIZED DEFORMABLE MODEL

Abstract

The quadratic assignment problem (QAP) belongs to the category of NP-complete, combinatorial optimization problems. Given a set of locations, the problem is one of obtaining an optimal assignment of a set of factories to these locations with the minimum cost. Though several procedures have been developed since the QAP was proposed in 1957, none of them is computationally feasible for any but small size problems. The present paper describes a solution strategy to the QAP that is based on a generalized deformable model. Recursive relations required in the solution of the problem are identified as being similar in form to those of the Hopfield neural networks. Each factory, initially placed randomly along a circle centered at the centroid of the distribution of locations, is gradually moved towards some location until it is eventually close enough to define an assignment. Good results are obtained in solving standard problems where the number of factories is less than or equal to twenty. Even for larger dimensionality problems, such as one involving thirty factories, the assignment results in a total cost that is only about 10% higher than the known minimum. Characteristics of neural networks, in particular the potential for parallel processing, are seen as the principal driving force behind the study of such techniques.