The Dantzig-Wolfe Decomposition Algorithm

DECOMP Statement

DECOMP <decomp-options>;

DECOMPOSITION <decomp-options>;

The DECOMP statement controls the overall Dantzig-Wolfe decomposition algorithm.

Table 3 summarizes the decomp-options available in the DECOMP statement. These options control the overall Dantzig-Wolfe decomposition algorithm process flow during the solution of an LP or a MILP. (As the table indicates, you can specify the data table options only in the OPTLP or OPTMILP procedure, and you can specify some control options only for a MILP.)

Table 3: Options in the DECOMP Statement

Description	decomp-option
Data Table Options (OPTLP and OPTMILP procedures only)
Specifies the blocks input data table	BLOCKS=
Control Options
Specifies the stopping criterion based on an absolute objective gap	ABSOBJGAP=
Specifies the level of detail of solution progress to print in the log	LOGLEVEL=
Specifies the maximum number of blocks to allow	MAXBLOCKS=
Specifies the block-specification method	METHOD=
Specifies the number of blocks to search for in the automated detection methods	NBLOCKS=
Specifies the range for the number of blocks to search for in the automated detection methods	NBLOCKSRANGE=
Specifies the number of block threads to use in the Dantzig-Wolfe decomposition algorithm	NTHREADS=
Specifies the stopping criterion based on a relative objective gap	RELOBJGAP=
Control Options (MILP only)
Specifies whether to process the root node by using standard MILP techniques	HYBRID=
Specifies how frequently to print the continuous iteration log	LOGFREQ=
Specifies the maximum number of outer iterations for the Dantzig-Wolfe decomposition algorithm	MAXITER=

You can specify the following decomp-options:

ABSOBJGAP=number ABSOLUTEOBJECTIVEGAP=number

specifies a stopping criterion for the continuous bound of the decomposition. When the absolute difference between the master objective and the best dual bound falls below number, the Dantzig-Wolfe decomposition algorithm stops adding columns. The value of number can be any nonnegative number. The default value is the value of the OPTTOL= main solver option.

BLOCKS=CAS-libref.data-table

specifies (for OPTLP and OPTMILP procedures only) the input data table that contains block definitions to use in the Dantzig-Wolfe decomposition algorithm if METHOD=USER. For more information, see the section The BLOCKS= Data Table in PROC OPTMILP and PROC OPTLP. To specify blocks in PROC OPTMODEL, use the .block constraint suffix instead (see the section The .block Constraint Suffix in PROC OPTMODEL). libref.data-table is a two-level name, where libref refers to the library, and data-table specifies the name of the input data table. For more information about this two-level name, see the section Using CAS Sessions and CAS Engine Librefs in Chapter 3, Shared Concepts.

HYBRID=FALSE | TRUE

specifies whether to first process the root node by using standard MILP techniques, as described in the section Details: MILP Solver. You can specify the following values:

FALSE: disables root processing by using standard MILP techniques.
TRUE: enables root processing by using standard MILP techniques.

By default, HYBRID=TRUE if METHOD=AUTO or METHOD=COMMUNITY, and HYBRID=FALSE otherwise.

LOGFREQ=number

specifies (for MILP problems only) how often to print information in the continuous iteration log. The value of number can be any nonnegative 32-bit integer. The default value of number is 10. If number is 0, then the iteration log is disabled. If number is positive, then an entry is made in the log at the first iteration, at the last iteration, and at intervals that are dictated by the value of number. An entry is also made each time a better integer solution or improved bound is found.

LOGLEVEL=AUTOMATIC | NONE | BASIC | MODERATE | AGGRESSIVE

controls the amount of information that the Dantzig-Wolfe decomposition algorithm displays in the SAS log.

You can specify the following values for an LP:

AUTOMATIC: prints the continuous iteration log at the interval dictated by the LOGFREQ= main solver option.
NONE: turns off printing of all the Dantzig-Wolfe decomposition algorithm messages to the SAS log.
BASIC: prints the continuous iteration log at the interval dictated by the LOGFREQ= main solver option.
MODERATE: prints the continuous iteration log and summary information for each iteration at the interval dictated by the LOGFREQ= main solver option.
AGGRESSIVE: prints the continuous iteration log and detailed information for each iteration at the interval dictated by the LOGFREQ= main solver option.

You can specify the following values for a MILP:

AUTOMATIC: prints the continuous iteration log for the root node at the interval dictated by the LOGFREQ= option in the DECOMP statement. Prints the branch-and-bound node log at the interval dictated by the LOGFREQ= main solver option.
NONE: turns off printing of all the Dantzig-Wolfe decomposition algorithm messages to the SAS log.
BASIC: prints the continuous iteration log for each branch-and-bound node at the interval dictated by the LOGFREQ= option in the DECOMP statement.
MODERATE: prints the continuous iteration log and summary information for each iteration of each branch-and-bound node at the interval dictated by the LOGFREQ= option in the DECOMP statement.
AGGRESSIVE: prints the continuous iteration log and detailed information for each iteration of each branch-and-bound node at the interval dictated by the LOGFREQ= option in the DECOMP statement.

