The Mixed Integer Linear Programming Solver: MILP Solver Options

MILP Solver Options

This section describes the options that are recognized by the MILP solver in PROC OPTMODEL. These options can be specified after a forward slash (/) in the SOLVE statement, provided that the MILP solver is explicitly specified using a WITH clause. For example, the following line could appear in PROC OPTMODEL statements:

   solve with milp / allcuts=aggressive maxnodes=10000 primalin;

Presolve Option

PRESOLVER=option | num

specifies a presolve option or its corresponding value num, as listed in Table 6.2.

Table 6.2 Values for PRESOLVER= Option
Number	Option	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 value is AUTOMATIC.

Warm Start Option

PRIMALIN

enables you to input a starting solution in PROC OPTMODEL before invoking the MILP solver. Adding the PRIMALIN option to the SOLVE statement requests that the MILP solver use the current variable values 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. It is possible to set a variable value to the missing value '.' to mark a variable for repair. When it is difficult to find a good integer feasible solution for a problem, warm start can reduce solution time significantly.

Note: If the MILP solver produces a feasible solution, the variable values from that run can be used as the warm start solution for a subsequent run. If the warm start solution is not feasible for the subsequent run, the solver automatically tries to repair it.

Control Options

ABSOBJGAP=num

specifies a stopping criterion. When the absolute difference between the best integer objective and the objective of the best remaining node falls below the value of num, the solver stops. The value of num can be any nonnegative number; the default value is 1E–6.

CUTOFF=num

cuts off any nodes in a minimization (maximization) problem with an objective value above (below) num. The value of num can be any number; the default value is the positive (negative) number that has the largest absolute value representable in your operating environment.

EMPHASIS=option | num

specifies a search emphasis option or its corresponding value num as listed in Table 6.3.

Table 6.3 Values for EMPHASIS= Option
Number	Option	Description
0	BALANCE	Performs a balanced search
1	OPTIMAL	Emphasizes optimality over feasibility
2	FEASIBLE	Emphasizes feasibility over optimality

The default value is BALANCE.

INTTOL=num

specifies the amount by which an integer variable value can differ from an integer and still be considered integer feasible. The value of num can be any number between 0.0 and 1.0; the default value is 1E–5. The MILP solver attempts to find an optimal solution with integer infeasibility less than num. If you assign a value smaller than 1E–10 to num and the best solution found by the solver has integer infeasibility between num and 1E–10, then the solver terminates with a solution status of OPTIMAL_COND (see the section Macro Variable _OROPTMODEL_ ).

MAXNODES=num

specifies the maximum number of branch-and-bound nodes to be processed. The value of num can be any nonnegative integer up to the largest four-byte signed integer, which is $\text{[math]}$ . The default value of num is $\text{[math]}$ .

MAXSOLS=num

specifies a stopping criterion. If num solutions have been found, then the solver stops. The value of num can be any positive integer up to the largest four-byte signed integer, which is $\text{[math]}$ . The default value of num is $\text{[math]}$ .

MAXTIME=num

specifies the maximum time allowed for the MILP solver to find a solution. The type of time, either CPU time or real time, is determined by the value of the TIMETYPE= option. The value of num 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.

PRINTFREQ=num

specifies how often information is printed in the node log. The value of num can be any nonnegative number up to the largest four-byte signed integer, which is $\text{[math]}$ . The default value of num is 100. If num is set to 0, then the node log is disabled. If num 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 num. An entry is also made each time a better integer solution is found.

PRINTLEVEL2=option | num

controls the amount of information displayed in the SAS log by the MILP solver, from a short description of presolve information and summary to details at each node. Table 6.4 describes the valid values for this option.

Table 6.4 Values for PRINTLEVEL2= Option
Number	Option	Description
0	NONE	Turns off all solver-related messages to SAS log
1	BASIC	Displays a solver summary after stopping
2	MODERATE	Prints a solver summary and a node log by using the interval dictated by the PRINTFREQ= option
3	AGGRESSIVE	Prints a detailed solver summary and a node log by using the interval dictated by the PRINTFREQ= option

The default value is MODERATE.

PROBE=option | num

specifies a probing option or its corresponding value num, as listed in the following table:

