Branch and Bound explanation

Question

I have a test about the branch and bound algorithm. I understand theoretically how this algorithm works but I couldn't find examples that illustrates how this algorithm can be implemented practically.

I found some examples such as this one but I'm still confused about it. I also looked for travelling salesman problem and I couldn't understand it.

What I need is some problems and how can these problems solved by using branch and bound.

Answer 1

Let's apply Branch and Bound to Knapsack, hopefully this will make the concept clear to you.

We have $n$ items, labelled $1$ through to $n$. $v_i$ is the value of the $i$th item, and $w_i$ its weight. We try to fit them in a knapsack that can contain up to $T$ weight in total, and we try to maximize the sum of the values of the item we put in the knapsack.

The ordinary backtrack approach is our basis. We first put $v_1$ in the pack, and then solve the problem for the remaining $n-1$ items with recursion. We then remove $v_1$ from the pack and solve the problem for the remaining $n-1$ items again, and we return the best configuration that we've found.

This backtracking is the 'Branch' part of Branch and Bound. You branch on (in the case of Knapsack) two cases: 'item $i$ is part of the solution' and 'item $i$ is not part of the solution'. You can visualize this as a binary tree, where the left child is one case and the right child is the other case. This tree is the search tree (or search space): its depth is $n$, and it therefore has $O(2^n)$ nodes. The algorithm therefore has a running time exponential in the number of items.

Now we get to the 'Bound' part: we try to find criteria such that we can say 'this configuration never work out, so we might as well not bother computing this'. An example of such a criterion is 'the weight of the items we've already put in the knapsack exceeds $T$': if we've added, say, the first $n/2$ items to the knapsack and it is therefore already full, there's no point trying to put items $n/2+1$ through to $n$ in the knapsack as well, but there's also no point in trying to fit any subset of $n/2+1$ through to $n$ in the knapsack, as it's already full, so we save about $2^{n/2}$ cases. Another example is 'even if I put in all the remaining items, the value of the items I've put in will not exceed the best configuration I've found so far'.

These criteria essentially cut away parts of the search tree: at some node, you say for instance 'the left subtree will not give me a better configuration, because X', so you forget about that subtree and you don't explore it. A subtree of depth $d$ that you cut out this way saves you $O(2^d)$ nodes, which can be quite a bit of a speed increase if you're lucky.

Note that this is called 'Bounding' because it usually involves some kind of lower or upper bound: for the criterion 'even if I put in all the remaining items, the value of the items I've put in will not exceed the best configuration I've found so far', the value of your best configuration so far is a lower bound on the best configuration, so anything that will never make it past this lower bound is doomed to fail.

You can make the 'Bounding' part as complex as you like. For instance, integer programming problems are often solved using relaxations: you relax your program to a linear program, which you can solve in polynomial time, and then you can throw away a lot of cases for your binary variables that will never work out anyway. You then branch on the remaining options.

Note that Branch and Bound usually only gives you a speed increase in practice, but not in theory: it's hard to say exactly how much of the search tree is cut out using your heuristics. This is testified by the number of different heuristics used in practice on such problems. If you're unlucky, the remaining search tree remains huge even with a lot of bounding.

Answer 2

Consider scheduling, the task of assigning jobs with certain durations and deadlines to machines. We assume discrete time. Many such problems are NP(O)-hard.

In particular, this answer will talk about $1 \mid r_i \mid L_\max$, that is we schedule

• on one machine
• problems with release dates and we
• minimise maximum lateness $L_\max$, that is the maximum difference between deadline and completion time over all jobs.

The decision version of this problem is NP-hard; this can be seen by reduction from 3PARTITION.

Interestingly enough, if we allow preemption, that is swapping out active jobs, the problem can be solved in quadratic time by the Earliest Due Date First heuristic (on modified due dates). It is easy to see that the optimal solution of this variant can be no worse than the optimal solution of the original problem.

Now, in order to apply Branch & Bound to this problem we need to fix some parameters:

• We compute lower bounds by allowing preemption and using EDD.
• We branch by fixing every of the unscheduled jobs as next one.
• We go to the child with smalles lower bound first.

You have to do this for every application of B&B.

---

For a concrete example, consider this instance of $1 \mid r_i \mid L_\max$:

$\qquad \displaystyle \begin{array}{c|cccc} i & 1 & 2 & 3 & 4 \\ \hline p_i & 4 & 2 & 6 & 5 \\ r_i & 0 & 1 & 3 & 5 \\ d_i & 8 & 12 & 11 & 10 \end{array}$

with $p_i$ the jobs' processing times, $r_i$ the release dates and $d_i$ the due dates.

Executing B&B as specified above, this happens:

_{This GIF does not loop. Reload it in a new tab to see from the beginning.}
^{[source] [static version]}

Note that out of 41 nodes, only four are visited properly and only for ten are lower bounds computed.