Wednesday, July 3, 2013

CPLEX Remote Object

A very simple way to use CPLEX in an application is to create a CPLEX object, load a model from a file, and solve the problem. This could look like the following (in C++, no error handling)

    
#include <ilcplex/ilocplex.h>

void load_solve(const std::string& modelName) {
    IloEnv   env;
    IloCplex cplex(env);
    IloModel model(env);

    cplex.importModel(model, modelName.c_str());
    cplex.extract(model);
    cplex.solve();

    env.out() << "Solution value  = " 
              << cplex.getObjValue() 
              << std::endl;
    env.end();
}

int main() {
   load_solve("noswot.mps");
   return 0;
}

When that is all you need, you're good. But some challenging problems demand specific algorithms that CPLEX doesn't provide (yet!) and/or would benefit from the power of multiple machines... An example could be that you need to use a Benders decomposition for your very large problem, or you came up with a problem-specific algorithm that uses big LPs or MIPs as sub-problems.  CPLEX includes APIs in multiple languages (currently : C, C++, Java, Python, C# and VB), and using any of these solves the first part of the issue.  But what about the 'using multiple computers' part?  You probably don't want to invest much time into writing a framework to enable distributed computing. So we did it for you!

CPLEX Optimizers 12.5.1, the Mathematical Programming engine in the latest version of IBM CPLEX Optimization Studio, features what we called the CPLEX Remote Object. With only additional parameters given to the first CPLEX call, you turn this CPLEX object into a 'remote' object that does its computations on another machine.

This feature was introduced in version 12.5 for the C API, and we just added the C++ and Java APIs. Let's see how to use this with the example above:

    
#include <ilcplex/ilocplex.h>

void load_solve(const std::string& modelName) {
    IloEnv   env;
    const char* remote = "-address=the_server:12345";
    IloCplex cplex(env, "tcpiptransport", 1, &remote);
    IloModel model(env);

    cplex.importModel(model, modelName.c_str());
    cplex.extract(model);
    cplex.solve();

    env.out() << "Solution value  = " 
              << cplex.getObjValue() 
              << std::endl;
    env.end();
}

int main() {
   load_solve("noswot.mps");
   return 0;
}


Note that the only difference with a purely 'local' computation is in the creation of the CPLEX object. In the case above, your program will try to connect to a distant machine and run CPLEX there. The data will still be read from the same (local) file, but they will be serialized and sent to the remote object. The latter will execute the 'solve' call, and when instructed to with the last call, will return you the objective value of the optimal solution.

This needs some preparation work on the distant machine, of course, and this depends on the protocol you want to use:
- TCP/IP : fire up the CPLEX interactive with some options to listen on a specific port;
- Process : the distant computer must accept SSH sessions from which the CPLEX interactive is in the path;
- MPI : in that case, both machines (local and distant) must belong to the MPI cluster.

In addition to offloading your computations to a distant machine, the CPLEX Remote Object allows you to create fully distributed algorithms, where a 'master' connects to several 'workers' and gives different computations to each.  The CPLEX distribution includes two such examples: a Benders decomposition, and a distributed concurrent MIP solver... You will find more information about the Remote Object in Roland Wunderling's presentation. And you can browse the online documentation on the topic.

By the way, this new 12.5.1 version has a number of features, including a 43% performance improvement in the time to solve difficult MIP problems...  See Jean-Fran├žois Puget's blog post for more on this topic.

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'...