JeanFrancoisPuget 2700028FGP Visits (3240)
We are about to have a new CPLEX release, namely IBM ILOG CPLEX Optimization Studio 12.5.1. We plan for electronic availability this week.
The main focus for this release was to improve performance across the board, and particularly for Mixed Integer Programming (MIP) and Mixed Integer Quadratic Programming (MIQP and MIQCP). We also improved numerical accuracy and fixed few bugs.
For MIP we get the following geometric average speed up compared to the 12.5 release of November 2012:
Note that the above are average speed up, and may not be indicative of how this new release will perform on a particular problem. Some customers will see larger speed up, some will see lower speedup, or no speed up at all. The only way to know for sure is to try the new release!
Benchmarking MIP solvers isn't a trivial task, and it is quite easy to make statistical errors. I'll blog soon about how to avoid major pitfalls. Let me just say here that the above speed ups are measured on a large set of problems (more than 4,000) representative of what our customers need to solve.
Let me also stress that solving a problem means finding the best possible solution (optimal) and prove it is the best one. This has been the key performance measure for mathematical programming solvers for several decades.
This said, we see more and more customers that are just interested by getting good solutions quickly and do not worry much about the optimality proof. They are still interested in the gap, ie knowing how far they are form a theoretical optimum, but what they value most is the feasible solutions they can get in a limited amount of time. Measuring this in a non ambiguous way on a large set of models is tricky and we used a proxy for it, namely the time to the first feasible solution.
Release 12.5.1 provides significant improvements on average for the time to first feasible solution.
MIP improvements come from progress across the board, cuts, presolve, heuristics. We know people are eager to know more about it, and we (the CPLEX team) will publish more information in the coming year.
Here is the performance graph obtained by looking at how fast the new release is compared to previous versions since CPLEX 6.5. The speedup is measured by actually running all those versions on the same hardware. They are not obtained by multiplying version to version speedup as this yields wrong numbers if the comparison wasn't done on the same problem set. The bars indicate the number of problems that cannot be solved in 10,000 seconds. It does not mean that CPLEX does not find any feasible solution for these problems. It means that it cannot prove optimality within the time limit.
Here is the same information by year. Given that the 2013 entry is for this month, we have 6 more months left for potential additional speedup. With this in mind we see that the rate of improvement is quite steady, and that the trend is very encouraging.
Mixed Integer quadratic programming performance improvements come mainly from a simple linearization of products of binary variables. The product of two binary variables xy can be replaced by a new binary variable z such that
x - z >= 0
y - z >= 0
x + y - z <= 1
In particular, if all variables are binary then all quadratic terms can be replaced by linear constraints similar to the above.
It means that all MIQP and MIQCP with only binary variables are automatically transformed into MIP, This results in significant speed ups on average.