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

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.


--
--Bryan
.

Relevant Pages

  • 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)
  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... >> Bryan Olson wrote: ... >>>Step 2 is to subtract lambda from each arc on L, ... I had thought this meant to subtract lambda from y ... >> result in a negative number because lambda is the minimum of those flow ...
    (comp.theory)