[Top][All Lists]

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

Re: [Help-glpk] Simplex vertex neighborhood

From: Matteo Fischetti DEI
Subject: Re: [Help-glpk] Simplex vertex neighborhood
Date: Fri, 16 Aug 2013 19:41:17 +0200
User-agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130801 Thunderbird/17.0.8

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.


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?


Help-glpk mailing list

Prof. Matteo Fischetti
DEI, University of Padova
via Gradenigo 6/A
I-35131 Padova (Italy)
e-mail: address@hidden

reply via email to

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