Accession Number : ADA112858

Title :   A Branch and Bound Based Heuristic for Solving the Quadratic Assignment Problem,

Corporate Author : GEORGIA INST OF TECH ATLANTA PRODUCTION AND DISTRIBUTION RESEARCH CENTER

Personal Author(s) : Bazaraa,M S ; Kirca,O

PDF Url : ADA112858

Report Date : Oct 1981

Pagination or Media Count : 37

Abstract : In this paper a branch and bound algorithm is proposed for solving the quadratic assignment problem. Using symmetric properties of the problem, the algorithm eliminates 'mirror image' branches, thus reducing the search effort. Several routines that transform the procedure into an efficient heuristic are also implemented. These include certain 2-way and 4-way exchanges, selective branching rules, and the use of variable upper bounding techniques for enhancing the speed of fathoming. The computational results are quite encouraging. As an exact scheme, the algorithm solved the 12 facility problem of Nugent et al and the 19 facility problem of Elshafei. More importantly, as a heuristic, the procedure produced the best known solutions for all well-known problems in the literature, and produced improved solutions in several cases. (Author)

Descriptors :   *Quadratic programming, *Algorithms, Problem solving, Heuristic methods, Exchange, Iterations

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE