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


Jennifer Anderson wrote:
> 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


I am happy to see that you understand and thank you for letting me
know. I am quite convinced of the soundness of my overall approach.
But, I guess we will only know for sure about the correctness of the
current formulation after the formal review process is completed...
Best. //M.

.

Relevant Pages