Could anybody please explain what the difference between "bounding" and "pruning" in branch and bound algorithms is?
I'd also appreciate references (preferably books), where this distinction is made clear.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
In branch and bound algorithms, you essentially partition the original problem to be solved in a number of subproblems whose union is equivalent to the original problem you started with. The process of deriving new subproblems is called branching and leads to the so-called branch decision tree. Now, when you need to solve a subproblem, you can either determine its optimal solution, show that the subproblem is infeasible (so that you can discard it), or you can show that the subproblem solution is no better than the best known solution for the original problem. If you are not able to solve a subproblem, you branch again, partitioning it into sub-subproblems. Now, for each subproblem you can derive a lower bound for its solution and, if the lower bound is greater than or equal to the best known solution for the original problem, you can discard the subproblem since the best solution you can obtain for the subproblem is certainly worst with regard to the feasible solution of the original problem. In order to get a lower bound you must relax the problem. The relaxation may be continuous, lagrangian etc.
Therefore, the word bound in branch and bound refers to the process of determining lower bounds for subproblems. Pruning refers instead to the process of discarding subtrees in the branch decision tree rooted at subproblems whose solution is impossible or worst with regard to the feasible solution of the original problem.
As I understand it pruning is used in contraint programming problems where you are interested in finding a feasible solution as opposed to bounding where you are interested in an optimal solution, i.e. some maximum or minimum of an object function.
Take for example the 8-Queens puzzle, you branch by setting the first queen thereby decomposing the original problem into subproblems, since you are given a set of constraint the placing of the queen eliminates a number of solutions that have become infeasible (you are no longer able to place any other queens on the same row or diagonals) thereby reducing the search space.
As Massimo Cafaro explained above bounding is used to reduce the search space by providing an upper or lower bound. If however you are trying to find a feasible solution to a problem you reduce the search space by propagating the constraints through branching, if you exhaust the search space without finding a feasible solution you can backtrack and try a different configuration.
I hope I haven't confused anyone with this explanation and I do not contradict the above answer, however I think the answer aimed at the difference between pruning and bounding qua ways of reducing the search space of a given problem.
Both, branch and bound and pruning, are techniques used to reduce the number of possible solutions one has to examine when a search tree is there.
Pruning is the act of removing whole branches from the tree that cannot fulfill constraints. Problems, where solutions might apply pruning are:
Branch and bound is used to find optimal solutions. You also remove whole branches in branch and bound.
When you have found a solution, this solution has a value. Let's say you're interested in maximinzing that value. This means, as soon as you have found a solution of value $X$, you can remove all branches that cannot get a higher value than $X$. So you have a lower bound for the solution and you can prune all branches that do not fulfill this constraint.
Problems, where solutions might use branch and bound are: