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



Bryan Olson wrote:
> 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.

When lambda is their minimum?


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?

>
>
> > 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

.

Relevant Pages