Determinism, parallelism, and optimization limits

Documents effect of determinism on optimization limits.

CPLEX respects limits that the user sets, such limits as the number of iterations, the amount of time spent in optimization, and so forth. However, to achieve deterministic results, CPLEX must impose strict requirements with respect to synchronization of parallel threads or processes. The stricter synchronization requirements of deterministic parallel algorithms may cause CPLEX to deviate slightly from any non default limits on the optimization. For example, with a node limit of 2000 on four threads, the deterministic parallel MIP algorithm achieves the two-thousandth node on one thread but must wait for the other three threads to finish processing their nodes. In consequence, a final node count of up to 2003 is possible. Similarly, with a finite time limit on the parallel concurrent optimizer, if the thread for the dual simplex optimizer reaches the time limit first, it must wait for the other optimizers to finish their next iteration before that thread terminates. Particularly since each barrier method iteration involves computational effort equivalent to many simplex iterations, this wait for synchronization can yield a modest deviation from the specified time limit.