[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Simplex vertex neighborhood
Kevin Hunter Kesling
Re: [Help-glpk] Simplex vertex neighborhood
Fri, 16 Aug 2013 13:20:38 -0400
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
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.,
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.
Re: [Help-glpk] Simplex vertex neighborhood, Andrew Makhorin, 2013/08/17
- [Help-glpk] Simplex vertex neighborhood, sgerber, 2013/08/15
- Re: [Help-glpk] Simplex vertex neighborhood, Michael Hennebry, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood,
Kevin Hunter Kesling <=
- Re: [Help-glpk] Simplex vertex neighborhood, Michael Hennebry, 2013/08/17
- Re: [Help-glpk] Simplex vertex neighborhood, sgerber, 2013/08/19
- Re: [Help-glpk] Simplex vertex neighborhood, Michael Hennebry, 2013/08/19
- Re: [Help-glpk] Simplex vertex neighborhood, Matteo Fischetti DEI, 2013/08/19
- Re: [Help-glpk] Simplex vertex neighborhood, Michael Hennebry, 2013/08/20