### Example 13.3 Block-Diagonal Structure and METHOD=AUTO in Single-Machine Mode

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

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 15-second time limit:

```proc optmilp
data    = mpsdata
logfreq = 2000
maxtime = 15;
run;
```

The solution summary is shown in Output 13.3.1.

Output 13.3.1: Solution Summary

The OPTMILP Procedure

Solution Summary
Solver MILP
Algorithm Branch and Cut
Objective Function R0001298
Solution Status Time Limit Reached
Objective Value 133

Relative Gap 0.3965751025
Absolute Gap 37.767026308
Primal Infeasibility 0
Bound Infeasibility 0
Integer Infeasibility 0

Best Bound 95.232973692
Nodes 2268
Iterations 76252
Presolve Time 0.03
Solution Time 14.96

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

Output 13.3.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 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 coefficients. NOTE: The MILP solver is called. NOTE: The problem has a decomposable structure with 4 blocks. The largest block covers 25.08% of the rows in the problem. The DECOMP option with METHOD=AUTO is recommended for solving problems with this structure. Node  Active    Sols    BestInteger      BestBound      Gap    Time 0       1       1    231.0000000              0    231.0       0 0       1       1    231.0000000     91.4479396  152.60%       0 0       1       2    198.0000000     91.8607875  115.54%       0 0       1       2    198.0000000     92.0019485  115.21%       0 0       1       2    198.0000000     92.0404035  115.12%       0 0       1       2    198.0000000     92.0404035  115.12%       1 NOTE: The MILP solver added 6 cuts with 32 cut coefficients at the root. 787      36       3    135.0000000     95.2329737   41.76%       6 957     185       4    133.0000000     95.2329737   39.66%       7 2000    1075       4    133.0000000     95.2329737   39.66%      13 2281    1298       4    133.0000000     95.2329737   39.66%      14 NOTE: CPU time limit reached. NOTE: Objective of the best integer solution found = 133.

A note in the log suggests that you can use the decomposition algorithm because of the structure of the problem. The following PROC OPTMILP statements use the METHOD=AUTO option in the DECOMP statement in single-machine mode. The PERFORMANCE statement specifies the number of threads to be used.

```proc optmilp
data       = mpsdata;
decomp
loglevel = 2
method   = auto;
subprob
loglevel = 2;
performance
run;
```

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

Output 13.3.3: Performance Information and Solution Summary

The OPTMILP Procedure

Performance Information
Execution Mode Single-Machine

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 2.48

The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 13.3.4. When you specify NTHREADS=4 in the PERFORMANCE statement in single-machine mode, each block is processed simultaneously on each of four threads.

