Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Are there any theoretical results on the performance of branch-and-bound, even for a subset of instances of a particular discrete optimization problem?
As an example, does there exist a result of the form "When instances of problem $\Pi$ satisfy properties $P_1, P_2,...$ or $R_1, R_2, ...$, branch-and-bound finds an $\alpha$-approximation to the global optimum (maybe even w.h.p. or in expectation with respect to randomness in the instance) in a polynomial number of nodes"?
If the problem you are solving is in $P$, I guess you can construct a branch-and-bound algorithm that only produces a polynomial number of nodes, since you can use your polynomial time algorithm to make a perfect prediction which branch to explore first, and produce perfect bounds that allow you to prune away every node in the tree except the ones that lead to the optimal solution. But in practice, you would not even bother with branch-and-bound in those cases.
I know there are papers on a technique called measure and conquer, which is used to obtain tighter bounds on the number of nodes in a branch-and-bound tree of $NP$-complete problem than the trivial $b^n$ where $b$ is the number of branching decisions you can make at each step an $n$ is the depth of the tree. Typically, these papers obtain results of the kind: problem X can be solved in $O^*(c^n)$ where typically $1<c\leq b$ and $O^*$ is similar to the common $O$ but also ignores polynomial factors. Some proofs may show that $c$ is a lower number if the instance has certain properties (e.g. bounded degree).
Similarly, there are sophisticated branching algorithms that have been analyzed with other techniques. For the Maximum Independent Set problem, Wikipedia currently lists a reference that can solve this problem in $O(1.1996^n)$ time for general graphs and $O(1.0836^n)$ time if a graph has maximum degree three.
I don't think branch and bound can reduce to a polynomial tree for $NP$-hard problems (if you don't use a super-polynomial algorithm to obtain bounds). Since branch and bound is ultimately a clever enumeration technique, I don't think it is often useful when a problem's structure is so well understood that you can solve it in polynomial time. In those cases you typically employ a greedy, dynamic programming or divide and conquer approach. I am also not aware of any approximation results, although they might exist as I am not that familiar with everything that is happening in the analysis of exponential time and/or approximation algorithms.
I refer you to this question in which I mentioned some of the related papers investigated the performance of the Branch-and-Bound method by estimating the size of the BB tree. The old paper1 by Lai et al. investigated the performance of the parallel BB in which several nodes with least lower bounds are expanded simultaneously. In addition Lobjois et al. in their paper2, tried to estimate, for each particular problem instance, the most appropriate Branch-and-Bound algorithm from among several promising ones. May be these papers can be a good start point for your investigation.
(1): Lai, Ten-Hwang, and Alan Sprague. "Performance of parallel branch-and-bound algorithms." IEEE Transactions on Computers 100.10 (1985): 962-964.
(2): Lobjois, Lionel, and Michel Lemaître. "Branch and bound algorithm selection by performance prediction." AAAI/IAAI. 1998.
Recent work on theoretical results for "strong" branching are here:
"A Theoretical and Computational Analysis of Full Strong-Branching" by Santanu S. Dey, Yatharth Dubey, Marco Molinaro, Prachi Shah at https://arxiv.org/abs/2110.10754
Unfortunately the answer is that we can't know a priori how many nodes we'll have to explore, at least as far as we know today. Because the problem is NP-Hard (assuming we resort to BnB because we have to), determining how many nodes we will explore is as hard as solving the problem itself.
This is unlikely to change in the future because it's intrinsically linked to the NP-hardness of branch-and-bound. BnB is np-hard because at the worst case scenario we'll have to explore all nodes. In continuous bnb, that literally means infinity (integer BnB is somewhat better). People have come up with heuristic estimates but nothing (to my knowledge) that is useful in practice.
At a solver level, this is impossible to predict because of the numerous heuristics in place that accelerate BnB to closer-to-linear runtime complexity. Sometimes these things work amazingly well, and we tune our solvers so that is generally the case, but it can never be true in general for an NP-Hard problem.
I would like to caution you when interpreting results in this domain - while it is true that we can derive correlations (and people have tried) between runtime behaviour and problem formulation by solving a large number of problems, correlation does not imply causation, which is something many people attempt to do. Such results can be statistically true for the specific problem set studied, but have no transferability (pretty much like all of machine learning).
