Memory Space Controllable Search Strategies for Branch-and-Bound Algorithms

Masaharu IMAI, Yuuji YOSHIDA, Teruo FUKUMURA

Summary :

The amount of memory space required by a branch-and-bound algorithm depends on the search strategy used in the algorithm. From the viewpoint of implementing branch-and-bound algorithms, it is desirable that the amount of memory space can be bounded to some feasible size. In this paper, we propose two new search strategies for branch-and-bound algorithms, by which the amount of required memory space is controllable. These strategies are named pdfs (parallel depth-first search)" and blis (breadth limited search)", respectively. One of the main results of this paper is that (a) the amount of required memory space of any of these strategies is a linear function of the size of the given problem and (b) the amount of required memory space is controllable by adjusting appropriate parameter. That is, these search strategies are adaptable to the available memory space. Another result of this paper is that the computational performance of a branch-and-bound algorithm, using any of these strategies, can be improved by adjusting appropriate parameters.

• Publication: IEICE TRANSACTIONS on transactions Vol.E65-E No.5 pp.257-264
• Publication Date: 1982/05/25
• Type of Manuscript: PAPER
• Category: Miscellaneous

Authors

Masaharu IMAI
Yuuji YOSHIDA
Teruo FUKUMURA

Keyword