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.
6
$\begingroup$
$\endgroup$
asked Oct 13 '12 at 10:20
-
1$\begingroup$ Books that discuss the topic B&B (that I am familiar with) are "Algorithmics for Hard problems" by Hromkovic and "Python Algorithms" by Hetland. They are at opposite difficulty levels. This is a good online pdf about B&B: imada.sdu.dk/~jbj/heuristikker/TSPtext.pdf $\endgroup$ – The Unfun Cat Oct 13 '12 at 10:54
-
1$\begingroup$ See here for an explanation of branch & bound which should cover your question. $\endgroup$ – Raphael♦ Oct 14 '12 at 9:28
10
$\begingroup$
$\endgroup$
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.
-
2$\begingroup$ Pruning is a technique needed to perform "branch and bound"-algorithms. Pruning is done if even the best solution in a subtree is positively certain to be worse than the one you already have. $\endgroup$ – The Unfun Cat Oct 13 '12 at 11:59
-
2$\begingroup$ Just to summarize: Both refer to a part of the same process where you determine that a subtree is irrelevant (bound it) and then remove it (prune). Most of the time I guess people use them interchangeably to refer to the whole step. $\endgroup$ – Bitwise Oct 14 '12 at 16:46
3
$\begingroup$
$\endgroup$
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.
3
$\begingroup$
$\endgroup$
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:
- Eight queens puzzle
- Finding the optimal strategy in win-or-lose games (Alpha–beta pruning):
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:
answered Mar 12 '14 at 20:25
-
$\begingroup$ Are you sure? It seems like branch-and-bound does use pruning, to prune out entire subtrees that the bounding stage have proved cannot be better than the best you've seen so far. It seems like a more detailed name for "branch-and-bound" might be "branch, bound, and prune", and a more detailed name for what you are calling pruning might be "branch and prune". In any case, it seems like they both involve pruning. $\endgroup$ – D.W.♦ Mar 12 '14 at 21:22
-
$\begingroup$ Agreed with D.W: Branch & Bound involves pruning. Bounding is the means of determining the bounds, while pruning is the decision not to explore certain subtrees. Constraint satisfaction is just a special case where you only have costs 0 and 1, so in fact even there you need bounding as well to figure out whether a subtree is solvable or not, without exploring the subtree. Your distinction is in fact pretty arbitrary. "Is used to X" is not a definition. In fact I think it is summed up quite nicely on Wikipedia $\endgroup$ – Niklas B. Mar 12 '14 at 21:33
-
$\begingroup$ You still need bounding in constraint satisfaction to figure out when you can prune. I guess you just don't call it bounding. You usually just call the whole process "backtracking" (not pruning), but the concept is the same $\endgroup$ – Niklas B. Mar 13 '14 at 14:26