Output 13.3.4: 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 single-machine mode. 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 coefficients. 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%) constraints. 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: The deterministic parallel mode is enabled. NOTE: The Decomposition algorithm is using up to 4 threads. NOTE: ------------------------------------------------------------------------------- NOTE: Starting to process node 0. NOTE: ------------------------------------------------------------------------------- NOTE: ------------------------------------------------------------------------------- NOTE: The subproblem solver for 4 blocks at iteration 0 is starting. NOTE: ------------------------------------------------------------------------------- NOTE: The subproblem solver for block 0 at iteration 0 is starting on thread 1. NOTE: The MILP presolver value AUTOMATIC is applied. NOTE: The MILP presolver removed 0 variables and 0 constraints. NOTE: The MILP presolver removed 0 constraint coefficients. NOTE: The MILP presolver modified 0 constraint coefficients. NOTE: The presolved problem has 88 variables, 316 constraints, and 948 constraint coefficients. NOTE: The MILP solver is called. Node  Active    Sols    BestInteger      BestBound      Gap    Time 0       1       1            -16            -56   71.43%       0 0       1       1            -16 -34.1037735849   53.08%       0 0       1       1            -16 -34.1037735849   53.08%       0 41      34       2            -22 -32.8571428571   33.04%       0 80      49       3            -24 -31.5256410256   23.87%       0 100      56       3            -24 -30.8823529412   22.29%       0 134      35       4            -27       -30.1875   10.56%       0 200      34       4            -27          -28.4    4.93%       1 253       0       4            -27            -27    0.00%       1 NOTE: Optimal. NOTE: Objective = -27. NOTE: The subproblem solver for block 0 used 1.26 (cpu: 4.88) seconds. NOTE: ------------------------------------------------------------------------------- NOTE: ------------------------------------------------------------------------------- NOTE: The subproblem solver for block 1 at iteration 0 is starting on thread 2. NOTE: The MILP presolver value AUTOMATIC is applied. NOTE: The MILP presolver removed 0 variables and 0 constraints. NOTE: The MILP presolver removed 0 constraint coefficients. NOTE: The MILP presolver modified 0 constraint coefficients. NOTE: The presolved problem has 88 variables, 316 constraints, and 948 constraint coefficients. NOTE: The MILP solver is called. Node  Active    Sols    BestInteger      BestBound      Gap    Time 0       1       1              0            -59  100.00%       0 0       1       1              0 -35.3671970624  100.00%       0 0       1       2            -12 -35.3671970624   66.07%       0 0       1       3            -22 -35.3671970624   37.80%       0 0       1       3            -22 -35.3671970624   37.80%       0 29      25       4            -25 -34.6201565606   27.79%       0 100      71       5            -25 -33.3904056593   25.13%       0 166      89       7            -27 -32.8646661367   17.84%       1 186      52       8            -30 -32.3042378242    7.13%       1 200      48       8            -30 -32.0393180237    6.37%       1 267       0       8            -30            -30    0.00%       1 NOTE: Optimal. NOTE: Objective = -30. NOTE: The subproblem solver for block 1 used 1.43 (cpu: 5.40) seconds. NOTE: ------------------------------------------------------------------------------- NOTE: ------------------------------------------------------------------------------- NOTE: The subproblem solver for block 3 at iteration 0 is starting on thread 4. NOTE: The MILP presolver value AUTOMATIC is applied. NOTE: The MILP presolver removed 0 variables and 0 constraints. NOTE: The MILP presolver removed 0 constraint coefficients. NOTE: The MILP presolver modified 0 constraint coefficients. NOTE: The presolved problem has 87 variables, 312 constraints, and 936 constraint coefficients. NOTE: The MILP solver is called. Node  Active    Sols    BestInteger      BestBound      Gap    Time 0       1       1            -16            -57   71.93%       0 0       1       1            -16 -33.8743589744   52.77%       0 0       1       1            -16 -33.8133333333   52.68%       0 0       1       1            -16 -33.7577927973   52.60%       0 0       1       1            -16 -33.7153309512   52.54%       0 0       1       2            -19 -33.7153309512   43.65%       0 0       1       2            -19 -33.7153309512   43.65%       0 NOTE: The MILP solver added 3 cuts with 18 cut coefficients at the root. 6       6       3            -20 -33.5685920578   40.42%       0 56      44       4            -22 -32.7647058824   32.85%       0 81      58       5            -23 -32.4088337685   29.03%       0 100      69       5            -23 -32.1129411765   28.38%       0 200     114       6            -23 -30.3005780347   24.09%       1 290     129       8            -24 -29.3214285714   18.15%       1 299      83       9            -26 -29.2063492063   10.98%       1 300      82       9            -26 -29.1785714286   10.89%       1 400      40       9            -26 -27.1111111111    4.10%       1 449       0       9            -26            -26    0.00%       1 NOTE: Optimal. NOTE: Objective = -26. NOTE: The subproblem solver for block 3 used 1.88 (cpu: 6.30) seconds. NOTE: ------------------------------------------------------------------------------- NOTE: ------------------------------------------------------------------------------- NOTE: The subproblem solver for block 2 at iteration 0 is starting on thread 3. NOTE: The MILP presolver value AUTOMATIC is applied. NOTE: The MILP presolver removed 0 variables and 0 constraints. NOTE: The MILP presolver removed 0 constraint coefficients. NOTE: The MILP presolver modified 0 constraint coefficients. NOTE: The presolved problem has 88 variables, 316 constraints, and 948 constraint coefficients. NOTE: The MILP solver is called. Node  Active    Sols    BestInteger      BestBound      Gap    Time 0       1       1             -9            -59   84.75%       0 0       1       1             -9 -36.2067307692   75.14%       0 0       1       2            -14 -35.8906956361   60.99%       0 0       1       2            -14 -35.7582989209   60.85%       0 0       1       2            -14 -35.7308331027   60.82%       0 0       1       2            -14 -35.7308331027   60.82%       0 NOTE: The MILP solver added 3 cuts with 14 cut coefficients at the root. 53      42       4            -19 -34.6324177369   45.14%       0 67      51       6            -20 -34.3787806049   41.82%       0 70      53       7            -21 -34.3787806049   38.92%       0 100      72       8            -21 -34.0784347526   38.38%       0 157     102       9            -22  -33.326652221   33.99%       0 200     124       9            -22 -32.8793103448   33.09%       1 233     130      11            -24 -32.5099569429   26.18%       1 244     104      12            -27       -32.4375   16.76%       1 267      90      13            -28 -32.0592920354   12.66%       1 300     100      13            -28 -31.6450098814   11.52%       1 400      69      14            -28 -29.6666666667    5.62%       1 489       0      14            -28            -28    0.00%       1 NOTE: Optimal. NOTE: Objective = -28. NOTE: The subproblem solver for block 2 used 1.98 (cpu: 6.41) seconds. NOTE: ------------------------------------------------------------------------------- NOTE: The subproblem solver for 4 blocks used 1.99 (cpu: 6.41) seconds. NOTE: ------------------------------------------------------------------------------- NOTE: The initial column pool after generating initial variables contains 4 columns. Iter         Best       Master         Best       LP       IP   CPU  Real Bound    Objective      Integer      Gap      Gap  Time  Time NOTE: Starting phase 2. 1     120.0000     120.0000     120.0000    0.00%    0.00%     6     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 used 4 threads. NOTE: The Decomposition algorithm time is 2.00 seconds. NOTE: Optimal. NOTE: Objective = 120.

In this case, the solver found that, after presolve, the constraint matrix decomposed into block-diagonal form. That is, all the constraints are covered by subproblem blocks, leaving the set of master constraints empty. With no coupling constraints, the problem decomposes into four completely independent problems. If you specify LOGLEVEL=2 in the DECOMP statement, the log displays the size of each block. The blocks in this case are nicely balanced, allowing parallel execution to be efficient, and the solver finds the optimal solution almost immediately.