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 13.1.

Figure 13.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 4
Presolve Time 0.01
Solution Time 0.36

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 13.2.

Figure 13.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 decomposition subproblems consist of 2 disjoint blocks.                     
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       1.0000            . 1.00e+00        .     0     0       
         2       0.0000       0.0000            .    0.00%        .     0     0       
NOTE: Starting phase 2.                                                               
         .       4.0000       3.0000       3.0000   25.00%   25.00%     0     0       
         3       4.0000       3.0000       3.0000   25.00%   25.00%     0     0       
         4       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      2       4.0000       4.0000    0.00%       0       0       
NOTE: The Decomposition algorithm used 2 threads.                                     
NOTE: The Decomposition algorithm time is 0.02 seconds.                               
NOTE: Optimal.                                                                        
NOTE: Objective = 4.