The Decomposition Algorithm

Example 15.5 Block-Angular Structure and METHOD=AUTO

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

As in Example 15.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 attempt to solve the problem by using standard methods and a 60-second time limit:

proc optmilp
   maxtime = 60
   data    = mpsdata;
run;

The solution summary is shown in Output 15.5.1.

Output 15.5.1: Solution Summary

The OPTMILP Procedure

Solution Summary
Solver MILP
Algorithm Branch and Cut
Objective Function Total_Profit
Solution Status Time Limit Reached
   
Best Bound 7291.4925915
Nodes 1
Iterations 38627
Presolve Time 0.45
Solution Time 60.01



The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 15.5.2.

Output 15.5.2: Log

NOTE: The problem MPSDATA has 52638 variables (16038 binary, 0 integer, 0 free, 0 fixed).       
NOTE: The problem has 3949 constraints (3339 LE, 0 EQ, 610 GE, 0 range).                        
NOTE: The problem has 148866 constraint coefficients.                                           
NOTE: The MILP presolver value AUTOMATIC is applied.                                            
NOTE: The MILP presolver removed 0 variables and 367 constraints.                               
NOTE: The MILP presolver removed 6606 constraint coefficients.                                  
NOTE: The MILP presolver modified 0 constraint coefficients.                                    
NOTE: The presolved problem has 52638 variables, 3582 constraints, and 142260 constraint        
      coefficients.                                                                             
NOTE: The MILP solver is called.                                                                
          Node  Active    Sols    BestInteger      BestBound      Gap    Time                   
             0       1       0              .   7342.1209242        .       0                   
             0       1       0              .   7339.5605463        .       7                   
             0       1       0              .   7329.6821306        .      14                   
             0       1       0              .   7321.1115391        .      22                   
             0       1       0              .   7315.4737113        .      29                   
             0       1       0              .   7310.5357458        .      38                   
             0       1       0              .   7306.4611529        .      45                   
             0       1       0              .   7300.6129841        .      53                   
             0       1       0              .   7295.3817577        .      55                   
             0       1       0              .   7291.4925915        .      58                   
NOTE: The MILP solver added 4944 cuts with 118150 cut coefficients at the root.                 
NOTE: CPU time limit reached.                                                                   
NOTE: No integer solutions found.                                                               



Standard MILP techniques struggle to find a feasible solution within the specified time limit. The default decomposition method (METHOD=AUTO) attempts to find a block-angular structure by using the matrix-stretching techniques that are described in Grcar (1990) and Aykanat, Pinar, and Çatalyürek (2004).

proc optmilp
   data     = mpsdata;
   decomp
     method = auto;
run;

The solution summary is displayed in Output 15.5.3.

Output 15.5.3: Solution Summary

The OPTMILP Procedure

Solution Summary
Solver MILP
Algorithm Decomposition
Objective Function Total_Profit
Solution Status Optimal within Relative Gap
Objective Value 6972.3309347
   
Relative Gap 2.884077E-9
Absolute Gap 0.0000201087
Primal Infeasibility 1.000244E-11
Bound Infeasibility 8.097545E-11
Integer Infeasibility 7.771561E-15
   
Best Bound 6972.3309548
Nodes 1
Iterations 11
Presolve Time 0.46
Solution Time 34.55



The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 15.5.4.

Output 15.5.4: Log

NOTE: The OPTMILP procedure is executing in single-machine mode.                                
NOTE: The problem MPSDATA has 52638 variables (16038 binary, 0 integer, 0 free, 0 fixed).       
NOTE: The problem has 3949 constraints (3339 LE, 0 EQ, 610 GE, 0 range).                        
NOTE: The problem has 148866 constraint coefficients.                                           
NOTE: The MILP presolver value AUTOMATIC is applied.                                            
NOTE: The MILP presolver removed 0 variables and 367 constraints.                               
NOTE: The MILP presolver removed 6606 constraint coefficients.                                  
NOTE: The MILP presolver modified 0 constraint coefficients.                                    
NOTE: The presolved problem has 52638 variables, 3582 constraints, and 142260 constraint        
      coefficients.                                                                             
NOTE: The MILP solver is called.                                                                
NOTE: The Decomposition algorithm is used.                                                      
NOTE: The DECOMP method value AUTO is applied.                                                  
NOTE: The automated method will attempt to find block-angular form with 4 blocks.               
NOTE: The problem has a decomposable structure with 610 blocks. The largest block covers 0.22%  
      of the constraints in the problem.                                                        
NOTE: The decomposition subproblems cover 52638 (100.00%) variables and 3574 (99.78%)           
      constraints.                                                                              
NOTE: The deterministic parallel mode is enabled.                                               
NOTE: The Decomposition algorithm is using up to 4 threads.                                     
      Iter         Best       Master         Best       LP       IP  CPU Real                   
                  Bound    Objective      Integer      Gap      Gap Time Time                   
NOTE: Starting phase 1.                                                                         
         1       0.0000     302.6667            . 3.03e+02        .   12    3                   
         4       0.0000       0.0000            .    0.00%        .   13    3                   
NOTE: Starting phase 2.                                                                         
         6    7586.8795    6393.7089    6387.7547   15.73%   15.81%   33   10                   
         7    7119.4327    6751.1789    6387.7547    5.17%   10.28%   52   15                   
         8    6976.4120    6932.9565    6387.7547    0.62%    8.44%   77   22                   
         9    6976.4120    6963.3497    6963.3497    0.19%    0.19%  102   29                   
         .    6976.4120    6968.0658    6968.0658    0.12%    0.12%  103   30                   
        10    6976.4120    6968.0658    6968.0658    0.12%    0.12%  108   31                   
        11    6972.3310    6972.3309    6972.3309    0.00%    0.00%  113   33                   
         Node  Active   Sols         Best         Best      Gap    CPU   Real                   
                                  Integer        Bound            Time   Time                   
            0       0      4    6972.3309    6972.3310    0.00%    113     33                   
NOTE: The Decomposition algorithm used 4 threads.                                               
NOTE: The Decomposition algorithm time is 33.97 seconds.                                        
NOTE: Optimal within relative gap.                                                              
NOTE: Objective = 6972.3309347.                                                                 



As stated in the log, the automated method attempts to find a balanced block-angular form that contains four blocks (the same setting is used by default in the NTHREADS= option). The algorithm successfully finds such a decomposition and then further decomposes each block into its weakly connected components, resulting in 610 blocks and 99.78% subproblem coverage.