[Top][All Lists]

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

Re: [Help-glpk] Simplex vertex neighborhood

From: Kevin Hunter Kesling
Subject: Re: [Help-glpk] Simplex vertex neighborhood
Date: Fri, 16 Aug 2013 13:20:38 -0400
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130803 Thunderbird/17.0.8

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

  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:

     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.


reply via email to

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