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