An Average-Case Analysis of Branch-and-Bound with Applications: Summary of Results

Weixiong Zhang, Richard E. KorfAAAI 1992 · OpenReview

Abstract

Motivated by an anomaly in branch-and-bound (BnB) search, we analyze its average-case complexity. We first delineate exponential vs polynomial average-case complexities of BnB. When best-first BnB is of linear complexity, we show that depth-first BnB has polynomial complexity. For problems on which best-first BnB has exponential complexity, we obtain an expression for the heuristic branching factor. Next, we apply our analysis to explain an anomaly in lookahead search on sliding-tile puzzles, and to predict the existence of an average-case complexity transition of BnB on the Asymmetric Traveling Salesman Problem. Finally, by formulating IDA* as costbounded BnB, we show its average-case optimality, which also implies that RBFS is optimal on average.

Introduction

Branch-and-Bound (BnB) is a fundamental algorithm for discrete optimization. While its worst-case performance is typically exponential, its practical behavior can be highly variable. A notable anomaly occurs in sliding-tile puzzles: depth-first search often generates fewer nodes on larger puzzles than on smaller ones when searching to the same depth. This paper provides a rigorous average-case analysis to explain such phenomena, identifying a sharp phase transition in search complexity.

The $B \cdot p_0$ Threshold

The core of the analysis uses a uniform random tree model with branching factor $B$ and edge costs drawn from a discrete distribution. A critical parameter is $p_0$, the probability that an edge has zero cost (meaning the child node has the same heuristic value as its parent). The product $B \cdot p_0$ represents the expected number of "same-cost" children.

The authors prove that the boundary $B \cdot p_0 = 1$ separates two distinct complexity regimes. When $B \cdot p_0 < 1$, the search cost grows exponentially with depth. Conversely, when $B \cdot p_0 > 1$, the search enters an "easy region" where the complexity becomes polynomial.

The phase transition boundary $B \cdot p_0 = 1$ separates the difficult exponential region from the easy polynomial region.

Explaining the Sliding-Tile Puzzle Anomaly

This theoretical framework directly explains the counterintuitive behavior observed in sliding-tile puzzles. In these puzzles, as the size increases (from the 8-puzzle to the 99-puzzle), the branching factor $B$ increases while the probability $p_0$ of a zero-cost move remains relatively stable (around 0.5). This shift pushes larger puzzles deeper into the polynomial "easy" region.

Experimental results on sliding-tile puzzles show that larger puzzles (higher B) result in slower node growth for a fixed lookahead depth d.

As shown in the figure, for a fixed lookahead depth $d$, the number of nodes generated for the 99-puzzle grows much more slowly than for the 8-puzzle, confirming the transition from exponential to polynomial growth as $B$ increases. This explains why searching a larger state space can actually be computationally cheaper for a fixed horizon.

Applications and Optimality

The analysis also predicts a complexity transition in the Asymmetric Traveling Salesman Problem (ATSP). By varying the range of city distances $k$, the probability $p_0$ changes, moving the problem across the $B \cdot p_0 = 1$ threshold. When $k$ is small, $p_0$ is high, making the problem easy; as $k$ increases, $p_0$ drops, and the problem becomes exponentially harder.

Furthermore, the paper establishes the average-case optimality of linear-space algorithms like Iterative-Deepening-A (IDA) and Recursive Best-First Search (RBFS). By formulating IDA* as a cost-bounded BnB, the authors show that no other linear-space algorithm can outperform them on average within the uniform random tree model.

Conclusion

By moving beyond worst-case bounds, this work provides a more nuanced understanding of heuristic search. The identification of the $B \cdot p_0$ threshold offers a practical metric—local consistency—to estimate search difficulty and explains why increasing problem size can sometimes lead to more efficient search. These results provide a theoretical foundation for the performance of modern search algorithms on large-scale optimization problems.

Summary updated

Abstract

Motivated by an anomaly in branch-and-bound (BnB) search, we analyze its average-case complexity. We first delineate exponential vs polynomial average-case complexities of BnB. When best-first BnB is of linear complexity, we show that depth-first BnB has polynomial complexity. For problems on which best-first BnB has exponential complexity, we obtain an expression for the heuristic branching factor. Next, we apply our analysis to explain an anomaly in lookahead search on sliding-tile puzzles, and to predict the existence of an average-case complexity transition of BnB on the Asymmetric Traveling Salesman Problem. Finally, by formulating IDA* as costbounded BnB, we show its average-case optimality, which also implies that RBFS is optimal on average.
BibTeX
@inproceedings{zhang1992average,
  author = {Weixiong Zhang and Richard E. Korf},
  title = {{An Average-Case Analysis of Branch-and-Bound with Applications: Summary of Results}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
  url = {https://openreview.net/forum?id=rkZRtCgu-B},
}
Figure