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

Problem Solving

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Problem Solving: Search and Expert Systems

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 haa 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 aaverage-case optimality, which also implies that RBFS is optimal on average.