Does branch-and-bound always achieve a globally optimal solution?

The idea of branch and bound is almost close to brute force search.

We keep splitting the search space, and work on the subproblems. The bounding part of the algorithm stop us from exploring a branch only if it is proven to not consist of the optimal solution.

Since we do not discard any potential global optimal, we will find one if it exists.

Tags:

Optimization

Proof Verification

Related

If $\frac {a_{(n+1)} }{a_n} < \frac {n^2}{(n+1)^2}$ and if $a_n > 0$ for all n . $\sum a_n$ converges or not The limit of $\frac{n^3-3}{2n^2+n-1}$ Doubt on limits evaluation. Beginner probability question about the phrase "order doesn't matter" Integral $\int_0^\infty \frac{\arctan(x) dx}{x(1+x^2)}$? If two spaces are homeomorphic and one is a metric space must the other be as well? Which method to use to integrate this function? Summation of this series ${1\over 2}\left[1+{1 \over 3}\left({1 \over 4}\right)^2+ {1 \over 5}\left({1 \over 4}\right)^4+\cdots\right]$ A continuous bijection between two complete metric spaces that is not a homeomorphism. Cap product Hochschild (co)homology Choosing office hours to maximise number of students who can attend at least one time slot Does the domain of the function depend on how you write it?

Recent Posts