Do you need a bigger computer to solve this MIP? [primal]

When I have difficult time solving a mixed-integer optimization problem (MIP), one of the most common reflexes is to run the problem on a bigger or faster machine.  However, when solving MIPs, throwing more processor power at a problem will not necessarily result in a better solution. Different models require different resources to solve. Overall, using a computer with fast processor and RAM seems better than aiming for a slower machine with more resources. Throwing more RAM at a problem in which the CPU is the bottleneck will result in zero extra performance. Today’s primal post illustrates this phenomenon with a single example run on different computers. The dual of this post will go more in depth about what you really need to solve a problems faster.

What do you really need?

If I had to summarize the experience I have in working on difficult MIPs, it would be: you don’t necessarily need a big machine, but you need a fast machine. A big machine is a computation server with lots of CPUs (or CPU cores) and lots of RAM. Sometimes, having a big machine helps in direct solving, but it really only shines when you try to do things in parallel such as implementing decomposition or solving multiple models in parallel. A fast machine, on the other hand, has a recent processor with lots of internal cache memory and fast RAM. Its processor is designed to handle long runs at 100% capacity and are properly cooled. One last thing: if you work on a laptop, it is 99% likely that it’s neither a big nor a fast machine. Use it to develop, prototype and test, but leave the big computation job to a workstation or server.

Experiments on a supply chain design model

As you may know, I work in the field of supply chain design. Let’s take an example of a difficult yet solvable model representing the supply chain of a pulp and paper company. I run this model on six different machines for two hours and check the solution quality I obtain as well as the overall amount of work done by CPLEX 12.6. This problem requires about 11 hours on a fast machine to be solved to optimality. The table below show the number of processor cores, processor type, RAM of the computers. If also lists the MIP gap obtained on the machine after 2 hours, the value of the best solution, as well as the nodes explored and the amount of ticks reported by CPLEX. (You can learn a bit about ticks here).  Machines 1 and 2 were bought in 2008 and 2009, respectively, while machine 4 has about 3.5 years of age. Machine 3 is a virtual machine on a 2013 server, M-5 is my laptop and M-6 is a workstation we just bought.

A first observation is that M-5 (a laptop) scores significantly less than the other machines I ran on. It evaluates less nodes and obtains a worse solution. The big machine does not perform better on this model than even the older machines (M-1 and M-2). Machine-6 founds a better solution and does more steps toward closing the gap than any of the other machines.  You might also notice that the older machines also find a solution quite close to the optimum, so even if less work is done, it does not impact much the solution quality for this particular model. This is but one example; other models might provide very different results.

Trackbacks

  1. […] Yesterday’s post explained why I prefer run solver on fast machines over big machines and gave a short example why. In today’s post, I provide some very personal guidelines on how to determine what kind of machine you might need to solve MIPs.  Beware: this post is more based on personal experiences than hard data. […]

  2. […] Yesterday’s post explained why I prefer to run solver on fast machines over big machines and gave a short example why. In today’s post, I provide some very personal guidelines on how to determine what kind of machine you might need to solve MIPs.  Beware: this post is more based on personal experiences than hard data. […]

Speak Your Mind

*