The Decomposition Algorithm

DECOMP Statement

DECOMP <decomp-options>;

The DECOMP statement controls the overall decomposition algorithm.

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

Table 15.4: Options in the DECOMP Statement

Description	decomp-option
Data Set Options (OPTLP and OPTMILP procedures only)
Specifies the blocks input data set	BLOCKS=
Control Options
Specifies the stopping criterion based on an absolute objective gap	ABSOBJGAP=
Specifies the frequency of removing ineffective columns from the master LP	COMPRESSFREQ=
Specifies whether or not to first process the root node by using standard MILP techniques	HYBRID=
Specifies whether to initialize the columns by solving each block with the original cost vector	INITVARS=
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 maximum number of new columns to allow into the master each pass	MAXCOLSPASS=
Specifies the maximum amount of time spent in the decomposition algorithm	MAXTIME=
Specifies the decomposition algorithm method	METHOD=
Specifies the number of blocks to search for by using METHOD=AUTO	NBLOCKS=
Specifies the number of block threads to use in the decomposition algorithm	NTHREADS=
Specifies the stopping criterion based on relative objective gap	RELOBJGAP=
Control Options (MILP only)
Specifies how frequently to print the continuous iteration log	LOGFREQ=
Specifies whether the master problem is solved as a MILP with the current set of columns at the beginning of phase II	MASTER_IP_BEG=
Specifies whether the master problem is solved as a MILP with the current set of columns at the end of phase II	MASTER_IP_END=
Specifies the frequency of solving the master problem as a MILP with the current set of columns	MASTER_IP_FREQ=
Specifies the maximum number of outer iterations for the decomposition algorithm	MAXITER=

The following list describes the decomp-options in detail.

ABSOBJGAP=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 the value of number, the 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=SAS-data-set

specifies (for OPTLP and OPTMILP procedures only) the input data set that contains block definitions to use in the decomposition algorithm if METHOD=USER. See the section The BLOCKS= Data Set in PROC OPTMILP and PROC OPTLP for more information. To specify blocks in PROC OPTMODEL, use the .block constraint suffix instead (see the section The .block Constraint Suffix in PROC OPTMODEL).

COMPRESSFREQ=number

removes ineffective columns from the master LP after every number of iterations. The frequency, number, is an integer between 0 and the largest four-byte signed integer, which is $2^{31} - 1$ . The default value is 0.

HYBRID=number | string

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

Table 15.5 describes the valid values of the HYBRID= option.

Table 15.5: Values for HYBRID= Option

number	string	Description
0	OFF	Disables root processing by standard MILP techniques.
1	ON	Enables root processing by standard MILP techniques.

The default is OFF.

INITVARS=number | string

specifies whether to initialize the columns by using the original cost vector to solve each block.

Table 15.6 describes the valid values of the INITVARS= option.

Table 15.6: Values for INITVARS= Option

number	string	Description
0	OFF	Disables initializing the columns by using the original cost vector to solve each block.
1	ON	Enables initializing the columns by using the original cost vector to solve each block.

This option must be set to ON when used with METHOD=CONCOMP. The default is ON.

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 number up to the largest four-byte signed integer, which is $2^{31} - 1$ . The default value of number is 10. If number is set to 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=number | string

controls the amount of information that is displayed in the SAS log by the decomposition algorithm. Table 15.7 and Table 15.8 provide the valid values for this option and a description of what is displayed in the log when an LP and a MILP, respectively, is solved.

Table 15.7: Values for LOGLEVEL= Option for an LP

number	string	Description
–1	AUTOMATIC	Prints the continuous iteration log at the interval dictated by the LOGFREQ= main solver option.
0	NONE	Turns off printing of all of the decomposition algorithm messages to the SAS log.
1	BASIC	Prints the continuous iteration log at the interval dictated by the LOGFREQ= main solver option.
2	MODERATE	Prints the continuous iteration log and summary information for each iteration at the interval dictated by the LOGFREQ= main solver option.
3	AGGRESSIVE	Prints the continuous iteration log and detailed information for each iteration at the interval dictated by the LOGFREQ= main solver option.

Table 15.8: Values for LOGLEVEL= Option for a MILP

number	string	Description
–1	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.
0	NONE	Turns off printing of all of the decomposition algorithm messages to the SAS log.
1	BASIC	Prints the continuous iteration log for each branch-and-bound node at the interval dictated by the LOGFREQ= option in the DECOMP statement.
2	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.
3	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.

