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 ?

$\endgroup$
  • 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 Aug 29 '11 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 Aug 30 '11 at 18:20
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.

$\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

$\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.

$\endgroup$

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.