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



Set x(i,s,j) = y(i,s,j,i,s,j) at the start of each iteration. 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.

.

Relevant Pages

  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... >> the procedure for given solution to Problem IP-Bar is ... the pseudo-code should be as follows:> ... Step 2 is to subtract lambda from each arc on L, ...
    (comp.theory)
  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... >>> initialize the set of excluded cities, EC = empty set; ... >>>>Step 2 is to subtract lambda from each arc on L, ... 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 ...
    (comp.theory)
  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... > Step 2 is to subtract lambda from each arc on L, ... I had thought this meant to subtract lambda from y ... Subtracting lambda from the flow values of the arcs on the path cannot ...
    (comp.theory)