The Network Solver

Traveling Salesman Problem

The traveling salesman problem (TSP) finds a minimum-cost tour in a graph (G) that has a node set (N) and a link set (E). A path in a graph is a sequence of nodes, each of which has a link to the next node in the sequence. An elementary cycle is a path in which the starting node and ending node are the same and otherwise no node appears more than once in the sequence. A Hamiltonian cycle (or tour) is an elementary cycle that visits every node. In solving the TSP, then, the goal is to find a Hamiltonian cycle of minimum total cost, where the total cost is the sum of the costs of the links in the tour. Associated with each link are a binary variable , which indicates whether link e is part of the tour, and a cost . Then an integer linear programming formulation of the TSP (for an undirected graph G) is as follows:

StartLayout 1st Row 1st Column Blank 2nd Column minimize 3rd Column sigma-summation Underscript e element-of upper E Endscripts c Subscript e Baseline x Subscript e 2nd Row 1st Column Blank 2nd Column subject to 3rd Column sigma-summation Underscript e element-of delta left-parenthesis i right-parenthesis Endscripts x Subscript e 4th Column equals 2 5th Column Blank 6th Column i element-of upper N 7th Column Blank 8th Column left-parenthesis normal upper T normal w normal o normal upper M normal a normal t normal c normal h right-parenthesis 3rd Row 1st Column Blank 2nd Column Blank 3rd Column sigma-summation Underscript e element-of delta left-parenthesis upper S right-parenthesis Endscripts x Subscript e 4th Column greater-than-or-equal-to 2 5th Column Blank 6th Column upper S subset-of upper N comma 2 less-than-or-equal-to StartAbsoluteValue upper S EndAbsoluteValue less-than-or-equal-to StartAbsoluteValue upper N EndAbsoluteValue minus 1 7th Column Blank 8th Column left-parenthesis normal upper S normal u normal b normal t normal o normal u normal r right-parenthesis 4th Row 1st Column Blank 2nd Column Blank 3rd Column x Subscript e 4th Column element-of StartSet 0 comma 1 EndSet 5th Column Blank 6th Column e element-of upper E EndLayout

where for each subset S of nodes represents the set of links , with and .

The TwoMatch equations represent the matching constraints, which ensure that each node has degree 2 in the subgraph. The Subtour inequalities represent the subtour elimination constraints (SECs), which enforce connectivity.

For a directed graph, G, the same formulation and solution approach is used on an expanded graph , as described in Kumar and Li (1994). The network solver takes care of the construction of the expanded graph and returns the solution in terms of the original input graph.

In practical terms, you can think of the TSP in the context of a routing problem in which each node is a city and the links are roads that connect those cities. If you know the distance between each pair of cities, the goal is to find the shortest possible route that visits each city exactly once and returns to the starting city. The TSP has applications in planning, logistics, manufacturing, genomics, and many other areas.

In the network solver, you can invoke the traveling salesman problem solver by using the TSP= option.

The algorithm that the network solver uses for solving a TSP is based on a variant of the branch-and-cut process described in Applegate et al. (2006).

The resulting tour is represented in two ways: in the numeric array that is specified in the ORDER= suboption of the OUT= option, the tour is specified as a sequence of nodes; in the set that is specified in the TOUR= suboption of the OUT= option, the tour is specified as a list of links in the optimal tour.

Traveling Salesman Problem Applied to a Simple Undirected Graph

As a simple example, consider the weighted undirected graph in Figure 96.

Figure 96: A Simple Undirected Graph

You can represent the links data set as follows:

data LinkSetIn;
   input from $ to $ weight @@;
   datalines;
A B 1.0   A C 1.0   A D 1.5   B C 2.0   B D 4.0
B E 3.0   C D 3.0   C F 3.0   C H 4.0   D E 1.5
D F 3.0   D G 4.0   E F 1.0   E G 1.0   F G 2.0
F H 4.0   H I 3.0   I J 1.0   C J 5.0   F J 3.0
F I 1.0   H J 1.0
;

The following statements calculate an optimal traveling salesman tour and output the results in the data sets TSPTour and NodeSetOut:

proc optmodel;
   set<str,str> EDGES;
   set<str> NODES = union{<i,j> in EDGES} {i,j};
   num weight{EDGES};
   read data LinkSetIn into EDGES=[from to] weight;
   num tsp_order{NODES};
   set<str,str> TOUR;

   solve with NETWORK /
      loglevel = moderate
      links    = (weight=weight)
      tsp
      out      = (order=tsp_order tour=TOUR)
   ;

   put TOUR;
   print {<i,j> in TOUR} weight;
   print tsp_order;
   create data NodeSetOut from [node]         tsp_order;
   create data TSPTour    from [from to]=TOUR weight;
quit;

The progress of the procedure is shown in Figure 97.

Figure 97: Network Solver Log: Optimal Traveling Salesman Tour of a Simple Undirected Graph

NOTE: There were 22 observations read from the data set WORK.LINKSETIN.

NOTE: The number of nodes in the input graph is 10.

NOTE: The number of links in the input graph is 22.

NOTE: The network solver is called.

NOTE: Processing the traveling salesman problem using 1 threads across 1

machines.

NOTE: The initial TSP heuristics found a tour with cost 16 using 0.00 (cpu:

0.00) seconds.

NOTE: The MILP presolver value NONE is applied.

NOTE: The MILP solver is called.

NOTE: The Branch and Cut algorithm is used.

Node Active Sols BestInteger BestBound Gap Time

0 1 1 16.0000000 15.5005000 3.22% 0

0 0 1 16.0000000 16.0000000 0.00% 0

NOTE: Optimal.

NOTE: Objective = 16.

NOTE: Processing the traveling salesman problem used 0.00 (cpu: 0.00) seconds.

{<'A','B'>,<'B','C'>,<'C','H'>,<'H','J'>,<'I','J'>,<'F','I'>,<'F','G'>,<'E','G'>

,<'D','E'>,<'A','D'>}

NOTE: The data set WORK.NODESETOUT has 10 observations and 2 variables.

NOTE: The data set WORK.TSPTOUR has 10 observations and 3 variables.

The data set NodeSetOut now contains a sequence of nodes in the optimal tour and is shown in Figure 98.

Figure 98: Nodes in the Optimal Traveling Salesman Tour

Traveling Salesman Problem

node	tsp_order
A	1
B	2
C	3
H	4
J	5
I	6
F	7
G	8
E	9
D	10

The data set TSPTour now contains the links in the optimal tour and is shown in Figure 99.

Figure 99: Links in the Optimal Traveling Salesman Tour

Traveling Salesman Problem

from	to	weight
A	B	1.0
B	C	2.0
C	H	4.0
H	J	1.0
I	J	1.0
F	I	1.0
F	G	2.0
E	G	1.0
D	E	1.5
A	D	1.5
		16.0

The minimum-cost links are shown in green in Figure 100.

Figure 100: Optimal Traveling Salesman Tour

Traveling Salesman Problem Applied to a Simple Directed Graph

As another simple example, consider the weighted directed graph in Figure 101. In this graph it might not be possible to travel directly between a pair of nodes in both directions, or the cost of traveling directly between two nodes might depend on the direction of travel.

Figure 101: A Simple Directed Graph

You can represent the links data set as follows:

data LinkSetIn;
   input from $ to $ weight @@;
   datalines;
A B 2.0   A C 1.0   A E 4.0
B A 1.0   B C 2.0   B D 1.0   B E 1.0
C B 2.0   C D 3.0
D A 1.0   D C 1.0   D E 2.0
E A 2.0   E D 1.0
;

The following statements, which are identical to those in the undirected example above except for the SOLVE statement clause DIRECTION=DIRECTED, calculate an optimal traveling salesman tour (on a directed graph) and output the results in the data sets TSPTour and NodeSetOut:

proc optmodel;
   set<str,str> EDGES;
   set<str> NODES = union{<i,j> in EDGES} {i,j};
   num weight{EDGES};
   read data LinkSetIn into EDGES=[from to] weight;
   num tsp_order{NODES};
   set<str,str> TOUR;

   solve with NETWORK /
      loglevel  = moderate
      links     = (weight=weight)
      direction = directed
      tsp
      out       = (order=tsp_order tour=TOUR)
   ;

   put TOUR;
   print {<i,j> in TOUR} weight;
   print tsp_order;
   create data NodeSetOut from [node]         tsp_order;
   create data TSPTour    from [from to]=TOUR weight;
quit;

The progress of the procedure is shown in Figure 102.

Figure 102: Network Solver Log: Optimal Traveling Salesman Tour of a Simple Directed Graph

NOTE: There were 14 observations read from the data set WORK.LINKSETIN.

NOTE: The number of nodes in the input graph is 5.

NOTE: The number of links in the input graph is 14.

NOTE: The network solver is called.

NOTE: The TSP solver is starting using an augmented symmetric graph with 10

nodes and 19 links.

NOTE: Processing the traveling salesman problem using 1 threads across 1

machines.

NOTE: The initial TSP heuristics found a tour with cost 6 using 0.00 (cpu:

0.00) seconds.

NOTE: The MILP presolver value NONE is applied.

NOTE: The MILP solver is called.

NOTE: The Branch and Cut algorithm is used.

Node Active Sols BestInteger BestBound Gap Time

0 1 1 6.0000000 5.9001000 1.69% 0

0 0 1 6.0000000 6.0000000 0.00% 0

NOTE: Optimal.

NOTE: Objective = 6.

NOTE: Processing the traveling salesman problem used 0.00 (cpu: 0.00) seconds.

{<'A','C'>,<'C','B'>,<'B','E'>,<'E','D'>,<'D','A'>}

NOTE: The data set WORK.NODESETOUT has 5 observations and 2 variables.

NOTE: The data set WORK.TSPTOUR has 5 observations and 3 variables.

The data set NodeSetOut now contains a sequence of nodes in the optimal tour and is shown in Figure 103.

Figure 103: Nodes in the Optimal Traveling Salesman Tour

node	tsp_order
A	1
C	2
B	3
E	4
D	5

The data set TSPTour now contains the links in the optimal tour and is shown in Figure 104.

Figure 104: Links in the Optimal Traveling Salesman Tour

from	to	weight
A	C	1
C	B	2
B	E	1
E	D	1
D	A	1
		6

The minimum-cost links are shown in green in Figure 105.

Figure 105: Optimal Traveling Salesman Tour

Last updated: June 04, 2025