The Decomposition Algorithm
- Overview
-
Getting Started
-
SyntaxDecomposition Algorithm Options in the PROC OPTLP Statement or the SOLVE WITH LP Statement in PROC OPTMODELDecomposition Algorithm Options in the PROC OPTMILP Statement or the SOLVE WITH MILP Statement in PROC OPTMODELDECOMP StatementDECOMP_MASTER StatementDECOMP_MASTER_IP StatementDECOMP_SUBPROB Statement
-
Details
-
ExamplesMulticommodity Flow ProblemGeneralized Assignment ProblemBlock-Diagonal Structure and METHOD=CONCOMP in Single-Machine ModeBlock-Diagonal Structure and METHOD=CONCOMP in Distributed ModeBlock-Angular Structure and METHOD=AUTOBin Packing ProblemResource Allocation ProblemVehicle Routing ProblemATM Cash Management in Single-Machine ModeATM Cash Management in Distributed ModeKidney Donor Exchange
- References
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: Decomposition Algorithm, the subproblem often has a block-diagonal structure that enables the solver to process each block independently.
You can run the decomposition algorithm in either a single-machine or a distributed computing environment. In single-machine mode, the computation is executed by multiple threads on a single computer. You can specify options for parallel execution in the PERFORMANCE statement, which is documented in the section PERFORMANCE Statement of Chapter 4: Shared Concepts and Topics. You can control the number of threads that are used by specifying the NTHREADS= option in the PERFORMANCE statement. In distributed mode, the computation is executed in a distributed computing environment. You can control the number of grid nodes (machines) that are used by specifying the NODES= option in the PERFORMANCE statement. The decomposition algorithm supports only the deterministic mode of the PARALLELMODE= option in the PERFORMANCE statement. The default mode of operation is single-machine mode, in which the number of concurrent threads is based on the number of CPUs (cores) on the machine (subject to any configuration limitations of the system).
The specified number of threads is used at each iteration to determine the number of blocks to be processed simultaneously. This same value is also used to determine the number of threads to be used for solving the master (continuous and integer) problem if the chosen solver method supports multithreading. To avoid contention, the number of threads that are allocated to each subproblem solve is 1 (unless the number of blocks to process is less than the number of threads).
In addition, in each subcomponent statement you can use the NTHREADS= option to specify the number of threads to use for that solver.
Note: Distributed mode requires SAS High-Performance Optimization.