Root relaxation and parallel MIP processing

Describes special considerations about the root relaxation in parallel MIP optimization.

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 or QP, CPLEX invokes the concurrent optimizer by default. This practice provides a form of parallelism that assigns the available threads to multiple optimizers. If the root problem is a QCP, the barrier optimizer alone is used.

You can try a different form of parallelism at the root by selecting the barrier optimizer specifically with the algorithm for initial MIP relaxation parameter:

  • RootAlg in Concert Technology;

  • CPX_PARAM_STARTALG in the Callable Library;

  • set mip strategy startalgorithm in the Interactive Optimizer.

In such a case, the parallel threads will all be applied to the barrier algorithm.

To help you evaluate how much time is spent at the root node before parallel processing begins, the log of parallel MIP processing distinguishes time spent processing the root node before parallel branch and cut begins, like this typical log:

Root node processing (before b&c):    
   Real time             =    4.67 sec. (991.49 ticks)    
Parallel b&c, 2 threads:       
   Real time             =    17.68 sec. (5417.26 ticks)   
   Sync time (average)   =    0.01    
   Wait time (average)   =    0.00    
                            -------   
Total (root+branch&cut) =   22.35 sec. (6408.75 ticks)

The log of sequential MIP optimization also distinguishes time spent processing the root node before sequential branch and cut begins. If you contrast the following sample log file of sequential MIP optimization with the previous sample log file of parallel MIP optimization, you get an idea of the time spent in synchronization and waiting. This contrast in your own model may help you estimate how much speed up in performance to anticipate from parallel optimization.


Root node processing (before b&c):  
    Real time             =    4.25 sec. (971.17 ticks)
Sequential b&c:                     
    Real time             =    19.12 sec. (6441.66 ticks)
                            ------- 
    Total (root+branch&cut) =  23.37 sec. (7412.83 ticks)