Stochastic Modeling of Branch-and-Bound Algorithms with Best-First Search

Branch-and-bound algorithms are organized and intelligently structured searches of solutions in a combinatorially large problem space. In this paper, we propose an approximate stochastic model of branch-and-bound algorithms with a best-first search. We have estimated the average memory space required and have predicted the average number of subproblems expanded before the process terminates. Both measures are exponentials of sublinear exponent. In addition, we have also compared the number of subproblems expanded in a best-first search to that expanded in a depth-first search. Depth-first search has been found to have computational complexity comparable to best-first search when the lower-bound function is very accurate or very inaccurate; otherwise, best-fit search is usually better. The results obtained are useful in studying the efficient evaluation of branch-and-bound algorithms in a virtual memory environment. They also confirm that approximations are very effective in reducing the total number of iterations.