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

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



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

.

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"
    ... >> 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)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... graph - one level of graph was representation of one parenthesis, ... remembered "flow" through every arc. ... from "cut point" to end) but could we possibly store tape contents with less ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... The reason is that the variables are not ... "fly" from arc to arc. ... Flow must be connected (required by constraints 2.8); ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... forms exactly one feasible solution. ... the total flow on an arc belonging to multiple ... arcs from stages that precede the stage of the arc in question. ... I agree that there is a large number of possible cass paths. ...
    (comp.theory)