Decision Optimization

A new parameter emphasis mip 5 allows to find solutions 1.8x faster with CPLEX 20.1.



CPLEX has been developed for 30+ years with one performance objective: be as fast as possible to prove the optimality of the best solution that it can find for the model.  In other words, the goal is not really to find the best solution quickly, but to prove its optimality.  Of course, in the course of proving the optimality, CPLEX will necessarily find an optimal solution.  But it doesn't really matter whether CPLEX finds this solution right from start, or only at the very end of the process.  Only the total time matters.

Yet, for half of our customers, the primary stopping criterion when running CPLEX is a time limit.  In other words, a very large part of the production usage of CPLEX is about getting the best possible solution in a given time, and is not about proving optimality, or reaching a known optimality gap. It doesn’t mean that these users are not interested in optimality! Of course, it would be better is CPLEX were able to solve their instances.  But maybe optimality is unreachable with the current state of the art.  Or maybe it’s not worth waiting for it.  The point is that they decided against spending the time to reach optimality.

The issue is that the default CPLEX behaviour is tailored to improve the time to optimality.  So there are quite a number of choices done while programming CPLEX, or at runtime, that are geared towards this criterion.  Examples are the effort on creating cuts at the root node, the strategy to choose the next open node to explore, or the time spent in heuristics.  All of these could, and should, be done differently if the goal is not any more time to optimality.

That’s why we created a new mode for CPLEX, tailored towards better solutions earlier. In the CPLEX Interactive, you can use

set emphasis mip 5

to choose this new mode.  In Java, you could write something like

cplex.setParam(IloCplex.Param.Emphasis.MIP, 5);

Although this is not all of it, you can think of “emphasis mip 5” as “heuristics on steroids”. On models that can actually be solved to optimality, this will almost certainly increase the time to optimality.  On the other hand, it will indeed find better solutions earlier.

We can imagine several ways to measure the ability of CPLEX to find good solutions early. One is the speedup.  The intuition behind it is “how much slower do I need to make the fastest solver to match the other one”.  So it's mostly based on the value of the last solution found. Other measures, such as the Primal Integral introduced by Timo Berthold in 2013. This is a measure of the surface below the curve that shows the progress of the objective across time (for a minimisation problem).  It takes into account all the solutions found, but the results are less intuitive, and I will only present speedup results below.

On the left-most column are displayed the results for default settings.  As this is the reference, these columns get a speedup of 1. Next are emphasis mip 1 and emphasis mip 4.  These two settings have been available for quite some time: around 2000 for the former, and 2003 for the latter.  Another way to increase the probability to find good solutions early is to use polishing as soon as the root node is done. This can be done via `set mip polishafter nodes 0`.  All of these have an effect on the time it takes to get good solutions.  But, with a speedup of 0.55 for a time limit of 30 minutes, the newly introduced emphasis mip 5 is clearly more efficient.  A speedup of 0.55 means that, in this mode, it takes only 55% of the time it takes CPLEX on default to reach the same value for the solution. In other words, on average, CPLEX is 1.8x faster in this mode than in the default mode.

We hope you will find this mode useful.

Thanks for using CPLEX!