# 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.