The default is AUTOMATIC for both LPs and MILPs.

MASTER_IP_BEG=number | string

specifies (for MILP problems only) whether the master problem is solved as a MILP with the current set of columns at the beginning of phase II. Table 15.9 describes the valid values of the MASTER_IP_BEG= option.

Table 15.9: Values for MASTER_IP_BEG= Option

number	string	Description
0	OFF	Disables solving the master as a MILP at the beginning of phase II.
1	ON	Enables solving the master as a MILP at the beginning of phase II.

The default is ON in the root node and automatically determines whether to call the heuristic in the branch-and-bound tree.

MASTER_IP_END=number | string

specifies (for MILP problems only) whether the master problem is solved as a MILP with the current set of columns at the end of phase II. Table 15.10 describes the valid values of the MASTER_IP_END= option.

Table 15.10: Values for MASTER_IP_END= Option

number	string	Description
0	OFF	Disables solving the master as a MILP at the end of phase II.
1	ON	Enables solving the master as a MILP at the end of phase II.

The default is ON in the root node and automatically determines whether to call the heuristic in the branch-and-bound tree.

MASTER_IP_FREQ=number

solves the master problem (for MILP problems only) as a MILP with the current set of columns after every number iterations. The frequency, number, is an integer between 0 and the largest four-byte signed integer, which is $2^{31} - 1$ . The default is 10 in the root node and 0 elsewhere.

MAXBLOCKS=number

specifies the maximum number of blocks to allow. If the defined number of blocks exceeds number, the algorithm creates superblocks using a very simple round-robin scheme. The value of number can be any positive number; the default value is the positive number that has the largest absolute value that can be represented in your operating environment.

MAXCOLSPASS=number

specifies the maximum number of new columns to allow into the master at each pass. This option is disabled on the initial pass if INITVARS=1. The value of number can be any positive number; the default value is the positive number that has the largest absolute value that can be represented in your operating environment.

MAXITER=number

specifies (for MILP problems only) the maximum number of outer iterations for the decomposition algorithm. The value number can be any integer between 1 and the largest four-byte signed integer, which is $2^{31} - 1$ . If you do not specify this option, the procedure does not stop based on the number of iterations performed.

MAXTIME=number

specifies an upper limit of number seconds of time for the decomposition algorithm. The value of the TIMETYPE= main solver option determines the type of units used. If you do not specify this option, the procedure does not stop based on the amount of time elapsed. The value of number can be any positive number; the default value is the positive number that has the largest absolute value that can be represented in your operating environment.

METHOD=string

specifies the decomposition algorithm method as shown in Table 15.11.

Table 15.11: Values for METHOD= Option

string	Description
AUTO	The algorithm attempts to find a block-angular structure in the constraint matrix by using matrix-stretching techniques similar to what is described in Grcar (1990) and Aykanat, Pinar, and Çatalyürek (2004). The NBLOCKS= option specifies 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.
CONCOMP	The algorithm 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	The algorithm 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	The algorithm 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	The user defines 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 set instead.

The default is USER if blocks are defined and AUTO otherwise.

NBLOCKS=number

specifies the initial number of blocks to search for when you specify METHOD=AUTO. If the algorithm is unable to find a block-angular structure that contains this number of blocks, it repeatedly attempts to find an appropriate structure that contains half the previously attempted number of blocks. If the algorithm fails to find a decomposition that contains at least two blocks, then the standard MILP solver is called directly. The value of number can be any positive number less than or equal to the number of rows in the presolved model; the default value is the number of block threads that are used for processing. In single-machine mode, this is equivalent to the value of the NTHREADS= option in the DECOMP statement. In distributed mode, this is equivalent to the number of compute nodes that you specify in the NODES= option in the PERFORMANCE statement times the number of threads that you specify for each compute node. For more information about parallel execution, see the section Parallel Processing.

NTHREADS=number

specifies the number of block threads to use in the decomposition algorithm. The value of the NTHREADS= option in the PERFORMANCE statement, which is described in the section PERFORMANCE 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 $t = \min (p,d,b)$ , where p is the value of the NTHREADS= option in the PERFORMANCE statement, d is the value of the NTHREADS= option in the DECOMP statement, and b is the number of blocks that the decomposition algorithm sets of 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

$\mid \mbox{MasterObjective} - \mbox{BestBound}\mid / \left(\mbox{1E$-$10}~ + \mid \mbox{BestBound}\mid \right)$

When this value becomes smaller than the specified gap size number, the 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.