The Decomposition Algorithm

Example 13.4 Block-Diagonal Structure and METHOD=AUTO in Distributed Mode

This example demonstrates how you can use the METHOD=AUTO option in the DECOMP statement to execute the decomposition algorithm in distributed mode.

As in Example 13.3, consider a mixed integer linear program that is defined by the MPS data set mpsdata. In this case, the structure of the model is unknown and only the MPS data set is provided to you.

The following PROC OPTMILP statements use the METHOD=AUTO option in distributed mode. The PERFORMANCE statement specifies the number of threads and nodes to be used.

proc optmilp
   data       = mpsdata;
     loglevel = 2
     method   = auto;
     nthreads = 1
     nodes    = 4;

The performance information and solution summary are displayed in Output 13.4.1.

Output 13.4.1: Performance Information and Solution Summary

The OPTMILP Procedure

Performance Information
Host Node <<your grid host>>
Execution Mode Distributed
Grid Mode Symmetric
Number of Compute Nodes 4
Number of Threads per Node 1

Solution Summary
Solver MILP
Algorithm Decomposition
Objective Function R0001298
Solution Status Optimal
Objective Value 120
Relative Gap 0
Absolute Gap 0
Primal Infeasibility 0
Bound Infeasibility 0
Integer Infeasibility 0
Best Bound 120
Nodes 1
Iterations 1
Presolve Time 0.03
Solution Time 1.20

The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 13.4.2. When you specify NODES=4 and NTHREADS=1 in the PERFORMANCE statement in distributed mode, each block is processed simultaneously on each of four grid nodes.

Output 13.4.2: Log

NOTE: The problem MPSDATA has 388 variables (36 binary, 0 integer, 1 free, 0 fixed).  
NOTE: The problem has 1297 constraints (630 LE, 37 EQ, 630 GE, 0 range).              
NOTE: The problem has 4204 constraint coefficients.                                   
NOTE: The OPTMILP procedure is executing in the distributed computing environment     
      with 4 worker nodes.                                                            
NOTE: The MILP presolver value AUTOMATIC is applied.                                  
NOTE: The MILP presolver removed 37 variables and 37 constraints.                     
NOTE: The MILP presolver removed 424 constraint coefficients.                         
NOTE: The MILP presolver modified 0 constraint coefficients.                          
NOTE: The presolved problem has 351 variables, 1260 constraints, and 3780 constraint  
NOTE: The MILP solver is called.                                                      
NOTE: The Decomposition algorithm is used.                                            
NOTE: The DECOMP method value AUTO is applied.                                        
NOTE: The decomposition subproblems consist of 4 disjoint blocks.                     
NOTE: The decomposition subproblems cover 351 (100.00%) variables and 1260 (100.00%)  
NOTE: Block 0 has 88 (25.07%) variables and 316 (25.08%) constraints.                 
NOTE: Block 1 has 88 (25.07%) variables and 316 (25.08%) constraints.                 
NOTE: Block 2 has 88 (25.07%) variables and 316 (25.08%) constraints.                 
NOTE: Block 3 has 87 (24.79%) variables and 312 (24.76%) constraints.                 
NOTE: -----------------------------------------------------------------               
NOTE: Starting to process node 0.                                                     
NOTE: -----------------------------------------------------------------               
NOTE: The subproblem solver for 4 blocks at iteration 0 is starting.                  
NOTE: The subproblem solver for 4 blocks used 1.24 (cpu: 0.00) seconds.               
NOTE: The initial column pool after generating initial variables contains 4 columns.  
      Iter         Best       Master         Best       LP       IP  Real             
                  Bound    Objective      Integer      Gap      Gap  Time             
NOTE: Starting phase 2.                                                               
         1     120.0000     120.0000     120.0000    0.00%    0.00%     1             
NOTE: The number of active nodes is 0.                                                
NOTE: The objective value of the best integer feasible solution is 120.0000 and the   
      best bound is 120.0000.                                                         
NOTE: The Decomposition algorithm time is 1.25 seconds.                               
NOTE: Optimal.                                                                        
NOTE: Objective = 120.