branch and bound

Question

Can someone explain the branch and bound search technique for me? I need to find a path with the smallest cost from any start node to an end node of any random graph using branch and bound search algorithm.

Answer 1

The basic idea of B & B is:

1. When solving an optimisation problem ("Find an X satisfying criteria Y so as to minimise the cost f(X)"), you build a solution piece by piece -- at any point in time, you have a partial solution, which has a cost.
2. If the nature of the problem is such that the cost of a partial solution can only stay the same or go up as you continue adding pieces to it, then you know that there's no point continuing to add pieces to a partial solution if there's already a full solution with lower cost. In this case, you can abandon (or "prune", or "fathom") further processing of this partial solution.

Many problems have the latter property, making B & B a widely applicable algorithm technique.

The process of searching for solutions can be represented by a search tree, where the root node represents the starting point where no decisions have been made, and each edge leading from a node represents a decision about something to be included in a partial solution. Each node is a partial solution comprising the decisions made (edges) from the root to that node.

Example: if we want to solve a Sudoku puzzle, the root node would represent the board with just the originally supplied numbers filled in; there might be 9 edges from this root, each representing the decision to assign a number 1-9 to the top-left cell. Each of those 9 partial solution nodes could have 8 branches, representing the valid assignments to the cell at position (1, 2), and so on. Usually, each edge represents a recursion step in a program.

With B & B, in the best case a good solution is found early, meaning that unpromising areas of the search tree can be pruned near the root; but in the worst case, the entire tree of valid solutions will be generated. For this reason B & B is usually only used to solve problems for which no faster algorithm is known (such as NP-hard problems).

Answer 2

This link provides a graphical representation of concepts related to B & B.

This link provides an explanation of the algorithm and sample C# code in a downloadable zip file.

Hope this helps.

Answer 3

Fantastic answer @j_random_hacker !!!!

See pg 439 (example 18.2) in Papadimitriou and Steiglitz, Combinatorial Optimization.

This book is a classic, and it discusses your exact problem.

Answer 4

There are a lot of references about branch and bound algorithms in the web.

here you can find some theoretical explanation.

whereas the code in C# is here