[Help-glpk] Can I reuse a basis?

[Axel Simon]

Hi,

I'm trying to remove all redundancies from a system of linear
inequalities. This was discussed earlier on this list (July 18th, 2007),
but the suggested solution is not quite clear to me. I also have another
question.

The question first. Given a system

a1 x <= c1
a2 x <= c2
..
an x <= cn

where ai and x are vectors, one can create a GLPK problem instance with
all these constraints. Then, to test the first inequality for
redundancy, one sets the upper bound on a1 x to infinity and asks for
the maximum of a1 x. If the maximum is larger than c1, then the first
inequality is non-redundant. So far so good.

I'm interested in speeding this process up. So, in order to test the
second inequality, one re-instantiates the upper bound on the first
inequality and removes the bound on the second inequality. Suppose that
the maximum of a1 x was larger than c1 such that the current basis
describes a point that lies outside of the feasible space. Will GLPK
reuse the current basis, even though the current basis describes a point
that lies outside of the feasible space? If not, does it reuse the basis
when the the maximum was smaller than c1 (i.e. the constraint was
redundant) such that the basis describes a feasible point? If the
answers are 'no' and 'yes', then I could ask for the minimum whenever a
constraint is non-redundant in order to move the basis back to a
feasible point.

The second question relates to the answer given in

http://lists.gnu.org/archive/html/help-glpk/2007-07/msg00031.html

As I understand, a vertex of the polyhedron is non-degenerate if it can
only be described by one unique combination of constraints. But how do I
get this information from GLPK? I suppose its somewhere in
glp_eval_tab_col, but I don't see it.

Furthermore, for degenerate points, it was suggested that one could
infer that a constraint is redundant by looking at its reduced cost. How
do I ask GLPK about the reduced cost (there's lpx_prim_ratio_test but it
talks about columns)? If a constraint is redundant then it must have a
reduced cost of zero, but this is only a sufficient condition, right?

And help appreciated, many thanks in advance,
Axel.