[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 23:36:58 -0500 (CDT) |
User-agent: |
Alpine 1.00 (DEB 882 2007-12-20) |
On Fri, 16 Aug 2013, sgerber 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.
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.
Correct.
In that case, you will have one neighbor per active constraint.
You need to persuade GLPK to perform one simplex pivot per
tight constraint, starting from the source vertex each time.
From the source vertex, adjust the objective function so
that the desired variable has the only positive reduced cost.
Tell GLPK that at most one more pivot is allowed.
Tell GLPK to use the simplex method.
I am dubious about the usefulness of doing so.
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.
Consider the regular solids.
Each vertex of the simplex, the cube and
the dodecahedron has three neighbors,
but the vertices of the octahedron and the
icosahedron have four and five, respectively.
Note that in n-space only 2n constraints are required
to define an n-cube which has 2**n vertices.
In n-space, only 2n-1 constraints are neessary to define
a region that has a vertex with 2**(n-1) neighbors.
-x[n] <= x[j] <= x[n] for j in 1..n-1
x[n]<=1
The origin is a vertex with 2**(n-1) neighbors.
'Tis my understanding that the situation is actually worse.
--
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
- [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, sgerber, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood, Matteo Fischetti DEI, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood, sgerber, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood, Matteo Fischetti DEI, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood, Kevin Hunter Kesling, 2013/08/16
- Re: [Help-glpk] Simplex vertex neighborhood,
Michael Hennebry <=
- 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
- Re: [Help-glpk] Simplex vertex neighborhood, Andrew Makhorin, 2013/08/17