Re: P=NP: Linear Programming Formulation of the TSP
- From: dmoews@xxxxxxxxxxxxxxxxxxxxx (David Moews)
- Date: 30 Apr 2005 01:43:11 GMT
I have read the revised version
<http://www.business.uconn.edu/users/mdiaby/TSPLP/Paper/TSP_LP_small.pdf>,
dated 2005-II-12, of Moustapha Diaby's paper
``P=NP: Linear Programming Formulation of the Traveling Salesman Problem''.
I have the following comments.
1. The statement of Proposition 2 is unclear, because it has not been
defined what it means for (y, z) to consist of a collection of
c.a.s.s. paths.
2. The proof of Proposition 2 is likewise unclear. At the bottom
of page 13, for example, it is claimed that ``there must remain at
least one path, say Path L, with positive flow, say \lambda (\lambda>0),
that is not a c.a.s.s. path''. Presumably, what is happening here
is that vectors which project onto multiples of the v_g's (see below)
are being subtracted from the y_{isjkrt}'s and z_{ijupvkrt}'s so as to
leave these variables nonnegative, and after this can no longer be
done, the situation is examined. However, a priori, the y_{isjkrt}'s and
z_{ijupvkrt}'s are only a collection of variables, and it is not clear
what it means to locate in them a path of positive flow, nor why this
should be possible.
3. If we attempt nonetheless to clarify the content of Proposition 2,
given the claims made in Propositions 1, 3, 4 and the rest of the paper,
it appears that it must imply that the projection of the feasible polytope
onto the variables y_{isjisj} yields the convex hull of
{ v_g | g a c.a.s.s. path}, where c.a.s.s. paths and v_g are as defined in
my previous post <cmote5$al6$1@xxxxxxxxxxxxxxxxxx>. Given this, it can
be shown, using similar reasoning to my previous post, that Proposition 2
is in conflict with Yannakakis's 1988 result. I give the argument in an
appendix at the end of this post.
4. Re the remarks on Yannakakis's result near the bottom of p. 12, I will
point out that in order for a LP formulation of the TSP to be symmetric,
Yannakakis does not require that the stages of the tour be treated
symmetrically, or even that they be expressed at all. Symmetry under
permutation of cities (in a sense defined in Yannakakis's paper) is all
that is required. Of course, Diaby's formulation is not symmetric in this
sense, because city 1 is treated differently from the other cities.
However, Yannakakis's proof can be adapted to handle this, as I outline
below and in my previous post.
5. There appears to be a typo in equations (2.7) (p. 9), (2.17) (p. 10),
and (3.6) (p. 17): to preserve Proposition 1 and the sense of the paper,
y_{isjk,r+1,t} should be changed to y_{isjt,r+1,k} in these equations.
--
David Moews dmoews@xxxxxxxxxxxxxxxxxxxxx
---------------------------------------------------------------------------
APPENDIX.
In this revision, Diaby's initial LP formulation, \overline{IP} (p. 12)
of an n-city TSP problem contains variables y_{isjkrt} and z_{ijupvkrt},
where i, j, k, t, u, and v range over the set {2, ..., n} (the set of
cities, excluding city 1), and p, r, and s range over the set {1, 2, ..., n-2}
(the set of times at which these cities are visited, excluding time n-1.)
Now
(1') If the y's and z's are permuted by sending
y_{isjkrt} to y_{f(i)sf(j)f(k)rf(t)}
and z_{ijupvkrt} to z_{f(i)f(j)f(u)pf(v)f(k)rf(t)}
for some permutation f of {2, ..., n}, the set of constraints used
to define the feasible polytope is left unchanged, and therefore the
feasible polytope is left unchanged,
and
(2') According to Proposition 2, projecting the feasible polytope
onto the variables y_{isjisj} yields the convex hull of
{ v_g | g a c.a.s.s. path }. Here, a c.a.s.s. path is a bijection g
from {1, ..., n-1} (the set of times) to {2, ..., n} (the set of
cities, excluding city 1), and the value of y_{isjisj} at v_g is 1 if
(g(s),g(s+1))=(i,j), 0 otherwise.
We can now proceed with the argument given in <cmote5$al6$1@xxxxxxxxxxxxxxxxxx>,
replacing (1) and (2) with (1') and (2'), and construct a counterexample to
Theorem 1 in Yannakakis (J. Computer and System Sciences 43 (1991), pp.
441--466).
--
David Moews dmoews@xxxxxxxxxxxxxxxxxxxxx
.
- Prev by Date: Re: P=NP: Linear Programming Formulation of the TSP
- Next by Date: The Steiner Tree Problem
- Previous by thread: Re: P=NP: Linear Programming Formulation of the TSP
- Next by thread: Problems in NP with infinite number of possibiltiies to check?
- Index(es):
Relevant Pages
|
