Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem

This article introduces two new techniques for solving the Quadratic Assignment Problem. The first is a heuristic technique, defined in accordance with the Ant System metaphor, and includes as a distinctive feature the use of a new lower bound at each constructive step. The second is a branch-and-bound exact approach, containing some elements introduced in the Ant algorithm. Computational results prove the effectiveness of both approaches.