Going for hiking and having difficulty packing your rucksack? Optimizaton and Search: The branch and bound algorithm

A branch and bound is an algorithm paradigm. It basically relies on a combinatorial approach and is hence used for combinatorial optimization like the knapsack problem.

Have you ever watered and maintained your garden? Going around removing weeds around trees and removing unwanted branches growing from your plants to keep them in the best possible symmetry, so that your neighbor envies your garden for the perfect shape it's always in. Removing over-ripe fruits so that they don't spoil the other around them. Cutting and pruning at each step so that you don't have to deal with a huge jungle later on.

Well, this is the basic principle for B&B. Below is a more detailed explanation.

It usually of the form of a decision tree where each decision is represented by an edge. The leaves of this tree is the set of all possible solutions. To find the most optimized solution(i.e. one of the leaves) the following is the basis of evaluation.

The intuition is that you start from the root and calculate an upper bound if the problem asks the function to be maximized (or lower bound for function minimization in case of TSP where distance is to be minimized) for a function you want to optimize. This bound describes the best you can get from the sub-tree below the node. It is to be kept in mind that this bound is re-calculated every time a decision is made in the tree. This bound describes the most optimistic solution you can find in one of the leaves of the sub-tree rooted at this particular node.

Make a series of decisions and find the first solution. Now this is your benchmark. Compare this solution obtained with the optimized evaluation of the function at each level (i.e. after every decision). As the root of a sub-tree bounds the best you can achieve from any of the leaves of that sub-tree; if the root of the sub-tree in question has a higher optimized evaluation then you can search that sub-tree in hope for a better solution you already have else discard the whole sub-tree below (called pruning).

If a better solution is found it's updated as the benchmark.

Keep searching the main tree for solutions better than what you have (benchmark) and prune the sub-trees which have a lower optimized evaluation than the benchmark.

Pruning reduces the search space by an amount depending on where the pruning of the tree occurs. Generally, it helps in reducing it by a large factor.

The above is an instance of the knapsack (max weight is 16) using Branch and Bound. The weight and the value of the item is enlisted on the left.

Each node has current value, space occupied and optimistic evaluation of the value of its sub-tree. 

1. The root shows that currently no items have been selected and the best one can do is 115$.(or less)

2. A decision is made to accept the Item 1.

3. If Item 1 is accepted then we go to left of root else right of root.

4. Going left the value of the knapsack is increased and the weight is also updated. An optimistic evaluation is calculated for the results under this node.(i.e. all possible ways of selecting remaining items after selecting Item 1)

5. Going right the value of the knapsack and the weight is unchanged (since nothing was chosen). An optimistic evaluation is calculated for the results under this node.(i.e. results with all possible ways of selecting remaining items after discarding Item 1)

6. If a node has optimistic evaluation less than the best we have found then the sub-tree is discarded. If a node occurs such that the weight surpasses the max allowed weight by the knapsack then again the sub-tree under the node is discarded.

The first solution is found and set as the benchmark and the above steps are repeated until the whole search space has been exhausted.

This is the basic idea of Branch and Bound.

Algorithms and Computer Science

Why is computer science a science?

What is the difference between say Physics or Biology and Computer Science? Is there a difference at all?

Well for starters science constitutes of experimentation which makes if fundamentally difference from other subjects that may seem similar at first glance. The field of computer science is a machine science. It deals with a particular type of machine that we colloquially refer to as a PC or a personal computer. So why don't we have something like a tube-light science or a pressure cooker science?

That is something debatable but computers unlike a tube-light or a pressure cooker doesn't inherently have a singular purpose such as glowing or boiling your favourite veggies. If you can encode your thoughts in a precise and particular manner, the personal computer can function based on that. These may vary from solving problems that occur while studying particle physics and trying to make sense of the humongous amount of variegated data or as inconsequential as calculating the amount you spent on groceries at the market.

Alan Turing, the father of theoretical computer science wrote a scientific paper in which he described "computers" as people (mostly women at that time, primarily due to their patience while performing arduous calculations) who did math on pen and paper according to the whims of a set of sequential instructions also known as an algorithm.

Let's go back to the pressure cooker. 

Could there be a microwave oven science, since we already have one that caters to a pressure cooker? What cooks faster in a pressure cooker: a chicken or some potatoes? Potatoes or rice? Rice or wood? Wood or Iron? That escalated quickly.

On closer observation, there seems to be some sort of classification. Things that cook slow, other food items that cook quicker and some others, even quicker. And then there's this class of items that are so stubborn that they won't boil in a pressure cooker, like a piece of metal. Every science begins with classification and so does the one that deals with theoretical computer science.

Absurd as it may sound, in this context, we are dealing with the contents or what we can actually come up with, rather than the tool itself. We are worried about the chicken or the rice or perhaps the potatoes in the cooker rather than the humble pressure cooker itself. Similarly theoretical computer science at it's heart doesn't believe in discriminating based on the tool we use, whether it's a microwave oven or an old school pressure cooker, all we are worried about is getting nice boiled potatoes in the end. It doesn't really matter whether you have a super computer of this generation or a quantum technology powered device of the next era. This is what is computational complexity.

Things cooking at various speeds can be compared analogously to the various complexity classes in computer science, that instead of rating food items classify algorithms on their efficiency for easy comparison and deciding what maybe difficult for a computer to solve.

Difficulty is relative. Someone may find talking to a girl really difficult while another one may deem waking up early in the morning a difficult task. Many may also find it laborious to prove the Pigeon-hole principle. Computer science calls problems difficult that require at least exponential number of steps in the size of an input to an algorithm. But a database scientist may treat anything worse than a logN or a linear algorithm as inefficient. Depending on the context the definition of hardness may vary. The algorithms are compared in terms of the number of instructions required, space occupied (as a scratchpad), etc. These metrics are technology independent and that's where the universality lies. You'd compare them in the next century as you would in this. Doesn't matter what kind of specification the system has. The tool is just a means, it's the method that we bother about.

While mathematics has this puzzle kind of perspective to it. If you have solved a jigsaw puzzle or say a Rubik's cube, which you most certainly have, for the first time it may seem more of a challenge. But once you know how a jigsaw puzzle works and understand the concept behind it, you can solve any puzzle with the same technique. If you know how to computer 33+12, you can surely compute 132144+39427438 with little difficulty. Once a mathematical problem is solved, it is like you've become aware of the great magician's secret. Any local fair you visit and you see a person performing the trick you'll be aware of how it's done, irrespective of whether it's happening.

A solution for the travelling salesman problem for the cities in Germany.

On the other hand, computer science deals with skewing the problem. Let's say that now you take a 4x4 Rubik's cube to solve. What happens to your step-wise procedure? Does it work as expected or fails miserably? What happens to the number of steps when you consider a cube of an arbitrary size NxN? How much space does the computer need as a scratch pad to find a conclusive solution? Here, as soon as you fish out an algorithm it is then that you have even more questions to answer than you had to begin with in the first place.

P.S.: I attended a talk on algorithms and this is what it was all about. Really simple stuff but made a lot of sense. I thought I'd share it with my readers. :)