The Decomposition Algorithm

Decomposition Algorithm Options in the PROC OPTMILP Statement or the SOLVE WITH MILP Statement in PROC OPTMODEL

To solve a mixed integer linear program, you can specify the decomposition algorithm in a SOLVE WITH MILP statement in the OPTMODEL procedure or in a PROC OPTMILP statement in the OPTMILP procedure. To control the overall decomposition algorithm, you can specify one or more of the MILP solver options shown in Table 15.2. (As indicated, you can specify some options only in the PROC OPTMILP statement.)

The options in Table 15.2 control the overall process flow for solving a mixed integer linear program, and they are equivalent to the options that are used in the OPTMILP and OPTMODEL procedures with standard methods. These options are called main solver options in this chapter. They are described in detail in the section Syntax: MILP Solver and the section Syntax: OPTMILP Procedure.

The HYBRID= option in the DECOMP statement indicates the processing mode for the root node of the branch-and-bound search tree. When HYBRID=ON, the root node is first processed using standard MILP techniques, as described in the section Details: MILP Solver. The default setting for the decomposition algorithm is HYBRID=OFF. In this case, the root processing is done solely by the decomposition algorithm, and several of the direct MILP options are ignored. These options are indicated in Table 15.2 in the column Ignored HYBRID=OFF.

Table 15.2: MILP Options in the PROC OPTMILP Statement or SOLVE WITH MILP Statement

Description	option	Ignored
		HYBRID=OFF
Data Set Options (OPTMILP procedure only)
Specifies the input data set	DATA=
Specifies the constraint activities output data set	DUALOUT=
Specifies whether the model is a maximization or minimization problem	OBJSENSE=
Specifies the primal solution input data set (warm start)	PRIMALIN=
Specifies the primal solution output data set	PRIMALOUT=
Presolve Option
Specifies the type of presolve	PRESOLVER=
Control Options
Specifies the stopping criterion based on an absolute objective gap	ABSOBJGAP=
Emphasizes feasibility or optimality	EMPHASIS=	X
Specifies the maximum violation of variables and constraints	FEASTOL=
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 in determining the optimality of nodes in the branch-and-bound tree	OPTTOL=
Uses the input primal solution (warm start) (OPTMODEL procedure only)	PRIMALIN
Enables or disables printing summary (OPTMILP procedure only)	PRINTLEVEL=
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=	X
Specifies the stopping criterion based on target objective value	TARGET=	X
Specifies whether time units are CPU time or real time	TIMETYPE=
Heuristics Option
Specifies the primal heuristics level	HEURISTICS=
Search Options
Specifies the number of pricing iterations performed on each variable in the 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 the branching variable	VARSEL=
Cut Options
Specifies the cut level for all cuts	ALLCUTS=	X
Specifies the clique cut level	CUTCLIQUE=	X
Specifies the flow cover cut level	CUTFLOWCOVER=	X
Specifies the flow path cut level	CUTFLOWPATH=	X
Specifies the Gomory cut level	CUTGOMORY=	X
Specifies the generalized upper bound (GUB) cover cut level	CUTGUB=	X
Specifies the implied bounds cut level	CUTIMPLIED=	X
Specifies the knapsack cover cut level	CUTKNAPSACK=	X
Specifies the lift-and-project cut level	CUTLAP=	X
Specifies the mixed lifted 0-1 cut level	CUTMILIFTED=	X
Specifies the mixed integer rounding (MIR) cut level	CUTMIR=	X
Specifies the multicommodity network flow cut level	CUTMULTICOMMODITY=	X
Specifies the row multiplier factor for cuts	CUTSFACTOR=	X
Specifies the overall cut aggressiveness	CUTSTRATEGY=	X
Specifies the zero-half cut level	CUTZEROHALF=	X

The following search options, listed in Table 15.2, have a different interpretation from what is described in the MILP solver sections.

LOGFREQ=number PRINTFREQ=number: specifies how often information is printed in the node log. The value of number can be any nonnegative integer up to the largest four-byte signed integer, which is $2^{31} - 1$ . The default value is 10. If you set number to 0, then the node log is disabled. If number is positive, then an entry is made in the node log at the first node, at the last node, and at intervals dictated by the value of number. An entry is also made in the node log each time the solver finds a better integer solution or improved bound.
STRONGITER=number | AUTOMATIC: specifies the number of pricing iterations that are performed for each variable in the candidate list when you use the strong branching variable selection strategy. The value of number can be any positive integer up to the largest four-byte signed integer, which is $2^{31} - 1$ . If you specify the keyword AUTOMATIC or the value –1, the MILP solver uses the default value, which is calculated automatically.

The following search option, listed in Table 15.2, has a different set of options from what is described in the MILP solver sections.

VARSEL=number | string

specifies the rule for selecting the branching variable. The values of string and the corresponding values of number are listed in Table 15.3.

Table 15.3: Values for VARSEL= Option

number	string	Description
–1	AUTOMATIC	Uses automatic branching variable selection.
0	MAXINFEAS	Selects the variable in the original compact formulation with maximum infeasibility.
2	PSEUDO	Selects the variable in the original compact formulation that maximizes the weighted up and down pseudocosts.
3	STRONG	Selects the variable in the original compact formulation that maximizes the estimated improvement in the objective value based on strong branching.
4	RYANFOSTER	When appropriate, uses a specialized branching rule known as Ryan-Foster branching.

The default value is AUTOMATIC. For more information about variable selection, see the sections Variable Selection and Special Case: Identical Blocks and Ryan-Foster Branching.