Problem

Formulation

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|http://en.wikipedia.org/wiki/Metric_(mathematics)#Definition], the metric TSP. One good integer programming formulation for TSP is the _cutset_ formulation. For any {mathinline}S \subset V{\mathinline}, let {mathinline}\delta(S) = \{(u,v) \in E \mid u \in S, v \not \in S\}{mathinline}, i.e. those edges with exactly one endpoint in {mathinline}S{mathinline}. With a slight abuse of notation, for {mathinline}v \in V{mathinline}, we also let {mathinline}\delta(v) = \delta(\{v\}){mathinline}, i.e. the edges incident to {mathinline}v{mathinline}. The cutset formulation is: {mathdisplay} \begin{aligned} &\min & \sum_{e \in E} d_e x_e\\ &\text{subject to}& \sum_{e \in \delta(v)} x_e &= 2&v&\in V\\ && \sum_{e \in \delta(S)} x_e &\geq 2& S &\subset V&S&\neq V,\, \emptyset\\ && x_e &\in\{0,1\}&e&\in E \end{aligned} {mathdisplay} The first family of constraints say that every node must have degree two, and will be referred to as the *degree constraints*. The second family of constraints say that for any cut separating the graph into two subsets, there must be at least two edges in use across the cut, and will be referred to as the *cutset constraints*. The solution to the linear programming relaxation of this formulation (when the integrality constraints are dropped) is known as the Held-Karp lower bound. Notice that there are exponentially many subsets of {mathinline}V{mathinline}, (exactly {mathinline}2^{|V|}{mathinline}), and thus our integer programming formulation has exponentially many constraints. h1. Integrality Gap The integrality gap is measure of the quality of an integer programming formulation. For a minimization problem, If {mathinline}I^*{mathinline} is the optimal solution to the IP, and {mathinline}L^*{mathinline} is the optimal solution to the LP (so {mathinline}I^* \geq L^*{mathinline}, then integrality gap is defined to be the ratio {mathinline}I*/L^*{mathinline}.

One good integer programming formulation for TSP is the cutset formulation. For any

The first family of constraints say that every node must have degree two, and will be referred to as the degree constraints. The second family of constraints say that for any cut separating the graph into two subsets, there must be at least two edges in use across the cut, and will be referred to as the cutset constraints. The solution to the linear programming relaxation of this formulation (when the integrality constraints are dropped) is known as the Held-Karp lower bound. Notice that there are exponentially many subsets of