Hi Sam.
You have two related concepts here: one is vertex adjacency (a geometric
concept), and the other is adjacency between LP bases.
If you have no primal degeneracy (are you sure? this is *very*
unusual!), the two concepts coincide and you can enumerate all the
vertices x adjacent to a given vertex x* by just considering all the
bases B that are adjacent to the (unique) basis B* associated with x*.
In practice:
0. I assume your LP is in standard form Ax = b, x >=0 (all equations, no
upper bound on var.s), where A has (say) m rows and n cols.
1. given your vertex x*, find the unique LP basis B* associated with x*
(I guess you have it readily available, otherwise you can just minimize
the linear function c x with c_j=1 if x*_j>0, =0 otherwise--this work
only if x* is a vertex and there is no primal degeneracy)
2. for each nonbasic var. x_j (w.r.t. B*), in turn, make a single pivot
operation to bring x_j into the basis (the outgoing basic var. will be
determined by the usual simplex ratio test, again in a unique way
because of nondegeneracy), and store the new basic sol. x after pivoting
Step 2 will produce the required list of the (at most) n-m adjacent
bases B of B* and the associated basic solutions x adjacent to x*--note
that some nonbasic x_j could produce no adjacent vertex because of
unboundedness.
In case of primal degeneracy, insted, you have a (possibly exponential)
n. of different bases B*_1, B*_2, .... associated with a single vertex
x*, and each such basis can produce up to n-m adjacent vertices, meaning
that the total number of adjacent vertices can explode. In other
words, if x is vertex geometrically adjacent to x*, you can still reach
x through a single pivot from a CERTAIN basis B*_k associated with x*,
but you have to try all possible such bases B*_1, B^*_2, ... to find the
B*_k that works.
At this point, you may want to know how to perform step 2. in an
effective way through GLPK. One (very inefficient) option could be to
use GLPK (simplex) as a black box and to decrease the objective function
coefficient c_j of the entering nonbasic var. x_j so as move it (alone)
into the basis, being sure to keep all the other outside the basis.
I guess however that there are much more efficient ways to do this,
e.g., by computing the ratio test yourself or by using some GLPK
internal pivoting functions (if available).
I hope the above helped.
Matteo
Il 16/08/2013 18:03, sgerber ha scritto:
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.
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.
My question still stands is it possible to enumerate the neighbors of
a vertex with gplk?
-Sam
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
--
Prof. Matteo Fischetti
DEI, University of Padova
via Gradenigo 6/A
I-35131 Padova (Italy)
e-mail: [email protected]
web: www.dei.unipd.it/~fisch
reports: www.dei.unipd.it/~fisch/papers
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
