A parallel depth first search branch and bound algorithm for the quadratic assignment problem

A parallel depth first search branch and bound algorithm for the quadratic assignment problem

0.00 Avg rating0 Votes
Article ID: iaor19981371
Country: Netherlands
Volume: 81
Issue: 3
Start Page Number: 617
End Page Number: 628
Publication Date: Mar 1995
Journal: European Journal of Operational Research
Authors: , ,
Keywords: combinatorial analysis
Abstract:

We propose a new parallel Branch and Bound algorithm for the Quadratic Assignment Problem, which is a Combinatorial Optimization problem known to be very hard to solve exactly. An original method to distribute work to processors using the notion of Feeding Tree is presented. When adequately used, it allows us to reduce memory contention and load unbalance. Therefore, a linear speed-up in the number of processors is reached on a shared memory multiprocessor, the Cray 2, and the optimality of solutions for famous problems of size less than 20 (Nugent 16, Elshafei 19, Scriabin–Vergin 20, . . .) is proved by this program. The implementation analysis shows that these results are more than an improvement due to hardware evolution and confirms the usefulness of our parallel Branch and Bound algorithm for larger Quadratic Assignment Problems.

Reviews

Required fields are marked *. Your email address will not be published.