Problem Formulation
The Traveling Salesmen Problem (TSP) is as follows: given a set of cities, or vertices
V
a set of direct routes between cities, or edges
E
, and for each edge
e
a distance
d_e
, 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
d_e
is assumed to be metric
, the metric TSP.
One good integer programming formulation for TSP is the cutset formulation. For any
S \subset V
, let
\delta(S) = {(u,v) \in E \mid u \in S, v \not \in S}
, i.e. those edges with exactly one endpoint in
S
. With a slight abuse of notation, for
v \in V
, we also let
\delta(v) = \delta({v})
, i.e. the edges incident to
v
. The cutset formulation is:
\begin
&\min & \sum_
d_e x_e
&\text
& \sum_
x_e &= 2&v&\in V
&& \sum_
x_e &\geq 2& S &\subset V&S&\neq V,\, \emptyset
&& x_e &\in{0,1}&e&\in E
\end
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
V
, (exactly
2^
), and thus our integer programming formulation has exponentially many constraints.
Integrality Gap
The integrality gap is measure of the quality of an integer programming formulation. For a minimization problem, If
I^*
is the optimal solution to the IP, and
L^*
is the optimal solution to the LP (so
I^* \geq L^*
, then integrality gap is defined to be the ratio
I^/L^
. For a class of integer programming problems and a formulation, such as all instances of the TSP with the cutset formulation, we say the the integrality gap is the suprememum of the integrality gap over all instances in the class.
For TSP with the cutset formulation, we can show that the integrality gap is atleast 3/2. Consider the following family of instances, parameterized by
n
.