|
|||||
|
|
Speedup estimates for some variants of the parallel implementations of the branch-and-bound method |
|
| Authors: | M. A. Posypkin I. Kh. Sigal |
| Affiliation: | (1) Institute of System Analysis, Russian Academy of Sciences, pr. Shestidesyatiletiya Oktyabrya 9, Moscow, 117312, Russia;(2) Computing Center, Russian Academy of Sciences, ul. Vavilova 40, Moscow, 119991, Russia |
| Abstract: | The efficiency of parallel implementations of the branch-and-bound method in discrete optimization problems is considered. A theoretical analysis and comparison of two parallel implementations of this method is performed. A mathematical model of the computation process is constructed and used to obtain estimates of the maximum possible speedup. Examples of problems in which none of these two parallel implementations can speed up the computations are considered. |
| Keywords: | algorithms for parallel computations discrete optimization branch-and-bound method speedup estimate model of the computation process |
| 本文献已被 SpringerLink 等数据库收录！ | |