Re: P=NP: Linear Programming Formulation of the TSP

Dear Dr. Diaby,

Are you sure the algorithm isn't just getting lucky, landing on 0,1
solutions, and that there's no guarantee that the optima achieved is
always 0,1? This can happen with lots of integer programs formulated as
linear programs.

For instance, in your proof of Proposition 2, you assume that the path
that is not c.a.s.s. has positive flow. Why can't it have a negative
flow, as Jarfo pointed out before and other paths which are not
c.a.s.s. have positive flows to cancel it out?

- 1/M x ( 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 .......)
+ 1/M x ( 1 1 1 .....................................)
+ 1/M x ( ...............1 1 1...................... )
+ 1/M x ( ..............................1 1 1....... )

In his chart, we have an example, the first vector that could have a
negative flow and not be c.a.s.s. but not violate your "constraint
(2.22)".

Jenny

.