6533b839fe1ef96bd12a6ea2

RESEARCH PRODUCT

An Exact Algorithm for the Quadratic Assignment Problem on a Tree

Nicos ChristofidesEnrique Benavent

subject

Discrete mathematicsQuadratic assignment problemManagement Science and Operations ResearchTravelling salesman problemComputer Science ApplicationsReduction (complexity)Tree (data structure)symbols.namesakeExact algorithmLagrangian relaxationsymbolsInteger programmingGeneralized assignment problemMathematics

description

The Tree QAP is a special case of the Quadratic Assignment Problem (QAP) where the nonzero flows form a tree. No condition is required for the distance matrix. This problem is NP-complete and is also a generalization of the Traveling Salesman Problem. In this paper, we present a branch-and-bound algorithm for the exact solution of the Tree QAP based on an integer programming formulation of the problem. The bounds are computed using a Lagrangian relaxation of this formulation. To solve the relaxed problem, we present a Dynamic Programming algorithm which is polynomially bounded. The obtained lower bound is very sharp and equals the optimum in many cases. This fact allows us to employ a reduction method to decrease the number of variables and leads to search-trees with a small number of nodes compared to those usually encountered in problems of this type. Computational results are given for problems with size up to 25.

yearjournalcountryeditionlanguage
1989-10-01Operations Research
https://doi.org/10.1287/opre.37.5.760