Depth-m search in branch-and-bound algorithms |
| |
Authors: | Toshihide Ibaraki |
| |
Affiliation: | (1) Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University, Kyoto, Japan |
| |
Abstract: | A new search strategy, called depth-m search, is proposed for branch-and-bound algorithms, wherem is a parameter to be set by the user. In particular, depth-1 search is equivalent to the conventional depth-first search, and depth- search is equivalent to the general heuristic search (including best-bound search as a special case). It is confirmed by computational experiment that the performance of depth-m search continuously changes from that, of depth-first search to that of heuristic search, whenm is changed from 1 to . The exact upper bound on the size of the required memory space is derived and shown to be bounded byO(nm), wheren is the problem size. Some methods for controllingm during computation are also proposed and compared, to carry out the entire computation within a given memory space bound. |
| |
Keywords: | Branch-and-bound combinatorial optimization depth-m search memory space bound |
本文献已被 SpringerLink 等数据库收录! |
|