Thursday, May 16, 2013

A bit about CPLEX…

I’ve been serving the scientists and software engineers in the CPLEX Optimizer team as their manager for almost two years, now. I consider myself very lucky: this is an extremely dedicated and talented team, working on a great piece of software!

Let me explain what CPLEX is about…

Suppose you have decisions to take and there are many possibilities. It could be about choosing a location for a warehouses and which customers each will serve, deciding when to produce which item, allocating crews to trains or planes, etc. You don’t have the luxury of infinite resources, and you have some constraints to satisfy: all customers must be served, not all machines can produce any item, rest periods must be taken into consideration, etc. And of course all the solutions are not equivalent, and you needs the best possible solution according to some objective function that may refer to costs, revenue, idle times, etc. As you can see, the types of problems that can be modeled in this framework is very large. And, indeed, all industries and sectors use these technologies to improve their efficiency...

The issue is that for anything but toy problems, there are so many possible solutions that you can’t test them all to decide which is the best. Consider for example the problem of ordering a set of 30 tasks. There are so many possible solutions that you would need in the order of 100.000 years to test them all using all CPUs on earth!

Fortunately, there are sophisticated programs that do just that: find the optimal solution for your problem as quickly as possible. IBM has one such product, named ILOG CPLEX Optimization Studio. It features a modeling language (OPL) that allows you to express the problem to solve in an easy way, an IDE to write and run your models, several connectors to access your data (from Excel, DB2 or most other databases) and two computation engines to find the solutions: CPO (Constraint Programming Optimizer) and CPLEX, each dedicated to a particular class of models.

The algorithms included in CPLEX are targeted at solving Mathematical Programming models. They range from Linear Programming (the objective is a linear combination of the variables, and each constraint is an equality or inequality) to Mixed Integer Linear Programming (some of the variables must take integer values – makes the problem much harder to solve), Quadratic Programming (the objective may contain products of two variables) and Quadratically Constrained Programming (the constraints can include quadratic terms). You will find details about these e.g. on Wikipedia.

Most of the team’s work is to improve the performance of these algorithms, or add new ones. Consider for example that CPLEX 12.5, the latest version as of this writing, solves the most difficult MIP problems in our test set more than 190 times faster than version 6.0 (1998) on the same hardware! And the runs are deterministic: on a given platform, for the same data, the program will always run the same way and return the same solution, even if you use a heavily loaded multi-core machine…

As I don't have a technical role anymore, I don't often have much to post about on the 'how' we are doing things. So stay tuned for more about the 'what'...