The ILOG CPLEX Parallel MIP Optimizer delivers significant increases in speed on a wide variety of models, particularly on difficult ones that solve a large number of nodes in the branch & cut search tree. There are several different opportunities for applying multiple processors to the solution of a MIP problem. These topics highlight those opportunities:

After those highlights of opportunities to apply multiprocessing, the following sections tell you more about managing parallel MIP optimization:

Increase the Global Thread Parameter

The most straightforward way to invoke parallelism is by setting the global thread parameter, Threads, to a value greater than 1 to indicate the desired degree of parallelism. If the other parameters remain set to their default values, the result is that nodes in the branch & cut tree will be processed in parallel; that is, each node is solved in its entirety on one of the available processors, independently of the work being performed on other processors. In typical cases, the number of nodes waiting for solution quickly becomes greater than the number of threads, creating enough work which can be done in parallel to make speed increases possible. ILOG CPLEX automatically manages the pool of nodes, so that each time a thread finishes one node, it is assigned to solving another.

Branch & Cut Parallel Processing

A contrasting and specialized approach to obtaining speed increases by parallel processing within the branch & cut tree is to:

On models where strong branching is already a beneficial technique, this approach to parallelism can be especially attractive.

Root Relaxation Parallel Processing

In some models, the continuous root relaxation takes significant solution time before parallel branching begins. These models have potential for additional speed increases by running the root relaxation step in parallel. If the root problem is an LP and the Threads parameter is set to a value greater than 1, the concurrent optimizer is invoked by default. This provides a form of parallelism that applies the available threads to multiple optimizers. If the root problem is a QCP, the dual simplex optimizer alone is used.

You can try a different form of parallelism at the root by selecting a specific optimizer with the starting algorithm parameter (RootAlg in Concert, CPX_PARAM_STARTALG in the Callable Library, set mip strategy startalgorithm in the Interactive Optimizer) to select the Barrier optimizer. The parallel threads will all be applied to the barrier algorithm.

Individual Optimizer Parallel Processing

Parallelism in barrier is ordinarily controlled by the global thread count parameter, but this default behavior can be overridden by the individual optimizer thread limit parameter, BarThreads. The degree of parallelism within the branch & cut tree likewise can be controlled by the MIP thread limit MipThreads, which overrides the global thread limit. This capability to set either or both MipThreads and BarThreads permits great flexibility in the use of parallel resources during the solution of a MIP model.

For example, on a model where only a small number of nodes is active at any one time, the benefit of parallel solution of these nodes is limited. If the individual nodes are computationally challenging, then it may be possible to achieve speed increases by leaving the global thread limit at its default of 1 and setting the continuous optimizer thread limit (BarThreads) to a value greater than 1. The global thread limit of 1 will inhibit the parallelism of the branching process, while the explicit thread limit of more than 1 will permit the optimization of each node in parallel.

Nested Parallel Processing

Nested parallelism represents a further way to exploit the flexibility of independent thread parameters. For example, it might be determined from experience in a given family of models that only a modest degree of parallelism is beneficial at the nodes and additional processors do not help speed up the branching. In such a case, better speed increases might be obtained by combining a parallelization of the work that the continuous optimizer does at each node. On an 8-processor computer, you might opt to solve a model by setting the MipThreads limit to 4 instead of its maximum of 8, and the BarThreads limit to 2, thus keeping all 8 processors busy as much of the time as possible, with the four MIP threads each invoking two threads for the barrier optimizer.

If you do decide to try a nested parallel approach, keep in mind the rule of thumb that it is usually better to keep a higher degree of parallelism of the nodes themselves (MipThreads) than of the continuous optimizer (BarThreads); this is in keeping with the general observation that MIP speed increases are on average closer to linear in the number of threads than the speed increases for the continuous optimizers.