Re: [Help-glpk] Enumerating the vertex neighborhood

[Andrew Makhorin]

>Because of convexity issues in the problem I'm currently studying, I
>want to obtain the neighbors of the optimal vertice.

If you want to enumerate all alternative optimal vertices, there may be
at least two problems: i) in general case the number of such vertices
may be exponential; ii) due to finite precision arithmetic it may be
difficult to distinguish between optimal and non-optimal or infeasible
vertices.

> The easiest way for 
>this is to start from the simplex tableau corresponding to the optimal 
>solution, and make a pivot operation with each non-basis [auxiliary or 
>stuctural] variable, one after the other.

You may introduce the constraint <objective> = Zopt, where Zopt is an
optimal value of the objective, to construct the polyhedron of all
optimal solutions, and then enumerate all its feasible basic solutions
(which all are obviously optimal). The latter problem is equivalent to
enumerating of all vertices of an undirected graph, where two vertices
are adjacent if they are adjacent in the polyhedron (i.e. differ only
in statuses of two variables), so, say, the depth-first-search algorithm
may be used.

>I was thinking of using lpx_eval_tab_{row,col} with 
>lpx_{prim,dual}_ratio_test to be given the variable leaving the basis 
>when the selected non-basic variable is forced to enter. But I couldn't 
>manage to "fix" this state and get the new values (of course, values are 
>not automatically recomputed when operations are done on the basis, and 
>lpx_simplex juste gives me the same optimal value).

Glpk does not automatically recompute values of variables once the
current basis has been changed. You need to explicitly do that using
the api routine lpx_warm_up.

>So, is there a way to fix the status of a variable ? Or force a pivot 
>operation on a given variable ?

To force a basic variable not to leave the basis it is sufficient to
make it free (LPX_FR). Analogously, to force a non-basic variable not to
enter the basis it is sufficient to make it fixed (LPX_FX) at current
bound.

>Bonus question : what is the meaning of the "how" argument in the 
>lpx_{prim,dual}_ratio_test functions ? My limited kowledge in this area 
>tells me that, on entering or leaving the basis, a variable has a 
>deterministic behaviour.  therefore I don't see what is the use of this 
>parameter.

The routine lpx_prim_ratio_test assumes that *the bound* on which the
specified non-basic variable is currently set starts changing, that, in
turn, causes changing the non-basic variable itself (and this changing
stops once a basic variable reported by the routine reaches its bound
first). The parameter how specifies whether the bound starts increasing
or decreasing; it is understood that both cases are possible. The
routine lpx_dual_ratio_test works in a similar way with exception that
the current (zero) bound of corresponding dual variable is assumed.

Andrew Makhorin