The Decomposition Algorithm

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
     nthreads = 4;
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
Number of Threads	4

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: 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

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: 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

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: 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

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: 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

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.