The OPTGRAPH Procedure

TSP Statement

  • TSP < options >;

The TSP statement invokes an algorithm that solves the traveling salesman problem.

The traveling salesman problem is described in the section Traveling Salesman Problem. The algorithm that is used to solve this problem is built around the same method as is used in PROC OPTMILP: a branch-and-cut algorithm. Many of the following options are the same as those described for the OPTMILP procedure in the SAS/OR User's Guide: Mathematical Programming.

You can specify the following options:

ABSOBJGAP=number

specifies a stopping criterion. When the absolute difference between the best integer objective and the objective of the best remaining branch-and-bound node becomes less than the value of number, the solver stops. The value of number can be any nonnegative number; the default value is 1E–6.

CONFLICTSEARCH=number | string

specifies the level of conflict search that PROC OPTGRAPH performs. The solver performs a conflict search to find clauses that result from infeasible subproblems that arise in the search tree. Table 1.44 describes the valid values for this option.

Table 1.44: Values for CONFLICTSEARCH= Option

number

string

Description

–1

AUTOMATIC

Performs a conflict search based on a strategy that is determined by PROC OPTGRAPH

0

NONE

Disables conflict search

1

MODERATE

Performs a moderate conflict search

2

AGGRESSIVE

Performs an aggressive conflict search


By default, CONFLICTSEARCH=AUTOMATIC.

CUTOFF=number

cuts off any branch-and-bound nodes in a minimization problem that has an objective value that is greater than number. The value of number can be any number; the default value is the positive number that has the largest absolute value that can be represented in your operating environment.

CUTSTRATEGY=number | string

specifies the level of mixed integer linear programming cutting planes to be generated by PROC OPTGRAPH. TSP-specific cutting planes are always generated. Table 1.45 describes the valid values for this option.

Table 1.45: Values for CUTSTRATEGY= Option

number

string

Description

–1

AUTOMATIC

Generates cutting planes based on a strategy determined by the mixed integer linear programming solver

0

NONE

Disables generation of mixed integer linear programming cutting planes (some TSP-specific cutting planes are still active for validity)

1

MODERATE

Uses a moderate cut strategy

2

AGGRESSIVE

Uses an aggressive cut strategy


By default, CUTSTRATEGY=NONE.

EMPHASIS=number | string

specifies a search emphasis option. Table 1.46 describes the valid values for this option.

Table 1.46: Values for EMPHASIS= Option

number

string

Description

0

BALANCE

Performs a balanced search

1

OPTIMAL

Emphasizes optimality over feasibility

2

FEASIBLE

Emphasizes feasibility over optimality


By default, EMPHASIS=BALANCE.

HEURISTICS=number | string

controls the level of initial and primal heuristics that PROC OPTGRAPH applies. This level determines how frequently PROC OPTGRAPH applies primal heuristics during the branch-and-bound tree search. It also affects the maximum number of iterations that are allowed in iterative heuristics. Some computationally expensive heuristics might be disabled by the solver at less aggressive levels. Table 1.47 lists the valid values for this option.

Table 1.47: Values for HEURISTICS= Option

number

string

Description

–1

AUTOMATIC

Applies the default level of heuristics

0

NONE

Disables all initial and primal heuristics

1

BASIC

Applies basic initial and primal heuristics at low frequency

2

MODERATE

Applies most initial and primal heuristics at moderate frequency

3

AGGRESSIVE

Applies all initial primal heuristics at high frequency


By default, HEURISTICS=AUTOMATIC.

LOGFREQ=number

specifies how often to print information in the branch-and-bound 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 100. If number is set 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 that are controlled by the value of number. An entry is also made each time a better integer solution is found.

LOGLEVEL=number | string

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

Table 1.48: Values for LOGLEVEL= Option

number

string

Description

0

NONE

Turns off all solver-related messages in the SAS log

1

BASIC

Displays a solver summary after stopping

2

MODERATE

Prints a solver summary and a node log by using the interval that is specified in the LOGFREQ= option

