I've been studying Branch and Bound's graph algorithm and I hear it always finds the optimal path because it uses previously found solutions to find others, but I haven't been able to find a proof on why it finds the optimal path(In fact most sites kind of do a bad job generalizing the algorithm itself). I was wondering what the proof is that this algorithm always find the optimal path in the case of a graph with 1 or more goal nodes?

  • $\begingroup$ Branch and bound is a paradigm and not a single algorithm. Which algorithm are you specifically referring to? Is it the algorithm that finds the optimal path between two points of a graph? $\endgroup$ – nbro May 19 '19 at 20:26
  • $\begingroup$ O sorry I'll update the question now. Thanks for letting me know though! I've only seen it in the context of a graph algorithm. $\endgroup$ – Dylan Y May 19 '19 at 20:38
  • $\begingroup$ Check this question: math.stackexchange.com/q/2915145/168764. Essentially, B&B can degenerate to an exhaustive search, which, in case the graph has a finite number of nodes, should find the optimal solution. However, I don't have a formal proof and I would like to see it too. $\endgroup$ – nbro May 19 '19 at 20:44
  • $\begingroup$ I feel like a quick proof would be a proof by contradiction maybe? Like assume there's a solution more optimal then the one found by B&B, which means it's cheaper in total cost, but that creates a contradiction because if there is a cheaper path it would have been explored by B&B because B&B would only stop searching after it's pruned everything more expensive or searched everything? $\endgroup$ – Dylan Y May 19 '19 at 20:56
  • $\begingroup$ That might be a good approach, but this is just an intuition. You might assume that an exhaustive search (on a graph with a finite number of nodes) is able to find the optimal solution and then you just need to worry about the "bound" part, that is, that the pruning of the tree (or search space) doesn't exclude a possible optimal solution. $\endgroup$ – nbro May 19 '19 at 21:07

My attempt was proof by contradiction. We can assume B&B found a sub-optimal path, but that would create a contradiction, because the only way B&B would miss an optimal path is if it skipped it completely (this part I don't know how to prove) or the related part of the search space was pruned.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.