[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Please help: identifying redundant inequalities using GL
From: |
Michael Hennebry |
Subject: |
Re: [Help-glpk] Please help: identifying redundant inequalities using GLPK |
Date: |
Wed, 18 Jul 2007 10:44:54 -0500 (CDT) |
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