The Decomposition Algorithm

Example 13.3 Block-Diagonal Structure Using METHOD=AUTO

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

Consider a mixed integer linear program 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	141

Relative Gap	0.4813041883
Absolute Gap	45.81360877
Primal Infeasibility	0
Bound Infeasibility	0
Integer Infeasibility	0

Best Bound	95.18639123
Nodes	1318
Iterations	44477
Presolve Time	0.03
Solution Time	14.99

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.0423991 115.12% 0
0 1 2 198.0000000 92.0754817 115.04% 0
0 1 2 198.0000000 92.0754817 115.04% 1
NOTE: The MILP solver added 5 cuts with 32 cut coefficients at the root.
787 36 3 150.0000000 95.1863912 57.59% 9
824 69 4 148.0000000 95.1863912 55.48% 9
825 68 5 144.0000000 95.1863912 51.28% 9
926 159 6 142.0000000 95.1863912 49.18% 11
1220 417 7 141.0000000 95.1863912 48.13% 13
1320 502 7 141.0000000 95.1863912 48.13% 14
NOTE: CPU time limit reached.
NOTE: Objective of the best integer solution found = 141.

A note in the log suggests using the decomposition algorithm because of the structure of the problem. The following PROC OPTMILP statements use the METHOD=AUTO option:

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

The solution summary is shown in Output 13.3.3.

Output 13.3.3: Solution Summary

The OPTMILP Procedure

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.02
Solution Time	2.37

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

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 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 16 threads.

NOTE: -------------------------------------------------------------------------------

NOTE: Starting to process node 0.

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

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.103774 53.08% 0

41 34 2 -22 -32.857143 33.04% 0

79 50 3 -24 -31.525641 23.87% 0

100 58 3 -24 -30.875 22.27% 0

120 38 4 -27 -30.209524 10.62% 0

200 29 4 -27 -28 3.57% 1

248 0 4 -27 -27 0.00% 1

NOTE: Optimal.

NOTE: Objective = -27.

NOTE: The subproblem solver for block 0 used 1.14 (cpu: 4.49) seconds.

NOTE: -------------------------------------------------------------------------------

NOTE: The subproblem solver for block 1 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 0 -59 100.00% 0

0 1 1 0 -35.367197 100.00% 0

0 1 2 -12 -35.367197 66.07% 0

0 1 3 -22 -35.367197 37.80% 0

29 24 4 -25 -34.620157 27.79% 0

100 69 5 -25 -33.390406 25.13% 0

184 52 7 -30 -32.297517 7.11% 1

200 50 7 -30 -32.066667 6.44% 1

281 0 7 -30 -30 0.00% 1

NOTE: Optimal.

NOTE: Objective = -30.

NOTE: The subproblem solver for block 1 used 1.42 (cpu: 5.32) seconds.

NOTE: -------------------------------------------------------------------------------

NOTE: The subproblem solver for block 2 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 -9 -59 84.75% 0

0 1 1 -9 -36.206731 75.14% 0

0 1 2 -14 -35.890696 60.99% 0

0 1 2 -14 -35.717848 60.80% 0

0 1 2 -14 -35.695755 60.78% 0

0 1 2 -14 -35.695406 60.78% 0

0 1 2 -14 -35.678332 60.76% 0

0 1 2 -14 -35.666465 60.75% 0

0 1 2 -14 -35.666275 60.75% 0

NOTE: The MILP solver added 5 cuts with 34 cut coefficients at the root.

29 25 3 -21 -35.108701 40.19% 0

100 72 4 -21 -33.944444 38.13% 0

103 72 5 -22 -33.85206 35.01% 0

149 73 6 -28 -33.384915 16.13% 1

200 87 7 -28 -32.578125 14.05% 1

300 95 7 -28 -30.982929 9.63% 1

400 67 7 -28 -29.484848 5.04% 1

475 0 7 -28 -28 0.00% 1

NOTE: Optimal.

NOTE: Objective = -28.

NOTE: The subproblem solver for block 2 used 1.79 (cpu: 6.05) seconds.

NOTE: -------------------------------------------------------------------------------

NOTE: The subproblem solver for block 3 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 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.874359 52.77% 0

0 1 1 -16 -33.813333 52.68% 0

0 1 1 -16 -33.788667 52.65% 0

0 1 1 -16 -33.757793 52.60% 0

0 1 1 -16 -33.708333 52.53% 0

0 1 1 -16 -33.695839 52.52% 0

0 1 2 -19 -33.695839 43.61% 0

NOTE: The MILP solver added 4 cuts with 21 cut coefficients at the root.

6 6 3 -20 -33.56867 40.42% 0

100 74 3 -20 -32.15016 37.79% 0

111 77 4 -21 -32 34.37% 0

132 84 6 -23 -31.8 27.67% 1

200 111 7 -23 -30.72192 25.13% 1

249 101 8 -25 -29.915126 16.43% 1

300 109 8 -25 -29.25 14.53% 1

307 86 9 -26 -29.206349 10.98% 1

400 60 9 -26 -27.422535 5.19% 1

464 0 9 -26 -26 0.00% 1

NOTE: Optimal.

NOTE: Objective = -26.

NOTE: The subproblem solver for block 3 used 1.92 (cpu: 6.18) seconds.

NOTE: -------------------------------------------------------------------------------

NOTE: The subproblem solver for 4 blocks used 1.92 (cpu: 6.18) seconds.

NOTE: -------------------------------------------------------------------------------

NOTE: The initial column pool aftering 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 0.0000 120.0000 120.0000 1.20e+02 1.20e+02 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 0.0000.

NOTE: The Decomposition algorithm used 4 threads.

NOTE: The Decomposition algorithm time is 1.92 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 of 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, which allows parallel execution to be efficient, and the solver finds the optimal solution almost immediately.