The Decomposition Algorithm

DECOMP_SUBPROB Statement

DECOMP_SUBPROB <decomp-subprob-options>;

SUBPROB <decomp-subprob-options>;

The DECOMP_SUBPROB statement controls the subproblem.

Table 15.16 summarizes the options available for the decomposition algorithm in the DECOMP_SUBPROB statement when the subproblem algorithm chosen is an LP algorithm. (As indicated, you can specify the PRINTLEVEL= option only in the OPTLP procedure.) For descriptions of these options, see the section LP Solver Options in Chapter 7: The Linear Programming Solver and the section PROC OPTLP Statement in Chapter 12: The OPTLP Procedure. Some options have different defaults when you use the decomposition algorithm, as shown in Table 15.16.

Table 15.16: Options in the DECOMP_SUBPROB Statement Used with an LP Algorithm

Description	decomp-subprob-option	Different
		Default
Algorithm Option
Specifies the subproblem algorithm	ALGORITHM=	PS (METHOD=USER) NETWORK_PURE (METHOD=NETWORK)^†
Presolve Option
Controls the dualization of the problem	DUALIZE=	OFF
Specifies, for the first subproblem solve only, the type of presolve	INITPRESOLVER=
Specifies the type of presolve	PRESOLVER=	NONE (ALGORITHM=PS)^†
Control Options
Specifies the feasibility tolerance	FEASTOL=	1E–7
Specifies how frequently to print the solution progress	LOGFREQ=
Specifies the level of detail of solution progress to print in the log	LOGLEVEL=
Specifies the maximum number of iterations	MAXITER=
Specifies the time limit for the optimization process	MAXTIME=
Specifies the number of threads to use in the subproblem solver	NTHREADS=
Specifies the optimality tolerance	OPTTOL=	1E–7
Enables or disables printing summary (OPTLP procedure only)	PRINTLEVEL=
Specifies the initial seed for the random number generator	SEED=
Specifies whether time units are CPU time or real time	TIMETYPE=
Simplex Algorithm Options
Specifies the type of initial basis	BASIS=	WARMSTART (ALGORITHM=PS)^†
Specifies the type of pricing strategy	PRICETYPE=
Specifies the queue size for determining entering variable	QUEUESIZE=
Enables or disables scaling of the problem	SCALE=
Interior Point Algorithm Options
Enables or disables interior crossover	CROSSOVER=
Specifies the stopping criterion based on duality gap	STOP_DG=
Specifies the stopping criterion based on dual infeasibility	STOP_DI=
Specifies the stopping criterion based on primal infeasibility	STOP_PI=

† When METHOD=USER is specified in the DECOMP statement, ALGORITHM=PS, PRESOLVER=NONE, and BASIS=WARMSTART by default. These defaults are motivated by the fact that primal feasibility of the subproblem is preserved when the objective is changed, so a warm start from the previous optimal basis tends to be more efficient than solving the subproblem from scratch in each iteration. When METHOD=NETWORK, ALGORITHM=NETWORK_PURE by default because each subproblem is a pure network, causing the specialized pure network solver to usually be the most efficient choice.

Table 15.17 summarizes the options available in the DECOMP_SUBPROB statement when the subproblem algorithm chosen is a MILP algorithm. When the subproblem consists of multiple blocks (a block-diagonal structure), these settings apply to all subproblems. For descriptions of these options, see the section MILP Solver Options in Chapter 8: The Mixed Integer Linear Programming Solver and the section PROC OPTMILP Statement in Chapter 13: The OPTMILP Procedure.

Table 15.17: Options in the DECOMP_SUBPROB Statement Used with a MILP Algorithm

Description	decomp-subprob-option	Different
		Default
