[Top][All Lists]

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

Re: [Help-glpk] Simplex vertex neighborhood

From: Michael Hennebry
Subject: Re: [Help-glpk] Simplex vertex neighborhood
Date: Fri, 16 Aug 2013 10:48:41 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

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.

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

reply via email to

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