Technical Articles
ILOG CPLEX 11: Performance, Productivity, and Usability
like nothing before
Thomas Dong, Director, Product Management and Product Marketing, ILOG, Inc.
ILOG CPLEX 11 delivers breakthrough performance gains for mixed integer programming (MIP) models along with enhanced parallel MIP optimization and innovative usability features.
Breakthrough MIP Performance
ILOG CPLEX 11 promises significant performance improvements for MIP models with linear objective functions. The performance improvements can be attributed to the two search strategies available for MIPs. CPLEX 11 introduces dynamic search, which is ILOG’s latest twist on the branch-and-cut algorithm. Dynamic search is built around the same concepts of branching, nodes and cuts but is innovative in its integration and sequencing of them. CPLEX 11 also retains its conventional branch-and-cut algorithm but with advancements in branching, cuts and heuristics. During a MIP optimization, CPLEX is able to select the more efficient search strategy based on the characteristics of the model. For models solved in less than one minute, CPLEX 11 improves the time to optimality by 15% on average. For models solved in the range of one minute to one hour, CPLEX 11 solves them on average three times faster. For models requiring more than one hour to solve, the speedup is on average a factor of ten. Performance improvements of this magnitude are unprecedented and underscore the widespread usage of CPLEX.
Enhanced Parallel MIP
The ongoing shift in computing architecture to multi-core machines means that parallel computing is no longer exclusive to high-end users but is quickly becoming accessible to all. To broaden the appeal of parallel computing, the new release extends ILOG CPLEX’s parallel optimization capabilities. In particular, CPLEX 11 extends the functionality of the parallel MIP optimizer to include two modes of operation. New in this release, deterministic mode provides parallel MIP optimization in which repeated runs of the same model with the same parameter settings on the same machine reproduce the same solution path and the same solution vector. A newly implemented search algorithm exploits parallelism while solving nodes of the branch-and-cut tree but produces an invariant solution path. The result is that CPLEX 11 behaves on multi-core machines in a similar manner as on a single-core machine but often faster! Opportunistic mode, introduced in a previous release, takes full advantage of parallelism; the search algorithm performs less synchronization between threads and allows random tie breaking, which may result in a different solution path and solution vector but potentially faster performance. The bottom line is that parallel MIP optimization can now be an option for a broader set of users, both those who need repeatable runs and those who want to leverage the power of their multi-core machine.
Multiple MIP Solutions
ILOG CPLEX 11 introduces the solution pool feature, which enables users to consider multiple solutions to a MIP model. In practice, a single solution, even an optimal solution, is not always sufficient because not every aspect of a problem can be perfectly captured in a MIP model. For example, some constraints may be difficult to formulate efficiently as linear expressions, the objective may be difficult to quantify exactly or an end user may have subjective preferences on solutions. In such cases, CPLEX can collect all (optimal) solutions or solutions that satisfy specific criteria; then decision makers can select from among the solutions the one that best fits their application. For example, in a production planning application, a user could request five solutions, all within 2% of optimality and all with no more than $2.2M in variable production costs but each with differing utilization of the production facilities.
CPLEX provides two methods for filling the solution pool. One method is to invoke the MIP optimizer, which now automatically adds incumbent solutions to the solution pool. The other method is to invoke the new populate procedure, either following or in place of the MIP optimization, to generate alternative solutions. Generating multiple solutions requires additional computation time, and in general the computation time increases with the desired number of solutions. The solution pool intensity parameter controls the trade-off between the amount of time or memory consumed and the number of solutions generated, with increasing values of the parameter invoking increasing effort to generate larger numbers of solutions. With the default setting, the performance of MIP optimization is not affected but CPLEX will generate only a small number of solutions; with the most aggressive setting, CPLEX will generate all of the solutions to the model but MIP optimization is likely to take a long time. Parameters are available to limit both the number of solutions generated and the number of solutions stored in the pool.
CPLEX offers users a number of ways to control the characteristics of the generated solutions. Solution pool parameters allow for solutions to be screened according to an absolute and/or relative tolerance on the objective in reference to the objective of the incumbent. For an absolute tolerance, a user might specify that the objectives of the solutions stored in the pool must be within 1000 units of the objective of the incumbent. For a relative tolerance, a user might specify that the objective must be within 2% of the objective of the incumbent. If the user sets both an absolute gap and a relative gap, then a solution is accepted into the pool only if it is valid with respect to both tolerances.
Solution pool filters offer more control over the properties of the solutions generated and stored in the solution pool. In general, these filters offer the user a mechanism for exploring the effects of subjective preferences on the solution space without enforcing the preferences as constraints in the model. A diversity filter screens solutions based on their difference as compared to a reference solution. That is, a diversity filter allows the user to direct CPLEX to generate solutions that are similar to or different from a set of reference values specified for the binary variables in the model. For example, in the production planning example, the decision maker might want to collect solutions in which the assignment of products to production facilities differs by at least two assignments relative to an incumbent solution. A range filter screens solutions based on their validity with respect to a linear constraint. That is, a range filter allows the user to generate solutions that satisfy a new constraint, specified as a linear expression within a range. Consider again the production planning example. A range filter could be used to specify the criterion that solutions must have no more than $2.2M in variable production costs.
Performance Tuning
The default settings of ILOG CPLEX are intended to provide good performance for a majority of models without user involvement but some models will benefit from parameter tuning. CPLEX 11 introduces a utility to help users improve the performance of their optimization applications. The performance tuning tool analyzes one model or a group of models to identify parameter settings that yield better performance than default settings. Tuning can be applied to models that are solved to optimality or to earlier stopping criteria.
The basic idea of the utility is that CPLEX tries different parameters settings based on the outcome of the initial and subsequent model runs. In the case of a single model, the tool seeks to minimize solution time; in the case of a set of models, the tool seeks either to minimize mean computation time (across the set of models) or to minimize the maximum computation time.
The tuning sessions can be customized in various ways. Users can specify an overall amount of time for tuning, which can be spent on a single tuning session or multiple sessions. A separate time limit can be set for each of the individual sessions. Generally speaking, the tuning tool considers all parameters as available for tuning. However, users optionally can supply a list of parameters (and their associated value) to be excluded from tuning. For a single model, CPLEX offers the option of perturbing the model and re-tuning; the idea is that by permuting rows and columns and re-evaluating the tool, the recommended parameter settings may be most robust to data changes.
Informational Callbacks
ILOG CPLEX callbacks allow user-written functions to be called during optimization. ILOG CPLEX 11 introduces a new type of callbacks, informational callbacks. The advantage of informational callbacks is that applications can access information about the ongoing optimization while still getting the full benefits from dynamic search. Informational callbacks also are compatible with both modes of parallel MIP optimization. The other types of callbacks, query callbacks and control callbacks, are not compatible with dynamic search nor with deterministic parallel MIP optimization; users should replace existing callbacks with informational callbacks to realize the full potential of the performance improvements.
MIQCP Algorithm
ILOG CPLEX 11 offers a new algorithm for the solution of mixed integer quadratically constrained programming problems or MIQCPs. In particular, CPLEX now provides two options for the type of relaxation solved at each node of the branch-and-cut tree. CPLEX can solve an LP node relaxation, which is new in this release, or a QCP node relaxation, which was introduced in a previous release. A new parameter allows the user to specify the strategy; at the default setting, CPLEX automatically selects a strategy based on characteristics of the problem.
For more information on ILOG CPLEX, visit http://cplex.ilog.com.