Algorithm Option
Specifies the subproblem algorithm	ALGORITHM=
Presolve Option
Specifies, for the first subproblem solve only, the type of presolve	INITPRESOLVER=
Specifies the type of presolve	PRESOLVER=
Control Options
Specifies the stopping criterion based on absolute objective gap	ABSOBJGAP=
Emphasizes feasibility or optimality	EMPHASIS=
Specifies the maximum violation on variables and constraints	FEASTOL=	1E–7
Specifies the maximum allowed difference between an integer variable’s value and an integer	INTTOL=
Specifies how frequently to print the node log	LOGFREQ=
Specifies the level of detail of solution progress to print in the log	LOGLEVEL=
Specifies the maximum number of nodes to be processed	MAXNODES=
Specifies the maximum number of solutions to be found	MAXSOLS=
Specifies the time limit for the optimization process	MAXTIME=
Specifies the number of threads to use in the subproblem solver	NTHREADS=
Specifies the tolerance used when deciding on the optimality of nodes in the branch-and-bound tree	OPTTOL=	1E–7
Specifies whether to use the previous best primal solution as a warm start	PRIMALIN=
Specifies the probing level	PROBE=
Specifies the stopping criterion based on relative objective gap	RELOBJGAP=
Specifies the scale of the problem matrix	SCALE=
Specifies the stopping criterion based on target objective value	TARGET=
Specifies whether time units are CPU time or real time	TIMETYPE=
Heuristics Option
Specifies the primal heuristics level	HEURISTICS=
Search Options
Specifies the level of conflict search	CONFLICTSEARCH=
Specifies the node selection strategy	NODESEL=
Specifies the restarting strategy	RESTARTS=
Specifies the initial seed for the random number generator	SEED=
Specifies the number of simplex iterations performed on each variable in strong branching strategy	STRONGITER=
Specifies the number of candidates for strong branching	STRONGLEN=
Specifies the level of symmetry detection	SYMMETRY=
Specifies the rule for selecting branching variable	VARSEL=
Cut Options
Specifies the cut level for all cuts	ALLCUTS=
Specifies the clique cut level	CUTCLIQUE=
Specifies the flow cover cut level	CUTFLOWCOVER=
Specifies the flow path cut level	CUTFLOWPATH=
Specifies the Gomory cut level	CUTGOMORY=
Specifies the generalized upper bound (GUB) cover cut level	CUTGUB=
Specifies the implied bounds cut level	CUTIMPLIED=
Specifies the knapsack cover cut level	CUTKNAPSACK=
Specifies the lift-and-project cut level	CUTLAP=
Specifies the mixed lifted 0-1 cut level	CUTMILIFTED=
Specifies the mixed integer rounding (MIR) cut level	CUTMIR=
Specifies the row multiplier factor for cuts	CUTSFACTOR=
Specifies the overall cut aggressiveness	CUTSTRATEGY=
Specifies the zero-half cut level	CUTZEROHALF=

The following options, listed in Table 15.16 and Table 15.17, are specific to the DECOMP_SUBPROB statement and are not described in the LP or MILP solver sections.

ALGORITHM=string SOLVER=string SOL=string

specifies one of the algorithms shown in Table 15.18 (the valid abbreviated value for each string is shown in parentheses).

Table 15.18: Values for ALGORITHM= Option

string	Description
PRIMAL (PS)	Uses the primal simplex algorithm.
DUAL (DS)	Uses the dual simplex algorithm.
NETWORK (NS)	Uses the network simplex algorithm.
NETWORK_PURE (NSPURE)	Uses the network simplex algorithm for pure networks.
INTERIORPOINT (IP)	Uses the interior point algorithm.
MILP	Uses the mixed integer linear solver.

The default is NETWORK_PURE if METHOD=NETWORK, MILP for mixed integer linear programming subproblems, or PS for linear programming subproblems.

INITPRESOLVER=number | string INITPRESOL=number | string

specifies, for the first subproblem solve only, presolve conditions as listed in Table 15.19.

Table 15.19: Values for INITPRESOLVER= Option

number	string	Description
–1	AUTOMATIC	Applies the default level of presolve processing
0	NONE	Disables presolver
1	BASIC	Performs minimal presolve processing
2	MODERATE	Applies a higher level of presolve processing
3	AGGRESSIVE	Applies the highest level of presolve processing

The default is AUTOMATIC.

NTHREADS=number

specifies the number of threads to use in the subproblem solver (if the chosen solver method supports multithreading). By default, the number of threads is either 1 or the setting that is used for the NTHREADS= option in the DECOMP statement divided by the number of blocks in the decomposition (rounded down), whichever is greater.

PRIMALIN=number | string PIN=number | string

specifies (for MILP problems only) whether the MILP solver is to use the values of the previous best solution’s variables as a starting solution (warm start). If the MILP solver finds that the input solution is feasible, then the input solution provides an incumbent solution and a bound for the branch-and-bound algorithm. If the solution is not feasible, the MILP solver tries to repair it. When it is difficult to find a good integer-feasible solution for a problem, warm start can reduce solution time significantly. Table 15.20 describes the valid values of the PRIMALIN= option.

Table 15.20: Values for PRIMALIN= Option

number	string	Description
0	OFF	Ignores the previous solution.
1	ON	Starts from the previous solution.

The default is ON.