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, <[EMAIL PROTECTED]> 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 > [email protected] > http://lists.gnu.org/mailman/listinfo/help-glpk _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
