Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
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.
--
--Bryan
.
