h1. The Traveling Salesmen Problem

The Traveling Salesmen Problem (TSP) is as follows: given a set of cities, or vertices {mathinline}V{mathinline} a set of direct routes between cities, or edges {mathinline}E{mathinline}, and for each edge {mathinline}e{mathinline} a distance {mathinline}d_e{mathinline}, what is the shortest tour through all the cities that visits each city exactly once? As this problem is quite difficult, we often consider the special case where {mathinline}d_e{mathinline} is assumed to be metric, the metric TSP.