You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 5 Next »

The root page 15DOTs60ia13:Tutorial could not be found in space 15.S60 SSIM: Software Tools for Operations Research.

Problem Formulation

The Traveling Salesmen Problem (TSP) is as follows: given a set of cities, or vertices

Unknown macro: {mathinline}

V

a set of direct routes between cities, or edges

Unknown macro: {mathinline}

E

, and for each edge

Unknown macro: {mathinline}

e

a distance

Unknown macro: {mathinline}

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

Unknown macro: {mathinline}

d_e

is assumed to be metric, the metric TSP.

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

Unknown macro: {mathinline}

S \subset V

, let

Unknown macro: {mathinline}

\delta(S) = {(u,v) \in E \mid u \in S, v \not \in S}

, i.e. those edges with exactly one endpoint in

Unknown macro: {mathinline}

S

. With a slight abuse of notation, for

Unknown macro: {mathinline}

v \in V

, we also let

Unknown macro: {mathinline}

\delta(v) = \delta({v})

, i.e. the edges incident to

Unknown macro: {mathinline}

v

. The cutset formulation is:

Unknown macro: {mathdisplay}

\begin

Unknown macro: {aligned}

&\min & \sum_

Unknown macro: {e in E}

d_e x_e
&\text

Unknown macro: {subject to}

& \sum_

Unknown macro: {e in delta(v)}

x_e &= 2&v&\in V
&& \sum_

Unknown macro: {e in delta(S)}

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

Unknown macro: {mathinline}

V

, (exactly

Unknown macro: {mathinline}

2^

Unknown macro: {|V|}

), 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

Unknown macro: {mathinline}

I^*

is the optimal solution to the IP, and

Unknown macro: {mathinline}

L^*

is the optimal solution to the LP (so

Unknown macro: {mathinline}

I^* \geq L^*

, then integrality gap is defined to be the ratio

Unknown macro: {mathinline}

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

Unknown macro: {mathinline}

n

.

  • No labels