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} |
|---|---|
| Subject to | \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. |