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

[Maurice.Djona]

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  #43;0300; Subject: Re: 
GLPK and redundant constraints), you wrote: 
 #8220;Detecting redundant inequality constraints is much harder (in general 
case), because detecting *one* such constraint requires, roughly speaking, 
solving an LP problem #8221;.

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  #43; a12x2  #43; a13x3  #43; a14x4 <= 0
R2: a21x1  #43; a22x2  #43; a23x3  #43; a24x4 <= 0
R3: a31x1  #43; a32x2  #43; a33x3  #43; a34x4 <= 0
R4: a41x1  #43; a42x2  #43; a43x3  #43; a44x4 <= 0
R5: a51x1  #43; a52x2  #43; a53x3  #43; 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

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

Part2.txt
Description: Text document