The Decomposition Algorithm

Solving a MILP with DECOMP and PROC OPTMODEL

The following statements use the OPTMODEL procedure and the decomposition algorithm to solve the MILP:

proc optmodel;
   var x{i in 1..3, j in 1..2} binary;

   max f =    x[1,1] + 2*x[2,1] +   x[3,1]
                     +   x[2,2] +   x[3,2];

   con m :    x[1,1] +   x[1,2]            >=  1;
   con s1:  5*x[1,1] + 7*x[2,1] + 4*x[3,1] <= 11;
   con s2:    x[1,2] + 2*x[2,2] +   x[3,2] <=  2;

   s1.block = 0;
   s2.block = 1;

   solve with milp / presolver=none decomp=(logfreq=1);
   print x;
quit;

Here, the PRESOLVER=NONE option is used, because otherwise the presolver solves this small instance without invoking any solver. The solution summary and optimal solution are displayed in Figure 15.1.

Figure 15.1: Solution Summary and Optimal Solution

The OPTMODEL Procedure

Solution Summary
Solver MILP
Algorithm Decomposition
Objective Function f
Solution Status Optimal
Objective Value 4
   
Relative Gap 0
Absolute Gap 0
Primal Infeasibility 0
Bound Infeasibility 0
Integer Infeasibility 0
   
Best Bound 4
Nodes 1
Iterations 2
Presolve Time 0.00
Solution Time 0.01

x
  1 2
1 0 1
2 1 0
3 1 1



The iteration log, which displays the problem statistics, the progress of the solution, and the optimal objective value, is shown in Figure 15.2.

Figure 15.2: Log

NOTE: Problem generation will use 4 threads.                                                    
NOTE: The problem has 6 variables (0 free, 0 fixed).                                            
NOTE: The problem has 6 binary and 0 integer variables.                                         
NOTE: The problem has 3 linear constraints (2 LE, 0 EQ, 1 GE, 0 range).                         
NOTE: The problem has 8 linear constraint coefficients.                                         
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).                      
NOTE: The MILP presolver value NONE is applied.                                                 
NOTE: The MILP solver is called.                                                                
NOTE: The Decomposition algorithm is used.                                                      
NOTE: The Decomposition algorithm is executing in single-machine mode.                          
NOTE: The DECOMP method value USER is applied.                                                  
NOTE: The problem has a decomposable structure with 2 blocks. The largest block covers 33.33%   
      of the constraints in the problem.                                                        
NOTE: The decomposition subproblems cover 6 (100.00%) variables and 2 (66.67%) 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       0.0000            .    0.00%        .    0    0                   
NOTE: Starting phase 2.                                                                         
         2       4.0000       4.0000       4.0000    0.00%    0.00%    0    0                   
         Node  Active   Sols         Best         Best      Gap    CPU   Real                   
                                  Integer        Bound            Time   Time                   
            0       0      1       4.0000       4.0000    0.00%      0      0                   
NOTE: The Decomposition algorithm used 4 threads.                                               
NOTE: The Decomposition algorithm time is 0.01 seconds.                                         
NOTE: Optimal.                                                                                  
NOTE: Objective = 4.