THE POWER OF UPPER AND LOWER BOUNDING FUNCTIONS IN BRANCH-AND-BOUND ALGORITHMS
Toshihide Ibaraki · Journal of the Operations Research Society of Japan · 1982
In a branch-and-bound algorithm, a partial problem P_i is terminated if the lower bound of the optimal value of Pi is greater (in case all optimal solutions are sought) or not smaller (in case a single optimal solution is sought) than the least upper bound on the optimal value of the original minimization problem P_0 currently available. Although it seems obvious that tighter lower bounding function and upper bounding function always improve the efficiency of a branch-and-bound algorithm, counterexamples can be easily constructed. In this paper, therefore, it is extensively studied when such improvement is guaranteed, for typical search strategies such as heuristic search, best-bound search and depth-first search. The model of branch-and-bound algorithms used for investigation is quite general in the sense that it allows the dominance test as well as the lower bound test mentioned above. The efficiency is measured by the number of partial problems decomposed in the execution of the algorithm.