Determinism of Results

ILOG CPLEX 11.0 User's Manual > Advanced Programming Techniques > Parallel Optimizers > Determinism of Results

Determinism of Results

By default, CPLEX will employ parallel algorithms only as long as the optimization remains deterministic. In this context, deterministic means that repeated solving of the same model with the same parameter settings on the same computing platform will follow exactly the same solution path, yielding the same level of performance and the same values in the solution.

The parallel barrier optimizer can not work deterministically because of design considerations. Likewise, by design, the concurrent optimizer cannot work deterministically. (Even though determinism cannot be guaranteed theoretically for parallel barrier or concurrent optimization, these optimizers rarely exhibit behavior that is not deterministic in practice.) Because of this consideration about determinism in their design, and because of its implicit contract to use parallel algorithms deterministically by default, ILOG CPLEX does not invoke these optimizers by default in parallel. Thus, in order to use parallel processors for concurrent optimization or for barrier optimization, you must explicitly set the threads parameter (Threads, CPX_PARAM_THREADS) to a value strictly greater than one. This higher setting implicitly specifies to ILOG CPLEX that the user is willing to accept behavior that may not be deterministic.

In contrast, for mixed integer programming (MIP), two parallel implementations are available in ILOG CPLEX: deterministic and opportunistic. Opportunistic parallel optimization requires less synchronization between threads and thus offers better performance on average. Consequently, during development of an application, you may find deterministic parallelism advantageous for the repeatable, invariant solution path and results, whereas after development, during application deployment, you may prefer opportunistic parallelism for its performance.

To maintain determinism (that is, an implicit contract of repeatable, invariant search path and results), ILOG CPLEX invokes deterministic parallelism by default for MIP optimization, but when the threads parameter (Threads, CPX_PARAM_THREADS) is set to a value strictly greater than one, opportunistic parallel MIP will be invoked. This higher setting implicitly specifies to ILOG CPLEX that the user is willing to accept opportunistic behavior.

In addition to the threads parameter, you can use the parallel mode parameter (ParallelMode, CPX_PARAM_PARALLELMODE) to control the invocation of opportunistic algorithms. With its default setting of 0 (zero), only deterministic algorithms are used, unless the threads parameter is changed to a value strictly greater than one.

To force ILOG CPLEX to use deterministic algorithms in all cases, set the parallel mode parameter to 1 (one).

To allow ILOG CPLEX to use opportunistic algorithms in all situations, set the parallel mode parameter to -1 (minus one).

The presence of a time limit, set by the time limit parameter (TiLim, CPX_PARAM_TILIM) for example, poses problems for reproducibility in any algorithm that is otherwise deterministic, even in sequential rather than parallel mode. Subtle variations in runtime on computer architectures can lead to variation in the measurement of time. (Other limits, such as node limits, are not subject to this variability.)

Because time limits are so important in many applications, ILOG CPLEX will still attempt to use deterministic mode without regard to whether a time limit is in effect. While variability will still be much lower than with the opportunistic setting, the user is advised that complete determinism within time limits can not be assured.

PREVIOUS NEXT