2
$\begingroup$

The Dantzig-Fulkerson-Johnson formulation for the symmetric TSP Polytope is given as: $x(\delta(v))=2 \quad \forall v \in V$,
$x(\delta(S))\geq2 \quad \forall \emptyset \subset S \subset V$,
$x \in \{0,1\}^A$.

Also, I see that when there are 5 cities the perfect formulation is
$0 \leq x_e \leq 1 \quad \forall e\in E$,
$x(\delta(v))=2 \quad \forall v \in V$.

I can see that when there are 5 cities, the subtour elimination constraint gets redundant. However, I don't understand how this LP-relaxation gives integral solutions.

$\endgroup$
1
  • $\begingroup$ The integrality of polyhedron comes from Birkhoff's theorem. However in the literature this theorem is applied to matching polyhedron. How can this theorem be used for this purpose? (In matching polyhedron bipartition is being used as a trick). $\endgroup$
    – independentvariable
    Commented Feb 27, 2018 at 18:53

1 Answer 1

Reset to default
0
$\begingroup$

Solved it. Grötschel and Padberg (1979) proved that $0 \leq x \leq 1$ defines facets of the TSP polytope when n=5. This fact and redundant subtour elimination constraint gives the perfect formulation.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .