[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Simplex vertex neighborhood

From: Matteo Fischetti DEI
Subject: Re: [Help-glpk] Simplex vertex neighborhood
Date: Fri, 16 Aug 2013 20:28:12 +0200
User-agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130801 Thunderbird/17.0.8

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?


Prof. Matteo Fischetti
DEI, University of Padova
via Gradenigo 6/A
I-35131 Padova (Italy)
e-mail: address@hidden

reply via email to

[Prev in Thread] Current Thread [Next in Thread]