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: [email protected]
web: www.dei.unipd.it/~fisch
reports: www.dei.unipd.it/~fisch/papers
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
