The Dantzig-Wolfe Decomposition Algorithm

At each iteration of the decomposition method, the subproblem is solved to minimize the reduced cost that is derived from the dual information that solving the master problem provides. As discussed in the section Overview: Dantzig-Wolfe Decomposition Algorithm, the subproblem often has a block-angular structure that enables the solver to process each block independently.

When solving MILPs, you can run the Dantzig-Wolfe decomposition algorithm in either single-machine or distributed mode. If the DISTRIBUTED= option in the main solver statement is set to TRUE (and your configured CAS session has two or more workers), then the computation is executed in distributed mode (using multiple machines simultaneously). The Dantzig-Wolfe decomposition algorithm supports only the deterministic mode (DETERMINISTIC=TRUE in the main solver statement). The default mode of operation is single-machine mode.

You can control the number of threads that are used (by each machine) by specifying the NTHREADS= option in the main solver statement. In distributed mode, if the allowable number of active CPUs differs among machines, the Dantzig-Wolfe decomposition algorithm uses the minimum number allowed as the limit that is applied to the NTHREADS= option in the main solver statement. In addition, you can use the NTHREADS= option in each subcomponent statement to specify the number of threads to use for that solver. This is discussed in detail in the following sections:

Because of communication costs, increasing the number of machines does not guarantee faster execution, especially when you have subproblems that are unbalanced with respect to computational cost. For all the documentation examples, unless otherwise noted, the CAS session is configured for four worker nodes, each having 32 cores. For general information about CAS sessions, see SAS Cloud Analytic Services: Fundamentals.