Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"



Bryan Olson wrote:
> moustapha.diaby@xxxxxxxxxxxxxxxxxx wrote:
> moustapha.diaby also wrote ...
> >>> > Set x(i,s,j) = y(i,s,j,i,s,j) at the start of each iteration.
>
> [Bryan Olson wrote:]
> >>>Then those y values of the form y(i,s,j,i,s,j) will be at least
> >>>as large as lambda.
> >>
> >>When lambda is their minimum?
> >
> > You are actually correct on this point. So ignore my comment above.
> >>
> >>>How do you handle the others? You can't
> >>>subtract lambda, because that could be negative. You can't leave
> >>>them as they are, because then constraints the proof relies upon
> >>>won't hold.
> >>
> >>What specific constraints are you referring to?
> >
> > The question above remains: What specific constraints are you referring
> > to?
>
> The argument for Proposition 3 cites 2.21, 2.22, 2.28, and 2.29
> as if they held for y' (the final "adjusted y"). The latter two
> are not directly constraints, but are proven assuming other
> constraints on y.



OK, I understand your argument. May I need to be more detailed in the
proof. I will do so in a (minor) revision that will be posted shortly.


>
> > What would cause them to stop holding (since the solution at hand
> > is feasible)?
>
> If you subtract lambda from all the y[u,p,v,k,r,t] values, some
> can become negative. If you just subtract lambda from values of
> the form y[i,s,j,i,s,j], then constraints such as 2.21 don't
> hold.
>
>







> --
> --Bryan

.

Relevant Pages

  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... Computational complexity classes P and NP are equal." ... What specific constraints are you referring ... > If you subtract lambda from all the yvalues, some ...
    (comp.theory)
  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... >>>>When lambda is their minimum? ... You can't leave>>>them as they are, because then constraints the proof relies upon>>>won't hold. ... What specific constraints are you referring ... If you just subtract lambda from values of the form y, then constraints such as 2.21 don't hold. ...
    (comp.theory)
  • Re: Linear optimization problem
    ... The algorithm just computes the bracket when ... The corresponding lambda would change its value ... when the constraints change. ...
    (comp.soft-sys.matlab)
  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... >> as large as lambda. ... because then constraints the proof relies upon ... What specific constraints are you referring ... Prev by Date: ...
    (comp.theory)
  • Re: default values
    ... In merge replication AFAIK it isn't possible to not replicate the defaults ... constraints so perhaps you are referring to default objects? ... could redefine them as default constraints, or you could use a script to be ...
    (microsoft.public.sqlserver.replication)