Re: [Help-glpk] Simplex vertex neighborhood

[Michael Hennebry]

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.

--
Michael   address@hidden
"On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword."  --  Lily