Tree elaboration strategies in branch-and-bound algorithms for solving the quadratic assignment problem

This paper presents a new strategy for selecting nodes in a branch-and-bound algorithm for solving exactly the Quadratic Assignment Problem (QAP). It was developed when it was learned that older strategies had failed on larger-sized problems. The strategy is a variation of the polytomic depth-first search of Mautor and Roucairol which extends a node by all assignments of an unassigned facility to unassigned locations based upon the counting of ‘forbidden’ locations. A forbidden location is one where the addition of the corresponding leader (linear cost) element would increase the lower bound beyond the upper bound. We learned that this fortuitous situation never occurs near the root on Nugent problems larger than 15. One has to make better estimates of the bound if the strategy is to work. We have, therefore, designed and implemented an increasingly improved set of bound calculations. The better of these bound calculations is to be utilized near the root and the less accurate (poorer bounds) is utilized further into the tree. The result is an effective and powerful technique for shortening the run times of problem instances in the range of size 16 to 25. Run times were decreased generally by five- or six-to-one and the number of nodes evaluated was decreased as much as 10-to-one. Later improvements in our strategy produced a better than 3-to-1 reduction in run time so that overall improvement in run time was as high as 20-to-1 compared to our earlier results. At the end of our paper, we compare the performance of the four most successful algorithms for exact solution of the QAP.