Answers.Body: <p><a href="https://en.wikipedia.org/wiki/Branch_and_bound#Generic_version" rel="nofollow noreferrer">Branch and Bound</a> is similar to an <a href="https://en.wikipedia.org/wiki/Brute-force_search" rel="nofollow noreferrer">exhaustive search</a>, except it incorporates a method for computing lower bounds on branches. If the lower bound on a given branch is greater than the upper bound on the problem (i.e. the current best solution encountered), that branch can be discarded since it will never produce an optimal solution.</p>
  
  <p>Hence, since you explore all options except those you <em>know</em> will produce values less optimal than your current best value, you are guaranteed to encounter the global optimum.</p>
  
  <p>Note this is a generic algorithm, and you will need to reference a specific implementation if you want proof of why it satisfies these criteria.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-26T15:51:48.633Z
Answers.LastActivityDate: 2020-05-26T16:26:50.077Z
Answers.LastEditDate: 2020-05-26T16:26:50.077Z
Answers.UserDisplayName: brazofuerte
Answers.Body: <p>My attempt was proof by contradiction. We can assume B&amp;B found a sub-optimal path, but that would create a contradiction, because the only way B&amp;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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-19T21:13:59.753Z
Answers.LastActivityDate: 2019-05-19T22:20:44.360Z
Answers.LastEditDate: 2019-05-19T22:20:44.360Z
Answers.UserDisplayName: Gooby
Body: <p>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</p>
  
  <p>However, I haven't been able to find a proof of why it finds the optimal path. (In fact, most sites kind of do a bad job generalizing the algorithm itself.) </p>
  
  <p>What is the proof that this algorithm always finds the optimal path in the case of a graph with 1 or more goal nodes?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-26T16:34:59.150Z
Comments.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/108506/discussion-on-question-by-dylan-y-proof-branch-and-bound-always-finds-optimal-pa).
Comments.UserDisplayName: nbro
Tags: <search><proofs><graphs><branch-and-bound>
Title: What is the proof that the branch and bound algorithm always finds optimal path in a graph?
UserDisplayName: Gooby
ThreadText: # What is the proof that the branch and bound algorithm always finds optimal path in a graph?
  
  (Asked by: username_0 on 2019-05-19)
  
  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
  
  However, I haven't been able to find a proof of why it finds the optimal path. (In fact, most sites kind of do a bad job generalizing the algorithm itself.)
  
  What is the proof that this algorithm always finds the optimal path in the case of a graph with 1 or more goal nodes?
  
  **Tags:** search, proofs, graphs, branch-and-bound
  
  > **Comments:**
  > **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/108506/discussion-on-question-by-dylan-y-proof-branch-and-bound-always-finds-optimal-pa).  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-05-26. Score: 0
  
  [Branch and Bound](https://en.wikipedia.org/wiki/Branch_and_bound#Generic_version) is similar to an [exhaustive search](https://en.wikipedia.org/wiki/Brute-force_search), except it incorporates a method for computing lower bounds on branches. If the lower bound on a given branch is greater than the upper bound on the problem (i.e. the current best solution encountered), that branch can be discarded since it will never produce an optimal solution.
  
  Hence, since you explore all options except those you *know* will produce values less optimal than your current best value, you are guaranteed to encounter the global optimum.
  
  Note this is a generic algorithm, and you will need to reference a specific implementation if you want proof of why it satisfies these criteria.
  
  
  ---
  
  ### Answer by username_0 on 2019-05-19. Score: -1
  
  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.
  
  
  ---
  
  