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

Bernard Mans, Thierry Mautor*, Catherine Roucairol

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)

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 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.

Original languageEnglish
Pages (from-to)617-628
Number of pages12
JournalEuropean Journal of Operational Research
Volume81
Issue number3
DOIs
Publication statusPublished - 16 Mar 1995
Externally publishedYes

Keywords

  • Branch and bound
  • Combinatorial optimization
  • Parallel algorithm
  • Quadratic assignment problem

Fingerprint Dive into the research topics of 'A parallel depth first search branch and bound algorithm for the quadratic assignment problem'. Together they form a unique fingerprint.

Cite this