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

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.

> 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