13
$\begingroup$

Branch and bound is an effective heuristic for search problems, and Wikipedia lists a number of hard problems 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 ?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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 by Gomes and Selman. $\endgroup$
    – Aaron Sterling
    Commented Aug 29, 2011 at 15:27
  • 2
    $\begingroup$ 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. $\endgroup$
    – Opt
    Commented Aug 30, 2011 at 18:20

3 Answers 3

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
9
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

Exact Exponential Algorithms is a nice recent book about such algorithms. Algorithm X for the exact cover problem is also good to know.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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