Re: [Help-glpk] Please help: identifying redundant inequalities using GLPK

[Michael Hennebry]

On Tue, 17 Jul 2007, Sebastian Pokutta wrote:

> you can do the following: Say you want to check if constraint cx <=
> delta is redundant. Then take the other constraints (say as matrix)
> Ax <= b and maximize cx over this system. Let the objective function
> value be gamma. Then cx <= gamma is valid for P. If now gamma <=
> delta then the constraint cx <= delta is redundant as the system Ax
> <= b already implies cx <= gamma <= delta. Hence you can remove this
> constraint.
>
> Now you proceed iteratively.

The process can be speeded up a bit by noting
that at a non-degenerate basic point,
none of the binding constraints are redundant.
At a degenerate basic point,
one might determine redundancy or not of
some tight nonbasic constraints by examining
the "reduced costs" associated with them.

-- 
Mike   address@hidden
"Horse guts never lie."  -- Cherek Bear-Shoulders