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. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
