Re: [Help-glpk] Simplex vertex neighborhood

[sgerber]

On 2013-08-16 11:48, Michael Hennebry wrote:
> On Thu, 15 Aug 2013, sgerber wrote:
>
> > Is it possible to enumerate the neighboring feasible solutions of 
> > the solution of an lp?
> > I assume that in order to decide if the simplex algorithm can stop 
> > it is necessary to check all neighboring feasible solutions. Is this 
> > right? And if so is there a way of enumerating the neighborhood of 
> > feasible solutions around the optimal one?
>
> The simplex algorithm does not check all neighboring vertices.
> It checks all extreme rays of a cone that includes the feasible 
> region.
> The number of rays is the dimension of the problem.
>
> Allowing for degeneracy, the number of adjacent vertices
> can be much larger than the dimension of the problem.

Thank you for your answer.
There is no degeneracies in my problems. I assume the cone you are 
describing is the intersection of the half spaces of the active 
constraints.

Also how does degeneracy increase the number of neighbors? Note,I ask 
for the neighbors of a single optimal solution, i.e. a single vertex, 
not the neighbors of all vertices with optimal solution.

My question still stands is it possible to enumerate the neighbors of a 
vertex with gplk?

-Sam