The Decomposition Algorithm

DECOMPSUBPROB Statement

DECOMPSUBPROB <subprob-options>;

DECOMPOSITIONSUBPROB <subprob-options>;

SUBPROB <subprob-options>;

The DECOMPSUBPROB statement controls the subproblem.

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

Table 18.6: Options in the DECOMPSUBPROB Statement Used with an LP Algorithm

Description	subprob-option	Different
		Default
Algorithm Option
Specifies the subproblem algorithm	ALGORITHM=	†
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^†
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=	NONE
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^†
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 a duality gap	DUALITYGAP=

† When you specify METHOD=USER, METHOD=AUTO or METHOD=COMMUNITY in the DECOMP statement, ALGORITHM=PS, PRESOLVER=NONE, and BASIS=WARMSTART by default. The reason for these defaults is 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 at each iteration. When METHOD=NETWORK, ALGORITHM=NETWORKPURE by default because each subproblem is a pure network, causing the specialized pure network solver to usually be the most efficient choice. When METHOD=CONCOMP, ALGORITHM=DS by default because dual simplex generally has the best performance on linear programs and, in this case, one outer iteration is sufficient (that is, warm starts are not required).

Table 18.7 summarizes the options available in the DECOMPSUBPROB statement when the chosen subproblem algorithm 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 14: The Mixed Integer Linear Programming Solver, and the section PROC OPTMILP Statement in Chapter 7: The OPTMILP Procedure.

Table 18.7: Options in the DECOMPSUBPROB Statement Used with a MILP Algorithm

Description	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 an absolute objective gap	ABSOBJGAP=
Emphasizes feasibility or optimality	EMPHASIS=
Specifies the maximum violation on variables and constraints	FEASTOL=	1E–7
Specifies the maximum difference allowed 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 process	MAXNODES=
Specifies the maximum number of solutions to find	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 to use in determining 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 a relative objective gap	RELOBJGAP=
Specifies the scale of the problem matrix	SCALE=
Specifies the initial seed for the random number generator	SEED=
Specifies the stopping criterion based on a 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 number of iterations to perform for strong branching	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 multicommodity network flow cut level	CUTMULTICOMMODITY=
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 18.6 and Table 18.7, are specific to the DECOMPSUBPROB statement and are not described in the LP or MILP solver sections:

ALGORITHM=string SOLVER=string SOL=string

specifies the algorithm to use for the subproblem solves. You can specify the following values (the valid abbreviated value for each string follows the vertical bar):

PRIMAL | PS: uses the primal simplex algorithm.
DUAL | DS: uses the dual simplex algorithm.
NETWORK | NS: uses the network simplex algorithm.
NETWORKPURE | NSPURE: uses the network simplex algorithm for pure networks.
INTERIORPOINT | IP: uses the interior point algorithm.
MILP: uses the mixed integer linear solver.

By default, ALGORITHM=NETWORKPURE if METHOD=NETWORK, ALGORITHM=MILP for mixed integer linear programming subproblems, and ALGORITHM=PS for linear programming subproblems.

specifies, for the first subproblem solve only, the presolve level. You can specify the following values:

AUTOMATIC: applies the default level of presolve processing.
NONE: disables the presolver.
BASIC: performs minimal presolve processing.
MODERATE: applies a higher level of presolve processing.
AGGRESSIVE: applies the highest level of presolve processing.

By default, INITPRESOLVER=AUTOMATIC.

NTHREADS=number NUMTHREADS=number

specifies the number of threads to use in the subproblem solver (if the selected solver method supports multithreading). 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 subproblem threads is , where p is the value of the NTHREADS= option in the main solver statement; , which is the number of blocks being processed simultaneously; d is the number of block threads; and m is the number of compute nodes (which can be more than one, when you run the decomposition algorithm in distributed mode).

PRIMALIN=FALSE | TRUE PIN=FALSE | TRUE

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, a warm start can reduce solution time significantly. You can specify the following values:

FALSE: ignores the previous solution.
TRUE: starts from the previous solution.

By default, PRIMALIN=TRUE.

Last updated: June 14, 2018