Technical Articles

Harness the Power of Your Multi-Core Machine with Parallel CPLEX

Thomas Dong, Director, Product Management and Product Marketing, ILOG, Inc.

Do you have a dual core, quad core, or multi-CPU computer? Are you solving difficult mixed integer programming (MIP) problems that take many nodes to solve? If so, consider the ILOG Parallel CPLEX MIP Optimizer. The Parallel CPLEX MIP Optimizer takes advantage of multiple CPUs or cores to solve such problems faster.

The Parallel CPLEX MIP Optimizer was first introduced more than a decade ago when parallel optimization required expensive special hardware. Today, with the ongoing shift in computing architecture to multi-core machines, parallel computing is no longer exclusive to the high-end but is quickly becoming accessible to a broad set of users.

For some users, however, access to hardware has not been the primary deterrent to parallel optimization; instead the inherent non-determinism associated with traditional implementations of parallel MIP optimization precluded its use. The latest release of the Parallel CPLEX MIP Optimizer offers a solution for those users whose applications demand repeatable solution paths.

The Parallel CPLEX MIP Optimizer exploits parallelism while solving nodes of the branch-and-cut tree. In CPLEX’s original implementation of parallel MIP optimization, now called opportunistic parallel mode, the individual node subproblems are distributed to the available processors to be solved in parallel. While the solution path of an individual subproblem will not change, the solution time may vary slightly from run to run. As a result of these variations, nodes may be processed in a different order, leading to different solution paths and solution times. Although the variations in solution paths can bring improvements as often as degradations, variation of any kind may be problematic for some application environments. As an alternative, the latest release of the Parallel CPLEX MIP Optimizer offers deterministic parallel mode, a mode of operation that guarantees an invariant solution path. In a newly implemented algorithm, nodes or subtrees of the branch-and-cut tree are again distributed to the available processors but the work of the threads is regularly interrupted for synchronization. The result is parallel 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, thus yielding more consistent solution times.

Because the performance benefit realized from parallel optimization depends both on the characteristics of the particular problem and the characteristics of the computing environment, reporting benchmark numbers that are relevant for any individual problem is difficult. However, for a large suite of difficult MIP problems representing a wide range of industries and applications, ILOG’s internal tests with CPLEX 11 using two threads show that 70% of the problems could benefit from Parallel CPLEX, with a median speedup of 1.7 and with 30% solving at least twice as fast. Even larger speedups were achieved using four threads.

The Parallel CPLEX MIP Optimizer makes it easy to use parallel optimization to solve your most difficult MIP problems, whether you need repeatable runs or you want to leverage the full power of your multi-core or multi-CPU machine.

Send us your MIP problem and find out what Parallel CPLEX can do for you!