Why is my MILP not finishing

Peole often wonder my it takes several seconds/minutes/hours/days to solve their (claimed small) mixed-integer linear program. They know that integer programming is theoretically intractable, but fail to grasp how quickly exponential complexity can slap you in the face.

Let us take a simple example with a mixed-integer linear program with “just” 1000 binary variables. Surely that should be solved relatively fast also in the worst case? Assume your solver manages to solve 10000 LP relaxations per second which is 600000 per minute or 864000000 LPs per day, or 315 billion LPs per year. Keep counting and after 13.7 billion years (the age of the universe) we will have solved \(4.32\cdot 10^{21}\) LP relaxations in our branch-and-bound tree.

In the worst case, to solve a MILP with 1000 variables, we will have to go through all \(2^{1000}\) possible cases. How large is \(2^{1000}\) compared to \(4.32\cdot 10^{21}\)? Absolutely enormously uncomparably larger. Already \(2^{72}\) is larger than \(4.32\cdot 10^{21}\), i.e., with our solver we might, in the worst case, only manage to solve a problem with 72 binary variables if we are given the age of the universe to finish. For a problem with 1000 variables, the worst-case required time is simply incomprehensible.

In practice, we are lucky when we solve MILPs. We routinely solve problems with thousands of variables, but once in a while, we will (and must) find problems which we simply cannot solve. The only thing we can do then is to try to change some algorithmic options of the solver, or change the model, and cross our fingers.

Oh, by the way, with a 300W processor (i.e. 300 J/s) you’re going to use \(1.3\cdot 10^{20}\) Joules, which roughly speaking is the total world annual energy consumption.