search query: @indexterm COMBINATIONAL OPTIMIZATION / total: 8
reference: 4 / 8
| Author: | Mans, B. Mautor, T. Roucariol, C. |
| Title: | A parallel depth first search branch and bound algorithm for the quadratic assignment problem |
| Journal: | European Journal of Operational Research
1995 : MAR 16, VOL. 81:3, p. 617-628 |
| Index terms: | BRANCH AND BOUND METHODS COMBINATIONAL OPTIMIZATION ALGORITHMS |
| Language: | eng |
| Abstract: | The authors propose a new parallel Branch and Bound algorithm for the Quadratic Assignment Problem, which is a Combinational 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 is proved by this program. |
SCIMA