The Decomposition Algorithm

DECOMP_SUBPROB Statement

DECOMP_SUBPROB <decomp-subprob-options> ;

SUBPROB <decomp-subprob-options> ;

The DECOMP_SUBPROB statement controls the subproblem.

Table 14.14 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 6: The Linear Programming Solver and the section PROC OPTLP Statement in Chapter 11: The OPTLP Procedure. Some options have different defaults when you use the decomposition algorithm, as shown in Table 14.14.

Table 14.14: 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 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 14.15 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 7: The Mixed Integer Linear Programming Solver and the section PROC OPTMILP Statement in Chapter 12: The OPTMILP Procedure.

Table 14.15: 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=

 

Specifies the cutoff value for node removal

CUTOFF=

 

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 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 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 14.14 and Table 14.15, 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 14.16 (the valid abbreviated value for each string is shown in parentheses).

Table 14.16: 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 14.17.

Table 14.17: 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.

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 14.18 describes the valid values of the PRIMALIN= option.

Table 14.18: Values for PRIMALIN= Option

number

string

Description

0

OFF

Ignores the previous solution.

1

ON

Starts from the previous solution.


The default is ON.