{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}
|