Divide and Conquer to optimality!

optimization algorithm mip code

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:

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

/comments ~lucasemmoreira/ Divide and Conquer to optimality!

Pomodoro with shell script

code shell-script life

By now, you must be asking yourself: “Oh my god, all you know is janet/functional programming?!”, to which my answer would be a resounding “Yes!”.

However, today I decided to step a little bit outside my comfort zone and make a little script to help me use pomodoro for productivity.

Like you, hypothetical reader, I use dwm with dmenu. With these you can easily create a pomodoro executable to work for you. I say easily because I have no experience with shell script and I made it happen.

Enjoy =]

/comments ~lucasemmoreira/ Pomodoro with shell script

Moving averages beatifully

janet code math

So this is another post on the janet journey. My goal here was to create a simple moving average function in janet (maybe just as a functional programming lover).

The code

I created a repo named numja that I intend to put all mathy stuff there. And moving average fits that category.

The second step was to create a small script that would run with the new “lib”.

The result

Simple as the proposition is, simple the code and simple the result. I used the “lib”, and plotted with gnuplot and voila!

/comments ~lucasemmoreira/ Moving averages beatifully

Janet? Janet!

janet game-of-life code

Do you like C but changed because you were tired of the low productivity, the annoying syntax and - oh my god! - Segmentation fault? Holy shit! Me too!

But then, a couple of years ago, a friend of mine showed me Janet. And I was from the get go hooked! It took me a while to create something in it, now I have something to show.

Why Janet?

Come on… google it

What have I done with it?

Well, I have this pet project that it is to create a Janet wrapper for ncurses. But that will deserve a post on its own. For now, I will show a game of life using the prototype version of the janet-ncurses.

  1. I created a repo for it:
  2. It is very simple to use it. The big bang file is the initial state of it. Play with it!
  3. Now you can run with janet, if you have installed it, make

/comments ~lucasemmoreira/ Janet? Janet!