Re: [Help-glpk] Simplex vertex neighborhood

[Kevin Hunter Kesling]

At 12:03pm -0400 Fri, 16 Aug 2013, Sam Gerber wrote:
> 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.

Michael is of course correct, but I do not have the mathematical 
background to visualize that.  Here is how I visualize it (and I would 
welcome corrections to it!).

  1. For linear programming, smarter people than me talk about convex
     hulls, which I interpret -- very roughly -- as a sphere.

  2. With no constraints, the convex hull (or sphere) is just your
     standard x-y-z three dimensional space.  (With more than 3
     variables, it would be more than 3-d space, but I can't
     visualize that, so I stick with 3-d space for thinking about
     it.)

  3. The objective function is some line (or perhaps plane) inside
     this convex hull (or sphere).  With no constraints, there are
     no limits, so any point on the line/plane will always have a
     larger (or smaller) feasible associated value.  This would be
     an example of an UNBOUNDED problem.

  4. Every constraint added equates (again _very roughly_) to a
     boundary plane cutting through the convex hull (or sphere).  One
     side of this boundary plane is a valid (feasible) set of
     solutions, while the other side is invalid.  The valid side is
     determined by the choice of "less than" or "greater than" in
     the constraint equation.

  5. With multiple constraints (boundary planes), the convex hull
     looks something like a 20-sided die.  Technically, a
     "non-regular geodesic dome".  That is, it looks like some
     version of these spinning spheres on Wikipedia:

       http://en.wikipedia.org/wiki/Geodesic_dome#Chord_factors

     except that the sides won't be so regular.  The inside and edges
     of this dome are the feasible points.

  6. Assuming that a solution exists, then your objective function
     will touch at least one point on the edge of the convex hull
     (geodesic dome).

  7. If you do _not_ have degenerate solutions, then the optimal
     value of your objective function will only occur at a single
     vertex.  Thus, the algorithm need only test vertices.

In effect, what the simplex algorithm does is systematically test 
vertices until it has the optimal solution.  Now, to the crux of your 
assumption that the simplex algorithm tests points around the optimal 
vertex: no, I do not believe it does.  From the linear algebra tableau, 
if the algorithm happened upon the correct vertex at iteration 1, it 
would instantly know that it was the best solution.  No further 
iteration (i.e. testing of other vertices) necessary.

Put differently, recognize that finding the optimal vertex at step 1 
doesn't happen very often, so the algorithm has to test a number of 
vertices.  From the geodesic dome point of view, my understanding is 
that the algorithm jumps to seemingly random vertices until it reaches 
the optimal objective function value; the algorithm does *not* move 
through _adjacent_ vertices to find the best one.  The vertices tested 
aren't random of course, but are chosen via a different ordering that I 
haven't yet internalized.

Thus, even though the values of interest to you will be around the 
maximal vertex point (from the standpoint of _linear_ programming and 
your objective function), the simplex algorithm likely won't have seen them.

Now, with all that said, don't quote me.  I'm not a mathematician; use 
my description at your own risk; it may eat your children; etc.  Also, 
if someone has a link to an online visualization/animation (e.g., 
Youtube, Javascript page), I would be most appreciative!

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

I am by no means an expert on GLPK (so wait for other's responses!), but 
I don't think so directly.  However, you may be interested in the MGA 
algorithm.  My one line summation is that it is something along the 
lines of "Solve it once, then swap your objective function with a 
constraint and resolve.  Repeat as necessary."  See

    "Modeling to Generate Alternatives: The HSJ Approach and an
     Illustration Using a Problem in Land Use Planning"

    by Downey Brill, Shoou-Yuh Chang, and Lewis Hopkins (1982)

for a much more thorough explanation.

Kevin