The Decomposition Algorithm

Example 16.4 Block-Angular Structure

(View the complete code for this example.)

This example demonstrates how you can use the default automated method to run the decomposition algorithm in single-machine mode.

As in Example 16.3, 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 120-second time limit.

proc optmilp
   nthreads = 4
   maxtime  = 120
   data     = mpsdata;
run;

The solution summary is shown in Output 16.4.1.

Output 16.4.1: Solution Summary

The OPTMILP Procedure

Solution Summary
Solver	MILP
Algorithm	Branch And Cut
Objective Function	Total_Profit
Solution Status	Time Limit Reached
Objective Value	6151.1464478

Relative Gap	0.1477175368
Absolute Gap	1066.1162717
Primal Infeasibility	0
Bound Infeasibility	0
Integer Infeasibility	0

Best Bound	7217.2627195
Nodes	1
Solutions Found	3
Iterations	52279
Presolve Time	0.61
Solution Time	59.93

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

Output 16.4.2: Log

NOTE: The problem MPSDATA has 52638 variables (16038 binary, 0 integer, 0 free, 0 fixed).

NOTE: The problem has 3949 constraints (3339 LE, 0 EQ, 610 GE, 0 range).

NOTE: The problem has 148866 constraint coefficients.

NOTE: The initial MILP heuristics are applied.

NOTE: The MILP presolver value AUTOMATIC is applied.

NOTE: The MILP presolver removed 0 variables and 734 constraints.

NOTE: The MILP presolver removed 17616 constraint coefficients.

NOTE: The MILP presolver modified 0 constraint coefficients.

NOTE: The presolved problem has 52638 variables, 3215 constraints, and 131250 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.

Node Active Sols BestInteger BestBound Gap Time

0 1 3 6151.1464478 8590.4503506 28.40% 0

0 1 3 6151.1464478 7342.1209241 16.22% 1

0 1 3 6151.1464478 7333.7075132 16.13% 6

0 1 3 6151.1464478 7300.0871000 15.74% 13

0 1 3 6151.1464478 7271.5875027 15.41% 26

0 1 3 6151.1464478 7243.9217432 15.09% 40

0 1 3 6151.1464478 7217.2627195 14.77% 58

0 1 3 6151.1464478 7217.2627195 14.77% 59

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

NOTE: Real time limit reached.

NOTE: Objective of the best integer solution found = 6151.1464478.

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

Standard MILP techniques struggle to solve the problem within the specified time limit. The default decomposition method attempts to find a block-angular structure by using the matrix-stretching techniques that are described in Grcar (1990) and Aykanat, Pinar, and Çatalyürek (2004) and techniques that are based on community detection and described in Khaniyev, Elhedhli, and Erenay (2018).

proc optmilp
   nthreads  = 4
   data      = mpsdata;
   decomp
      hybrid = false;
run;

The solution summary is displayed in Output 16.4.3.

Output 16.4.3: Solution Summary

The OPTMILP Procedure

Solution Summary
Solver	MILP
Algorithm	Decomposition
Objective Function	Total_Profit
Solution Status	Optimal within Relative Gap
Objective Value	6972.330935

Relative Gap	4.3340963E-9
Absolute Gap	0.0000302188
Primal Infeasibility	2.664535E-13
Bound Infeasibility	8.5277542E-8
Integer Infeasibility	7.882583E-15

Best Bound	6972.3309652
Nodes	1
Solutions Found	9
Iterations	7
Presolve Time	0.62
Solution Time	32.87

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

Output 16.4.4: Log

NOTE: The problem MPSDATA has 52638 variables (16038 binary, 0 integer, 0 free, 0 fixed).

NOTE: The problem has 3949 constraints (3339 LE, 0 EQ, 610 GE, 0 range).

NOTE: The problem has 148866 constraint coefficients.

NOTE: The initial MILP heuristics are applied.

NOTE: The MILP presolver value AUTOMATIC is applied.

NOTE: The MILP presolver removed 0 variables and 734 constraints.

NOTE: The MILP presolver removed 17616 constraint coefficients.

NOTE: The MILP presolver modified 0 constraint coefficients.

NOTE: The presolved problem has 52638 variables, 3215 constraints, and 131250 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 DEFAULT is applied.

NOTE: The decomposition identification used 0.23 (cpu: 0.28) seconds.

NOTE: The problem has a decomposable structure with 610 blocks. The largest block covers

0.2488% of the constraints in the problem.

NOTE: The decomposition subproblems cover 52638 (100%) variables and 3207 (99.75%) constraints.

NOTE: The deterministic parallel mode is enabled.

NOTE: The Decomposition algorithm is using up to 4 threads.

Iter Best Master Best LP IP CPU Real

Bound Objective Integer Gap Gap Time Time

. 7963.9759 6468.7936 6468.7936 18.77% 18.77% 13 8

2 7255.9732 6468.7936 6468.7936 10.85% 10.85% 27 12

3 7143.8221 6877.2652 6468.7936 3.73% 9.45% 52 21

5 6986.1299 6960.5400 6960.5400 0.37% 0.37% 76 29

6 6986.1299 6965.5335 6965.5335 0.29% 0.29% 86 31

7 6972.3310 6972.3309 6972.3309 0.00% 0.00% 89 32

Node Active Sols Best Best Gap CPU Real

Integer Bound Time Time

0 1 9 6972.3309 6972.3310 0.00% 89 32

NOTE: The Decomposition algorithm used 4 threads.

NOTE: The Decomposition algorithm time is 32.86 seconds.

NOTE: Optimal within relative gap.

NOTE: Objective = 6972.330935.

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

As stated in the log, the algorithm successfully finds a decomposition that contains 610 blocks and has more than 99% subproblem coverage.

Last updated: October 07, 2022