Table 6.5 Values for PROBE= Option
Number	Option	Description
–1	AUTOMATIC	Uses the probing strategy determined by the MILP solver
0	NONE	Disables probing
1	MODERATE	Uses probing moderately
2	AGGRESSIVE	Uses probing aggressively

The default value is AUTOMATIC.

RELOBJGAP=num

specifies a stopping criterion based on the best integer objective (BestInteger) and the objective of the best remaining node (BestBound). The relative objective gap is equal to

$\text{[math]}$

When this value becomes smaller than the specified gap size num, the solver stops. The value of num can be any number between 0 and 1; the default value is 1E–4.

SCALE=option

indicates whether to scale the problem matrix. SCALE= can take either of the values AUTOMATIC (–1) and NONE (0). SCALE=AUTOMATIC scales the matrix as determined by the MILP solver; SCALE=NONE disables scaling. The default value is AUTOMATIC.

TARGET=num

specifies a stopping criterion for minimization (maximization) problems. If the best integer objective is better than or equal to num, the solver stops. The value of num can be any number; the default value is the negative (positive) number that has the largest absolute value representable in your operating environment.

TIMETYPE=option $\text{[math]}$ num

specifies the units of time used by the MAXTIME= option and reported by the PRESOLVE_TIME and SOLUTION_TIME terms in the _OROPTMODEL_ macro variable. Table 6.6 describes the valid values of the TIMETYPE= option.

Table 6.6 Values for TIMETYPE= Option
Number	Option	Description
0	CPU	Specifies units of CPU time
1	REAL	Specifies units of real time

The "Optimization Statistics" table, an output of PROC OPTMODEL if option PRINTLEVEL=2 is specified in the PROC OPTMODEL statement, also includes the same time units for "Presolver Time" and "Solver Time." The other times (such as "Problem Generation Time") in the "Optimization Statistics" table are always CPU times. The default value of the TIMETYPE= option is CPU.

Heuristics Option

HEURISTICS=option | num

controls the level of primal heuristics applied by the MILP solver. This level determines how frequently primal heuristics are applied during the branch-and-bound tree search. It also affects the maximum number of iterations allowed in iterative heuristics. Some computationally expensive heuristics might be disabled by the solver at less aggressive levels. The values of option and the corresponding values of num are listed in Table 6.7.

Table 6.7 Values for HEURISTICS= Option
Number	Option	Description
–1	AUTOMATIC	Applies default level of heuristics, similar to MODERATE
0	NONE	Disables all primal heuristics
1	BASIC	Applies basic primal heuristics at low frequency
2	MODERATE	Applies most primal heuristics at moderate frequency
3	AGGRESSIVE	Applies all primal heuristics at high frequency

Setting HEURISTICS=NONE does not disable the heuristics that repair an infeasible input solution that is specified by using the PRIMALIN= option.

The default value is AUTOMATIC. For details about primal heuristics, see the section Primal Heuristics.

Search Options

NODESEL=option | num

specifies the node selection strategy option or its corresponding value num as listed in Table 6.8.

Table 6.8 Values for NODESEL= Option
Number	Option	Description
–1	AUTOMATIC	Uses automatic node selection
0	BESTBOUND	Chooses the node with the best relaxed objective (best-bound-first strategy)
1	BESTESTIMATE	Chooses the node with the best estimate of the integer objective value (best-estimate-first strategy)
2	DEPTH	Chooses the most recently created node (depth-first strategy)

The default value is AUTOMATIC. For details about node selection, see the section Node Selection.

PRIORITY=0 $\text{[math]}$ 1

indicates whether to use specified branching priorities for integer variables. PRIORITY=0 ignores variable priorities; PRIORITY=1 uses priorities when they exist. The default value is 1. See the section Branching Priorities for details.

STRONGITER=num

specifies the number of simplex iterations performed for each variable in the candidate list when the strong branching variable selection strategy is used. The value of num can be any positive number; the default value is automatically calculated by the MILP solver.

STRONGLEN=num

specifies the number of candidates used when the strong branching variable selection strategy is performed. The value of num can be any positive integer up to the largest four-byte signed integer, which is $\text{[math]}$ . The default value of num is 10.

VARSEL=option | num

specifies the rule for selecting the branching variable. The values of option and the corresponding values of num are listed in Table 6.9.

