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


Jennifer Anderson wrote:
> moustapha.di...@xxxxxxxxxxxxxxxxxx wrote:
> > 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.
>
> How long does the review process take?

Refereeing time is highly variable. So, it is really anybody's guess.

.

Relevant Pages