Re: [Help-glpk] Simplex vertex neighborhood

[Matteo Fischetti DEI]

As you observed, because of degeneracy some of the basic solutions 
associated with different adjacent bases can in fact coincide. 
Nevertheless,  the number of different adjacent vertices can still be 
very large (as Micheal said, their number can be "much larger than the 
dimension of the problem").



Il 16/08/2013 19:50, sgerber ha scritto:
> Hi Matteo
>
> Thank you, this is very helpful. I am really interested in the 
> geometric neighborhood.
>
> This sentence is paragraph is a little confusing:
>
> > In case of primal degeneracy, instead, you have a (possibly
> > exponential) n. of different bases B*_1, B*_2, .... associated with a
> > single vertex x*, and each such basis can produce up to n-m adjacent
> > vertices, meaning that the total number of adjacent vertices can
> > explode.  In other words,  if x is vertex geometrically adjacent to
> > x*, you can still reach x through a single pivot from a CERTAIN basis
> > B*_k associated with x*, but you have to try all possible such bases
> > B*_1, B^*_2, ... to find the B*_k that works.
>
> Did you really mean the total number of adjacent vertices cen explode? 
> or the total number of bases representing the neighboring vertices can 
> explode?
>
>
> Thanks
> Sam
> .


--
Prof. Matteo Fischetti
DEI, University of Padova
via Gradenigo 6/A
I-35131 Padova (Italy)
e-mail: address@hidden
web: www.dei.unipd.it/~fisch
reports: www.dei.unipd.it/~fisch/papers