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


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?

.

Relevant Pages