An exact branch and bound algorithm for the general quadratic assignment problem
Date
1988-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Texas Tech University
Abstract
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.
Description
Keywords
Branch and bound algorithms, Mathematical optimization, Quadratic, Equations, Combinatorial optimization