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

moustapha.diaby@xxxxxxxxxxxxxxxxxx wrote:
>
> Bryan Olson wrote:
>
>>moustapha.diaby@xxxxxxxxxxxxxxxxxx wrote:
>> > Bryan Olson wrote:
>> >
>> >>moustapha.diaby@xxxxxxxxxxxxxxxxxx wrote:
>> >> > moustapha.diaby@xxxxxxxxxxxxxxxxxx wrote:
>> >> > > [a (not-so-efficient) pseudo-code for Step 1 of
>> >> > > the procedure for given solution to Problem IP-Bar is
>> >> > > as follows:]
>> >> >
>> >> > Actually, the pseudo-code should be as follows:
>> >> >
>> >> >
>> >> > Step 1.0:
>> >> >
>> >> > initialize the set of excluded cities, EC = empty set;
>> >> > select i(1) such that there exists j such that x(i(1), 1, j)) > 0
>> >> > set r = 1
>> >> >
>> >> >
>> >> > Step 1.1:
>> >> >
>> >> > choose an arc with positive flow originating from i(r), (i(r), r,
>> >> > i(r+1)), such that i(r+1) does not belong to EC;
>> >> >
>> >> >
>> >> > Step 1.2:
>> >> >
>> >> > if r = n-2, then
>> >> > compute lambda = min_over(1<=j<=n-2)_{x(i(j), j, i(j+1))
>> >> > stop;
>> >> > else
>> >> > set EC = EC U {i(r)}
>> >> > set r = r+1
>> >> > go to step 1.1
>> >> > endif
>> >>
>> >>Step 2 is to subtract lambda from each arc on L, and adjust y
>> >>accordingly. I had thought this meant to subtract lambda from y
>> >>values that correspond to the path, but now that doesn't work
>> >>because the y values could become negative.
>> >
>> >
>> > Subtracting lambda from the flow values of the arcs on the path cannot
>> > result in a negative number because lambda is the minimum of those flow
>> > values (see step 1.2 above).
>>
>>
>>Wrong. Read what you wrote above: lambda is the min of the x
>>values, not the y's.
>
>
> Set x(i,s,j) = y(i,s,j,i,s,j) at the start of each iteration.

Then those y values of the form y(i,s,j,i,s,j) will be at least
as large as lambda. 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.


> I believe
> this is indicated in the paper. But, I will try to see if it can
> emphasized further if/when I do a next revision of the paper.

It's not a matter of emphasis.


--
--Bryan
.