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 threads to use in the overall 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 be used by 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 0 elsewhere.

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 0 elsewhere.

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.

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 threads that are used for processing. In single-machine mode, this is equivalent to the setting of the NTHREADS= option in the PERFORMANCE statement or the DECOMP statement. In distributed mode, this is equivalent to the number of compute nodes that are set using the NODES= option in the PERFORMANCE statement times the number of threads set for each compute node. For more information about parallel execution, see the section Parallel Processing.

NTHREADS=number

specifies the number of threads to be used by the overall block decomposition algorithm. This overrides the NTHREADS= option in the PERFORMANCE statement, which is described in the section PERFORMANCE Statement.

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.