This week I made a pretty cool achievement for the paper on the wall that says that I am an applied mathematician. This week, I developed a branch and bound to solve a mixed integer linear problem.

Yeah… so?

Well, hipothetical reader, if you asked me that, I would say that you are not familiar with the power of integer programming. This kind of technique is pretty useful in the industry, in an area called operational research.

To make it simple, it is intended to help the user make better decisions. In other words, it is inside the prescription area inside artificial intelligence (more on this later!).

Ok… tell me more… (I think)

Let’s think of an example. Let’s say you have to find the best route from point A to point B, and for the sake of the example, you do not want google to track you down, so you cannot use google.maps =].

In this case, integer programming can help you! Why? Because you have to make the decisions of where to turn and when.

Ok, the problem passed the first test. The second test is a lot more techinical. You have to be able to model this problem only with linear equations. Putting aside what is the modelling per se, you might be wondering: “Why must it be linear? Nothing in the world follows a linear curve!”. To which my answer would be: “Correct, hypothetical reader! But you gain something pretty cool by forcing it to be linear. The solution you find is guaranteed to be optimal! In the worst case, I can tell you how better the solution could be, if not optimal!”

And now, I will give you some time to think about this. I am telling you there is an algorithm that with few conditions (one might be hard one), you can have the best kind o quality measure one can think of. The final solution is n percent worse than the best one.

Ok… I’m kind of sold. But what does Branch and Bound have to do with this?

Well, branch and bound is the go to algorithm framework solvers use to find this measure of quality I mentioned earlier. And I made one in clojure! I had to solve a small problem and I could not find a decent package similar to pulp in python (which is very sad, if I may say so).

Nice, but I don’t need to find a route…

Glad you mentioned this! That’s the beauty of it. Branch and Bound is a framework in which, if you can mathematically model the problem, you can solve a bunch of kind of problems:

• Find the best location to build a station (fire fighters, restaurants, telecomunication towers, etc…)
• Find the best way to load a truck (or any container for this matter).
• Best way to plan your production

and others. Here you can find a bunch of applications! =]