The Decomposition Algorithm

Example 15.3 Block-Diagonal Structure and METHOD=CONCOMP in Single-Machine Mode

This example demonstrates how you can use the METHOD=CONCOMP 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 solve the problem by using standard methods:

proc optmilp
   data = mpsdata;
run;

The solution summary is shown in Output 15.3.1.

Output 15.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	6.039615E-14
Bound Infeasibility	3.019808E-14
Integer Infeasibility	8.437695E-15

Best Bound	120
Nodes	1
Iterations	40025
Presolve Time	0.02
Solution Time	2.33

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

Output 15.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 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 1 231.0000000 91.4479396 152.60% 0

0 1 2 120.0000000 120.0000000 0.00% 2

0 0 2 120.0000000 120.0000000 0.00% 2

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

NOTE: Optimal.

NOTE: Objective = 120.

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 in single-machine mode. The PERFORMANCE statement specifies the number of threads to use.

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

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

Output 15.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	6.528111E-14
Bound Infeasibility	3.28626E-14
Integer Infeasibility	0

Best Bound	120
Nodes	1
Iterations	1
Presolve Time	0.02
Solution Time	0.89

The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 15.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 15.3.4: Log

NOTE: The OPTMILP procedure is executing in single-machine mode.

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 CONCOMP is applied.

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 231 to provide initial columns.

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

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

NOTE: The subproblem solver for 4 blocks used 0.83 (cpu: 2.64) seconds.

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

NOTE: The master solver at iteration 1 is starting.

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

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

NOTE: Optimal.

NOTE: Objective = 120.

In this case, the solver finds that after 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=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.