Table 6.9 Values for VARSEL= Option
Number	Option	Description
–1	AUTOMATIC	Uses automatic branching variable selection
0	MAXINFEAS	Chooses the variable with maximum infeasibility
1	MININFEAS	Chooses the variable with minimum infeasibility
2	PSEUDO	Chooses a branching variable based on pseudocost
3	STRONG	Uses strong branching variable selection strategy

The default value is AUTOMATIC. For details about variable selection, see the section Variable Selection.

Cut Options

Table 6.10 describes the option and num values for the cut options in the OPTMODEL procedure.

Table 6.10 Values for Individual Cut Options
Number	Option	Description
–1	AUTOMATIC	Generates cutting planes based on a strategy determined by the MILP solver
0	NONE	Disables generation of cutting planes
1	MODERATE	Uses a moderate cut strategy
2	AGGRESSIVE	Uses an aggressive cut strategy

You can use the ALLCUTS= option to set all cut types to the same level. You can override the ALLCUTS= value by using the options that correspond to particular cut types. For example, if you want the MILP solver to generate only Gomory cuts, specify ALLCUTS=NONE and CUTGOMORY=AUTOMATIC. If you want to generate all cuts aggressively but generate no lift-and-project cuts, set ALLCUTS=AGGRESSIVE and CUTLAP=NONE.

ALLCUTS=option | num: provides a shorthand way of setting all the cuts-related options in one setting. In other words, ALLCUTS=num is equivalent to setting each of the individual cuts parameters to the same value num. Thus, ALLCUTS=–1 has the effect of setting CUTCLIQUE=–1, CUTFLOWCOVER=–1, CUTFLOWPATH=–1, ..., CUTMIR=–1, and CUTZEROHALF=–1. Table 6.10 lists the values that can be assigned to option and num. In addition, you can override levels for individual cuts with the CUTCLIQUE=, CUTFLOWCOVER=, CUTFLOWPATH=, CUTGOMORY=, CUTGUB=, CUTIMPLIED=, CUTKNAPSACK=, CUTLAP=, CUTMILIFTED=, CUTMIR=, and CUTZEROHALF= options. If the ALLCUTS= option is not specified, then all the cuts-related options are either at their individually specified values (if the corresponding option is specified) or at their default values (if that option is not specified).
CUTCLIQUE=option | num: specifies the level of clique cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTCLIQUE= option overrides the ALLCUTS= option. The default value is AUTOMATIC.
CUTFLOWCOVER=option | num: specifies the level of flow cover cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTFLOWCOVER= option overrides the ALLCUTS= option. The default value is AUTOMATIC.
CUTFLOWPATH=option | num: specifies the level of flow path cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTFLOWPATH= option overrides the ALLCUTS= option. The default value is AUTOMATIC.
CUTGOMORY=option | num: specifies the level of Gomory cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTGOMORY= option overrides the ALLCUTS= option. The default value is AUTOMATIC.
CUTGUB=option | num: specifies the level of generalized upper bound (GUB) cover cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTGUB= option overrides the ALLCUTS= option. The default value is AUTOMATIC.
CUTIMPLIED=option | num: specifies the level of implied bound cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTIMPLIED= option overrides the ALLCUTS= option. The default value is AUTOMATIC.
CUTKNAPSACK=option | num: specifies the level of knapsack cover cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTKNAPSACK= option overrides the ALLCUTS= option. The default value is AUTOMATIC.
CUTLAP=option | num: specifies the level of lift-and-project (LAP) cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTLAP= option overrides the ALLCUTS= option. The default value is NONE.
CUTMILIFTED=option | num: specifies the level of mixed lifted 0-1 cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTMILIFTED= option overrides the ALLCUTS= option. The default value is AUTOMATIC.
CUTMIR=option | num: specifies the level of mixed integer rounding (MIR) cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTMIR= option overrides the ALLCUTS= option. The default value is AUTOMATIC.
CUTSFACTOR=num: specifies a row multiplier factor for cuts. The number of cuts added is limited to num times the original number of rows. The value of num can be any nonnegative number less than or equal to 100; the default value is 3.0.
CUTZEROHALF=option | num: specifies the level of zero-half cuts that are generated by the MILP solver. Table 6.10 lists the values that can be assigned to option and num. The CUTZEROHALF= option overrides the ALLCUTS= option. The default value is AUTOMATIC.