By default, LOGLEVEL=AUTOMATIC for both LPs and MILPs.

MAXBLOCKS=number

specifies the maximum number of blocks to allow. If the defined number of blocks exceeds number, the algorithm creates superblocks by using a very simple round-robin scheme. The value of number can be any positive 32-bit integer. The default is the largest number that can be represented by a 32-bit integer.

MAXITER=number

specifies (for MILP problems only) the maximum number of outer iterations for the Dantzig-Wolfe decomposition algorithm. The value of number can be any positive 32-bit integer. The default is the largest number that can be represented by a 32-bit integer.

specifies the block-specification method. You can specify the following values:

AUTO: attempts to find a block-angular structure in the constraint matrix by using matrix-stretching techniques similar to those described in Grcar (1990) and Aykanat, Pinar, and Çatalyürek (2004). The NBLOCKS= and NBLOCKSRANGE= options specify the range of the number of blocks into which the algorithm attempts to decompose the constraint matrix. If the algorithm fails to find a decomposition, the MILP solver is called directly.
COMMUNITY: attempts to find a block-angular structure in the constraint matrix by using community detection algorithms similar to those described in Khaniyev, Elhedhli, and Erenay (2018). You can use the matrix-stretching techniques from METHOD=AUTO in conjunction with the community detection algorithms by specifying the NBLOCKS= or NBLOCKSRANGE= option (or both). If the algorithm fails to find a decomposition, the MILP solver is called directly.
CONCOMP: attempts to find a block-diagonal (not block-angular) structure in the constraint matrix. Unless your problem separates into completely independent problems with no linking constraints, this method finds only one block and hence is equivalent to calling the MILP solver directly.
NETWORK: attempts to find an embedded network similar to what is described in the section The Network Simplex Algorithm. The weakly connected components of this network are used as the blocks.
SET: attempts to find a set partitioning or set covering structure in the constraint matrix and defines this as the master (linking) constraints. The weakly connected components of the remaining constraints are used as the blocks.
USER: uses a user-defined method to specify which rows belong to which blocks (subproblems). In PROC OPTMODEL, use the .block constraint suffix. In PROC OPTLP and PROC OPTMILP, use the BLOCKS= data table instead.

By default, METHOD=USER if blocks are defined, and an automated method which first runs METHOD=AUTO and then runs METHOD=COMMUNITY, otherwise.

NBLOCKS=n NUMBLOCKS=n

specifies the number of blocks to search for when using automated detection methods, where n can be any positive number less than or equal to the number of rows in the presolved model. If the NUMBLOCKSRANGE=r option is specified, then the value of n specifies the starting point and n+r specifies the ending point for the search. If the algorithm fails to find a decomposition that contains at least two blocks, then the standard MILP solver is called directly. By default, NBLOCKS=2 when METHOD=AUTO; when METHOD=COMMUNITY, NBLOCKS=0 by default.

NBLOCKSRANGE=r NUMBLOCKSRANGE=r

specifies the range for the number of blocks to search for when using automated detection methods, where r can be any positive number less than or equal to the number of rows in the presolved model. If the NUMBLOCKS=n option is specified, then the value of n specifies the starting point and n+r specifies the ending point for the search. By default, NBLOCKSRANGE=20 when METHOD=AUTO; when METHOD=COMMUNITY, NBLOCKSRANGE=0 by default.

NTHREADS=number NUMTHREADS=number

specifies the number of block threads to use in the Dantzig-Wolfe decomposition algorithm. The value of the NTHREADS= option in the main solver statement serves as the overall capacity for the number of active threads that can run at one time. By default, the number of block threads is , where p is the value of the NTHREADS= option in the main solver statement, d is the value of the NTHREADS= option in the DECOMP statement, and b is the number of blocks that the Dantzig-Wolfe decomposition algorithm sets or finds.

RELOBJGAP=number

specifies the relative objective gap as a stopping criterion. The relative objective gap is based on the master objective (MasterObjective) and the best dual bound (BestBound); it is equal to

StartAbsoluteValue MasterObjective minus BestBound EndAbsoluteValue slash left-parenthesis 1 upper E minus minus 10 plus StartAbsoluteValue BestBound EndAbsoluteValue right-parenthesis

When this value becomes smaller than the specified gap size number, the Dantzig-Wolfe decomposition algorithm stops adding columns. The value of number can be any nonnegative number. For LP, the default value is 0; for MILP, the default value is 1E–4.

Last updated: June 22, 2026