Problem

Formulation

The

Traveling

Salesmen

Problem

(TSP)

is

as

follows:

given

a

set

of

cities,

or

vertices

Mathinline

a set of direct routes between cities, or edges

Mathinline

, and for each edge

Mathinline

a distance

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

is assumed to be metric, the metric TSP.

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

Mathinline

, let

Mathinline

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

Mathinline

. With a slight abuse of notation, for

Mathinline

, we also let

Mathinline

, i.e. the edges incident to

Mathinline

. The cutset formulation is:

Mathdisplay

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

Mathinline

, (exactly

Mathinline

), and thus our integer programming formulation has exponentially many constraints.