Re: [Help-glpk] Simplex vertex neighborhood

[Matteo Fischetti DEI]

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
> address@hidden
> 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: address@hidden
web: www.dei.unipd.it/~fisch
reports: www.dei.unipd.it/~fisch/papers