<p>The Clique Partitioning Problem might not be the most popular NP-hard problem, but it was efficiently solved using branch-and-bound, see this paper: <a href="http://joc.journal.informs.org/content/6/2/141.abstract">http://joc.journal.informs.org/content/6/2/141.abstract</a></p>

CC BY-SA 3.0
2011-08-29T14:41:36.463Z
2011-08-29T14:41:36.463Z
Florian Jaehn
<p><a href="http://www.springer.com/computer/theoretical+computer+science/book/978-3-642-16532-0" rel="nofollow">Exact Exponential Algorithms</a> is a nice recent book about such algorithms. <a href="http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz" rel="nofollow">Algorithm X</a> for the exact cover problem is also good to know.</p>

CC BY-SA 3.0
2011-08-31T15:39:08.097Z
Be sure to look at the notes at the end of http://www.springer.com/cda/content/document/cda_downloaddocument/9783642165320-c1.pdf
Radu GRIGore
CC BY-SA 3.0
2011-08-31T15:37:13.937Z
2011-08-31T15:37:13.937Z
Radu GRIGore
<p>For TSP, checkout this book...
<a href="http://www.tsp.gatech.edu/book/index.html">http://www.tsp.gatech.edu/book/index.html</a></p>

<p>My understanding is that there is no one tool to kill them all. Arguably any recursive solution deploying backtracking and some scoring function is using branch and bound. As such, a large fraction of solvers to NP hard problems use some form of branch and bound.</p>

CC BY-SA 3.0
2011-08-28T16:56:42.027Z
2011-08-28T16:56:42.027Z
Sariel Har-Peled
<p>Branch and bound is an effective heuristic for search problems, and <a href="http://en.wikipedia.org/wiki/Branch_and_bound">Wikipedia lists a number of hard problems</a> where branch-and-bound has been used. However, I haven't been able to find references to suggest that it's more than just "one method" for solving these problems. </p>

<p>Anecdotally, I've heard that some of the best heuristics for SAT and integer programming come from branch and bound, so my question is:</p>

<blockquote>
  <p>Can someone point me to any references detailing <em>effective</em> uses of
  branch and bound for NP-hard problems ?</p>
</blockquote>

CC BY-SA 3.0
2011-08-29T15:27:16.990Z
I'm just now reading this paper for a different reason, but it seems to touch on your question, and it is fascinating: [Algorithm Portfolios](http://www.sciencedirect.com/science/article/pii/S0004370200000813) by Gomes and Selman.
Aaron Sterling
CC BY-SA 3.0
2011-08-30T18:20:29.483Z
A good book to read about integer programming is Integer and Combinatorial Optimization by Nemhauser & Wolsey. Covers a wide range of topics including different paradigms like branch and bound, branch and cut, etc. and other IP techniques like cutting planes, etc.
Opt
<ds.algorithms><reference-request><optimization><heuristics>
Successful application of branch-and-bound methods for NP-hard problems
Suresh Venkat
# Successful application of branch-and-bound methods for NP-hard problems

(Asked by: username_0 on 2011-08-28)

Branch and bound is an effective heuristic for search problems, and [Wikipedia lists a number of hard problems](http://en.wikipedia.org/wiki/Branch_and_bound) where branch-and-bound has been used. However, I haven't been able to find references to suggest that it's more than just "one method" for solving these problems.

Anecdotally, I've heard that some of the best heuristics for SAT and integer programming come from branch and bound, so my question is:

> Can someone point me to any references detailing *effective* uses of
> branch and bound for NP-hard problems ?

**Tags:** ds.algorithms, reference-request, optimization, heuristics

> **Comments:**
> **username_1**: I'm just now reading this paper for a different reason, but it seems to touch on your question, and it is fascinating: [Algorithm Portfolios](http://www.sciencedirect.com/science/article/pii/S0004370200000813) by Gomes and Selman.  
> **username_2**: A good book to read about integer programming is Integer and Combinatorial username_2imization by Nemhauser & Wolsey. Covers a wide range of topics including different paradigms like branch and bound, branch and cut, etc. and other IP techniques like cutting planes, etc.  

---

## 3 answers

### Answer by username_5 on 2011-08-28. Score: 9 | Accepted answer

For TSP, checkout this book...
<http://www.tsp.gatech.edu/book/index.html>

My understanding is that there is no one tool to kill them all. Arguably any recursive solution deploying backtracking and some scoring function is using branch and bound. As such, a large fraction of solvers to NP hard problems use some form of branch and bound.


---

### Answer by username_3 on 2011-08-29. Score: 9

The Clique Partitioning Problem might not be the most popular NP-hard problem, but it was efficiently solved using branch-and-bound, see this paper: <http://joc.journal.informs.org/content/6/2/141.abstract>


---

### Answer by username_4 on 2011-08-31. Score: 4

[Exact Exponential Algorithms](http://www.springer.com/computer/theoretical+computer+science/book/978-3-642-16532-0) is a nice recent book about such algorithms. [Algorithm X](http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz) for the exact cover problem is also good to know.

> **Comments:**
> **username_4**: Be sure to look at the notes at the end of http://www.springer.com/cda/content/document/cda_downloaddocument/9783642165320-c1.pdf  

---

