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

moustapha.di...@xxxxxxxxxxxxxxxxxx wrote:
> Jennifer Anderson wrote:
> > 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
>
> Dear Jenny - All variables in my model are non-negative. So, I am not
> sure I understand what you mean by "negative flow." I think it would
be
> helpful if you could indicate to me exactly which variables in my
model
> would be negative to correspond to the "first vector" in your chart
> above, and how and at what stage of the simplex procedure such
> negative variables would arise. //Moustapha.

Sorry, never mind. I didn't understand what you were doing in the proof
of Prop 2. My professor said the Clay Math Institute will pay $1
million for solving their P=NP problem. Have they contacted you?

Jenny

.