Re: [Help-glpk] Simplex vertex neighborhood

[Matteo Fischetti DEI]

Just a last comment: in case of (primal) degeneracy, a vertex x* can be 
optimal but a given associated basis B can still lead to negative 
reduced costs, i.e., B can be "nonoptimal". Indeed, the test on reduced 
costs is only a sufficient condition that can be violated by several 
bases B associated to an optimal vertex x*.

Under appropriate rules (Bland or lexicographic), however, you can prove 
that the simplex method will eventually find a basis B* still associated 
x* that satisfied the reduced- cost condition, i.e. an "optimal B*" 
always exists. But going from B to B*  can require a huge n. of pivots, 
in a sense because you need to "implicitly consider" all the adjacent 
vertices.

Matteo


Il 19/08/2013 18:14, Michael Hennebry ha scritto:
> On Mon, 19 Aug 2013, sgerber wrote:
>
> > Thanks for all the helpful answers. One more clarifying question.
> > You mentioned:
> > > It checks all extreme rays of a cone that includes the feasible region.
> > > The number of rays is the dimension of the problem.
> >
> > The cone you described is the intersection of the half spaces of the 
> > active constraints. Does this mean that in your example one would 
> > have to potentially check an exponential number of rays? This is not 
> > what the simplex
>
> An exponential number of vertices.
>
> > algorithm does, right? The simplex algorithm only checks adjacent 
> > bases (at most m*n), what do these geometrically correspond to? Just 
> > a subset of all neighboring vertices?
>
> The test for optimality requires testing up to n rays.
> If the vertex is optimal, there might be no need consider other bases.
> Performing minimum ratio tests for O(n)
> variables might involve O(m*n) bases.


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