An exact branch and bound algorithm for the general quadratic assignment problem
MetadataShow full item record
This research is concerned with the development of an exact algorithm for a general quadratic assignment problem (QAP), of which the Koopmans-Beckmann formulation, in the context of an analysis of the location of economic activities or facilities, is a special case. The algorithm is based on the linearization of a general QAP of size n into a linear assignment problem of size n(n-l)/2. The objective value and the dual solution of this subproblem are used to compute the lower bound used in an exact branch and bound procedure. Computational experience and comparisons to other well known methods are discussed.