3

AGGRESSIVE

Prints a detailed solver summary and a node log by using the interval that is specified in the LOGFREQ= option


The default value is MODERATE.

MAXNODES=number

specifies the maximum number of branch-and-bound nodes to be processed. 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 $2^{31} - 1$.

MAXSOLS=number

specifies a stopping criterion. If number solutions have been found, then the procedure stops. The value of number can be any positive integer up to the largest four-byte signed integer, which is $2^{31} - 1$. The default value is $2^{31} - 1$.

MAXTIME=number

specifies the maximum amount of time to spend solving the traveling salesman problem. The type of time (either CPU time or real time) is determined by the value of the TIMETYPE= option. The value of number 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.

MILP=number | string

specifies whether to use a mixed integer linear programming (MILP) solver for solving the traveling salesman problem. The MILP solver attempts to find the overall best TSP tour by using a branch-and-bound based algorithm. This algorithm can be expensive for large-scale problems. If MILP=OFF, then PROC OPTGRAPH uses its initial heuristics to find a feasible, but not necessarily optimal, tour as quickly as possible. Table 1.49 describes the valid values for this option.

Table 1.49: Values for MILP= Option

number

string

Description

1

ON

Uses a mixed integer linear programming solver

0

OFF

Does not use a mixed integer linear programming solver


By default, MILP=ON.

NODESEL=number | string

specifies the branch-and-bound node selection strategy option. Table 1.50 describes the valid values for this option.

Table 1.50: Values for NODESEL= Option

number

string

Description

–1

AUTOMATIC

Uses automatic node selection

0

BESTBOUND

Chooses the node that has the best relaxed objective (best-bound-first strategy)

1

BESTESTIMATE

Chooses the node that has the best estimate of the integer objective value (best-estimate-first strategy)

2

DEPTH

Chooses the most recently created node (depth-first strategy)


By default, NODESEL=AUTOMATIC. For more information about node selection, see Chapter 13: The OPTMILP Procedure in SAS/OR 14.1 User's Guide: Mathematical Programming.

OUT=SAS-data-set

specifies the output data set to contain the solution to the traveling salesman problem.

PROBE=number | string

specifies a probing option. Table 1.51 describes the valid values for this option.

Table 1.51: Values for PROBE= Option

number

string

Description

–1

AUTOMATIC

Uses an automatic probing strategy

0

NONE

Disables probing

1

MODERATE

Uses the probing moderately

2

AGGRESSIVE

Uses the probing aggressively


By default, PROBE=NONE.

RELOBJGAP=number

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

\[ \mid \mbox{BestInteger} - \mbox{BestBound}\mid / \left(\mbox{1E$-$10}~  + \mid \mbox{BestBound}\mid \right) \]

When this value becomes less than the specified gap size number, the solver stops. The value of number can be any nonnegative number. By default, RELOBJGAP=1E–4.

STRONGITER=number | AUTOMATIC

specifies the number of simplex iterations that PROC OPTGRAPH performs for each variable in the candidate list when it uses 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, PROC OPTGRAPH uses the default value, which it calculates automatically.

STRONGLEN=number | AUTOMATIC

specifies the number of candidates that PROC OPTGRAPH considers when it uses 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, PROC OPTGRAPH uses the default value, which it calculates automatically.

TARGET=number

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

VARSEL=number | string

specifies the rule for selecting the branching variable. Table 1.52 describes the valid values for this option.

Table 1.52: Values for VARSEL= Option

number

string

Description

–1

AUTOMATIC

Uses automatic branching variable selection

0

MAXINFEAS

Chooses the variable that has maximum infeasibility

1

MININFEAS

Chooses the variable that has minimum infeasibility

2

PSEUDO

Chooses a branching variable based on pseudocost

3

STRONG

Uses the strong branching variable selection strategy


By default, VARSEL=AUTOMATIC. For more information about variable selection, see Chapter 13: The OPTMILP Procedure in SAS/OR 14.1 User's Guide: Mathematical Programming.