The Dantzig-Wolfe Decomposition Algorithm

Example 18.10 ATM Cash Management in Distributed Mode

This section illustrates how you can use PROC OPTMODEL and the Dantzig-Wolfe decomposition algorithm in distributed mode. The problem is the same as the one described in Example 18.9 for managing the cash flow of a bank’s network of automated teller machines (ATMs). The only difference between single-machine and distributed mode is that the DISTRIBUTED= option is set to TRUE in the main solver statement. In this example, the CAS session is configured for 20 worker nodes, each having 32 cores.

The following statement changes the operating mode to distributed mode:

   /* solve with the Dantzig-Wolfe decomposition algorithm (in distributed mode) */
   solve with milp / distributed=true nthreads=4 relobjgap=0.01 decomp;

When you specify DISTRIBUTED=TRUE and NTHREADS=4, each machine in your configured session processes the subproblems by using up to four threads simultaneously (per machine).

The solution summary is displayed in Output 18.10.1.

Output 18.10.1: Solution Summary Table

The OPTMODEL Procedure

Solution Summary
Solver	MILP
Algorithm	Decomposition
Objective Function	CashFlowDiff
Solution Status	Optimal within Relative Gap
Objective Value	2466206.8269

Relative Gap	0.0094127499
Absolute Gap	22997.319943
Primal Infeasibility	5.684342E-14
Bound Infeasibility	0
Integer Infeasibility	0

Best Bound	2443209.507
Nodes	1
Solutions Found	5
Iterations	10
Presolve Time	0.43
Solution Time	14.84

The iteration log, which contains the problem statistics, the progress of the solution, and the optimal objective value, is shown in Output 18.10.2.

Output 18.10.2: Log

NOTE: There were 100 observations read from the data set WORK.BUDGET_DATA.

NOTE: There were 20 observations read from the data set WORK.CASHOUT_DATA.

NOTE: There were 2000 observations read from the data set WORK.POLYFIT_DATA.

NOTE: Problem generation will use 4 threads.

NOTE: The problem has 6480 variables (0 free, 0 fixed).

NOTE: The problem has 2220 binary and 0 integer variables.

NOTE: The problem has 4380 linear constraints (2340 LE, 2040 EQ, 0 GE, 0 range).

NOTE: The problem has 58878 linear constraint coefficients.

NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).

NOTE: The SOLVE statement is executing in the distributed computing environment with 20 worker

nodes.

NOTE: The initial MILP heuristics are applied.

NOTE: The MILP presolver value AUTOMATIC is applied.

NOTE: The MILP presolver removed 562 variables and 390 constraints.

NOTE: The MILP presolver removed 14325 constraint coefficients.

NOTE: The MILP presolver modified 0 constraint coefficients.

NOTE: The presolved problem has 5918 variables, 3990 constraints, and 44553 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 20

worker nodes.

NOTE: The DECOMP method value USER is applied.

NOTE: The problem has a decomposable structure with 20 blocks. The largest block covers 5.138%

of the constraints in the problem.

NOTE: The decomposition subproblems cover 5918 (100%) variables and 3890 (97.49%) 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

NOTE: Starting phase 1.

1 0.0000 1.1767 . 1.18e+00 . 5

2 0.0000 0.0000 . 0.00% . 5

3 0.0000 0.0000 . 0.00% . 5

NOTE: Starting phase 2.

. 2.4432e+06 2.5704e+06 2.5712e+06 5.21% 5.24% 7

8 2.4432e+06 2.4790e+06 2.4823e+06 1.46% 1.60% 14

NOTE: The Decomposition algorithm stopped on the integer RELOBJGAP= option.

10 2.4432e+06 2.4640e+06 2.4662e+06 0.85% 0.94% 14

Node Active Sols Best Best Gap Real

Integer Bound Time

0 1 5 2.4662e+06 2.4432e+06 0.94% 14

NOTE: The Decomposition algorithm used 4 threads.

NOTE: The Decomposition algorithm time is 14.84 seconds.

NOTE: Optimal within relative gap.

NOTE: Objective = 2466206.8269.

Notice how this iteration log differs from the iteration log for single-machine mode in Example 18.9. In this case, the path is slightly altered because each block solve uses four threads (parallel branch-and-cut) to solve the subproblems as opposed to one thread (sequential branch-and-cut) when running in single-machine mode. The calculation of the default value for the NTHREADS= option in the DECOMPSUBPROB statement is described on .

Last updated: June 22, 2026