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