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

[Sebastian Pokutta]

Dear Maurice,

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.

Greets,
Sebastian

On 17.07.2007, at 11:33, <address@hidden> wrote:

> Dear Dr Makhorin,
>
> First, congratulation for the impressive work on GLPK.
>
> I have a program that uses GLPK to solve linear programs containing  
> inequality constraints, some of which can be redundant.
>
> One requirement of the program is to systematically identify and  
> remove redundant constraints (so as to show the user the reduced  
> set of constraints).
>
> How can I systematically detect redundant inequality constraints  
> using GLPK?
> In a previous reply  (Date:  Tue, 14 Jan 2003 00:51:52 +0300;  
> Subject: Re: GLPK and redundant constraints), you wrote:
> “Detecting redundant inequality constraints is much harder (in  
> general case), because detecting *one* such constraint requires,  
> roughly speaking, solving an LP problem”.
>
> Could you please give me some details on how to detect redundant  
> inequalities by solving LP problems?
>
> For example, if the constraints are like:
> R1: a11x1 + a12x2 + a13x3 + a14x4 <= 0
> R2: a21x1 + a22x2 + a23x3 + a24x4 <= 0
> R3: a31x1 + a32x2 + a33x3 + a34x4 <= 0
> R4: a41x1 + a42x2 + a43x3 + a44x4 <= 0
> R5: a51x1 + a52x2 + a53x3 + a54x4 <= 0
> (xi >= 0).
>
> How would I use GLPK to systematically check if any of constraints  
> R1 to R5 is redundant?
>
> Thank you very much for any suggestion.
>
>
> Maurice Djona
> Division du développement de systèmes
> Statistique Canada
> Pré-Tunney, immeuble R.-H.-Coats, 14A
> Ottawa, ON, K1A 0T6
> Tél.: (613) 951-5331 Téléc.: (613) 951-0607
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk