# Recitation 13

Example: A salesperson needs to visit five cities on a regular basis and wishes to minimize the total cost of the round trip. He figures that it costs $0.20 per mile to operate his card. The table below gives the distances in miles between the cities. Between certain cities the only reasonable routes utilize a system of toll roads on which the toll is$0.04 per mile. An * indicates toll roads.

From \ To 1 2 3 4 5
1 55 45 90* 45
2 60 55 20 75
3 40 55 35* 120*
4 90* 20 35* 25
5 50 80 120* 30

Solution: We first turn the table of the distances between the cities to the table of the costs between the cities.

From \ To 1 2 3 4 5
1 M 11 9 21.6 9
2 12 M 11 4 15
3 8 11 M 8.4 28.8
4 21.6 4 8.4 M 5
5 10 16 28.8 6 M

Let $x_{ij}$, where $i,j=1,2,3,4,5$, be the variables indicating if the salesperson travels from city $i$ to city $j$. The linear program for the traveling salesman problem can be formulated as below. Denote the $(i,j)$ in the last table by $c_{ij}$.

Minimize $\sum_{ij}c_{ij}x_{ij}$ $\sum_{j}x_{ij} \ge 1$ for all $i$ $\sum_{i}x_{ij} \ge 1$ for all $j$ $\sum_{i\in D, j\notin D}x_{ij} \ge 1$ for all proper subset $D$.