
From:  Matteo Fischetti DEI 
Subject:  Re: [Helpglpk] Simplex vertex neighborhood 
Date:  Fri, 16 Aug 2013 19:41:17 +0200 
Useragent:  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 otherwisethis 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) nm 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 nm 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 20130816 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 _______________________________________________ Helpglpk mailing list address@hidden https://lists.gnu.org/mailman/listinfo/helpglpk
 Prof. Matteo Fischetti DEI, University of Padova via Gradenigo 6/A I35131 Padova (Italy) email: address@hidden web: www.dei.unipd.it/~fisch reports: www.dei.unipd.it/~fisch/papers
[Prev in Thread]  Current Thread  [Next in Thread] 