Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: Migration of unmigrated content due to installation of a new plugin
Section
Column
width300px
Page Tree
root15DOTs60ia13:Tutorial
h1.

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

Column
Wiki Markup
LaTeX Math Inline
a set of direct routes between cities, or edges
LaTeX Math Inline
, and for each edge
LaTeX Math Inline
a distance
LaTeX Math Inline
, 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
LaTeX Math Inline
is assumed to be metric, the metric TSP.

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

LaTeX Math Inline
, let
LaTeX Math Inline
, i.e. those edges with exactly one endpoint in
LaTeX Math Inline
. With a slight abuse of notation, for
LaTeX Math Inline
, we also let
LaTeX Math Inline
, i.e. the edges incident to
LaTeX Math Inline
. The cutset formulation is:

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

LaTeX Math Inline
, (exactly
LaTeX Math Inline
), and thus our integer programming formulation has exponentially many constraints.