The Decomposition Algorithm

Example 16.3 Block-Diagonal Structure and METHOD=CONCOMP

(View the complete code for this example.)

This example demonstrates how you can use the METHOD=CONCOMP option in the DECOMP statement to run the decomposition algorithm.

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 solve the problem by using standard methods.

proc optmilp
   nthreads = 4
   data     = mpsdata;
run;

The solution summary is shown in Output 16.3.1.

Output 16.3.1: Solution Summary

The OPTMILP Procedure

Solution Summary
Solver	MILP
Algorithm	Branch And Cut
Objective Function	R0001298
Solution Status	Optimal
Objective Value	120

Relative Gap	0
Absolute Gap	0
Primal Infeasibility	2.264855E-14
Bound Infeasibility	1.154632E-14
Integer Infeasibility	0

Best Bound	120
Nodes	283
Solutions Found	3
Iterations	38127
Presolve Time	0.01
Solution Time	1.39

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

Output 16.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 initial MILP heuristics are applied.

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 parallel Branch and Cut algorithm is used.

NOTE: The Branch and Cut algorithm is using up to 4 threads.

NOTE: The problem has a decomposable structure with 4 blocks. The largest block covers 25.08%

of the constraints in the problem. The DECOMP option with METHOD=CONCOMP is recommended

for solving problems with this structure.

Node Active Sols BestInteger BestBound Gap Time

0 1 2 161.0000000 0 161.0 0

0 1 2 161.0000000 91.4479396 76.06% 0

0 1 2 161.0000000 111.7932692 44.02% 1

NOTE: The MILP presolver is applied again.

0 1 3 128.0000000 111.7932692 14.50% 1

0 1 4 127.0000000 111.7932692 13.60% 1

0 1 4 127.0000000 112.1093044 13.28% 1

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

54 33 5 123.0000000 114.1564268 7.75% 1

60 36 6 120.0000000 114.4368512 4.86% 1

282 0 6 120.0000000 120.0000000 0.00% 1

NOTE: Optimal.

NOTE: Objective = 120.

NOTE: There were 6215 observations read from the data set WORK.MPSDATA.

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=CONCOMP option in the DECOMP statement.

proc optmilp
   nthreads    = 4
   data        = mpsdata;
   decomp
      loglevel = moderate
      method   = concomp;
run;

The solution summary is displayed in Output 16.3.3.

Output 16.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	3.752554E-14
Bound Infeasibility	2.420286E-14
Integer Infeasibility	0

Best Bound	120
Nodes	1
Solutions Found	4
Iterations	1
Presolve Time	0.01
Solution Time	0.59

The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 16.3.4. When you specify NTHREADS=4 in the PROC OPTMILP statement, the blocks are processed simultaneously on four threads.

Output 16.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 initial MILP heuristics are applied.

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 Decomposition algorithm is executing in single-machine mode.

NOTE: The DECOMP method value CONCOMP is applied.

NOTE: The decomposition identification used 0.00 (cpu: 0.00) seconds.

NOTE: The problem has a decomposable structure with 4 blocks. The largest block covers 25.08%

of the constraints in the problem.

NOTE: The decomposition subproblems cover 351 (100%) variables and 1260 (100%) 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 88 (25.07%) variables and 316 (25.08%) constraints.

NOTE: Block 4 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: Using a starting solution with objective value 161 to provide initial columns.

NOTE: Using a starting solution with objective value 231 to provide initial columns.

NOTE: The initial column pool using the starting solution contains 8 columns.

NOTE: The subproblem solver for 4 blocks at iteration 0 is starting.

NOTE: The subproblem solver for 4 blocks used 0.55 (cpu: 1.60, max: 0.55) seconds.

NOTE: The initial column pool after generating initial variables contains 12 columns.

Iter Best Master Best LP IP CPU Real

Bound Objective Integer Gap Gap Time Time

NOTE: The master solver at iteration 1 is starting.

NOTE: The master solver used 0.00 (cpu: 0.00) seconds and 0 iterations.

1 120.0000 120.0000 120.0000 0.00% 0.00% 1 0

NOTE: The number of active nodes is 1.

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 0.59 seconds.

NOTE: Optimal.

NOTE: Objective = 120.

NOTE: There were 6215 observations read from the data set WORK.MPSDATA.

In this case, the solver finds that after the presolve, the constraint matrix decomposes into block-diagonal form. That is, all the constraints are covered by subproblem blocks, leaving the set of master constraints empty. Because there are no coupling constraints, the problem decomposes into four completely independent problems. If you specify LOGLEVEL=MODERATE 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.

Last updated: October 07, 2022