Geodesic
Tree Elaboration Strategies in Branch-and-Bound Algorithms for Solving the Quadratic Assignment Problem
Yugoslav journal of operations research, Tome 11 (2001) no. 1, p. 41 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

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-l reduction in runtime 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.
Classification : 90B80 90C57 90C27
Keywords: Quadratic assignment problem, branch-and-bound algorithm. 
@article{YJOR_2001_11_1_a3,
     author = {Peter M. Hahn and William L. Hightower and Terri Anne Johnson and Monique Guignard-Spielberg and Catherine Roucairol},
     title = {Tree {Elaboration} {Strategies} in {Branch-and-Bound} {Algorithms} for {Solving} the {Quadratic} {Assignment} {Problem}},
     journal = {Yugoslav journal of operations research},
     pages = {41 },
     year = {2001},
     volume = {11},
     number = {1},
     zbl = {1073.90524},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2001_11_1_a3/}
}
TY  - JOUR
AU  - Peter M. Hahn
AU  - William L. Hightower
AU  - Terri Anne Johnson
AU  - Monique Guignard-Spielberg
AU  - Catherine Roucairol
TI  - Tree Elaboration Strategies in Branch-and-Bound Algorithms for Solving the Quadratic Assignment Problem
JO  - Yugoslav journal of operations research
PY  - 2001
SP  - 41 
VL  - 11
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/YJOR_2001_11_1_a3/
LA  - en
ID  - YJOR_2001_11_1_a3
ER  - 
%0 Journal Article
%A Peter M. Hahn
%A William L. Hightower
%A Terri Anne Johnson
%A Monique Guignard-Spielberg
%A Catherine Roucairol
%T Tree Elaboration Strategies in Branch-and-Bound Algorithms for Solving the Quadratic Assignment Problem
%J Yugoslav journal of operations research
%D 2001
%P 41 
%V 11
%N 1
%U http://geodesic.mathdoc.fr/item/YJOR_2001_11_1_a3/
%G en
%F YJOR_2001_11_1_a3
Peter M. Hahn; William L. Hightower; Terri Anne Johnson; Monique Guignard-Spielberg; Catherine Roucairol. Tree Elaboration Strategies in Branch-and-Bound Algorithms for Solving the Quadratic Assignment Problem. Yugoslav journal of operations research, Tome 11 (2001) no. 1, p. 41 . http://geodesic.mathdoc.fr/item/YJOR_2001_11_1_a3/