An exact branch and bound algorithm for the general quadratic assignment problem

Date

1988-12

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

Citation