The Dantzig-Wolfe Decomposition Algorithm

Example 18.5 Block-Angular Structure in Distributed Mode

This example demonstrates how you can use the default automated method to run the Dantzig-Wolfe decomposition algorithm in distributed mode.

Consider again the mixed integer linear program that is defined by the MPS data table mylib.mpsdata. The following PROC OPTMILP statements run the Dantzig-Wolfe decomposition algorithm in distributed mode. The DATA= option assumes that your libref is named mylib, but you can substitute any appropriately defined libref.

proc optmilp
   distributed = true
   nthreads    = 4
   data        = mylib.mpsdata;
   decomp
      hybrid   = false;
run;

The solution summary is displayed in Output 18.5.1.

Output 18.5.1: Solution Summary

The OPTMILP Procedure

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

Relative Gap	9.4901139E-9
Absolute Gap	0.0000661682
Primal Infeasibility	5.07927E-14
Bound Infeasibility	5.884182E-15
Integer Infeasibility	8.881784E-15

Best Bound	6972.3310008
Nodes	1
Solutions Found	10
Iterations	7

Presolve Time	0.27
Solution Time	22.24

The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 18.5.2. When you specify DISTRIBUTED=TRUE and NTHREADS=4 in the OPTMILP statement, the blocks are processed using all the machines in your configured session (four machines in this case). Each machine uses four threads.

Output 18.5.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 Decomposition algorithm is used.

NOTE: The Decomposition algorithm is executing in the distributed computing environment with 4

worker nodes.

NOTE: The DECOMP method value DEFAULT is applied.

NOTE: The decomposition identification used 0.15 (cpu: 0.21) 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 Real

Bound Objective Integer Gap Gap Time

. 7963.9920 6475.3533 6472.9990 18.69% 18.72% 6

2 7273.6083 6475.3533 6472.9990 10.97% 11.01% 8

3 7149.3907 6863.5987 6472.9990 4.00% 9.46% 12

5 6985.8461 6960.5561 6960.5561 0.36% 0.36% 16

6 6985.8461 6967.2510 6967.2510 0.27% 0.27% 19

7 6972.3310 6972.3309 6972.3309 0.00% 0.00% 22

Node Active Sols Best Best Gap Real

Integer Bound Time

0 1 10 6972.3309 6972.3310 0.00% 22

NOTE: The Decomposition algorithm used 4 threads.

NOTE: The Decomposition algorithm time is 22.24 seconds.

NOTE: Optimal within relative gap.

NOTE: Objective = 6972.3309347.

NOTE: The Cloud Analytic Services server processed the request in 22.544654 seconds.

In this case, the automated method successfully finds a decomposition that contains 610 blocks and has more than 99% subproblem coverage, as in Example 18.4.

Last updated: June 22, 2026