[Help-glpk] Re: GLPK and redundant constraints

[Andrew Makhorin]

>I've recently started using the GLPK in a programming project.  The 
>code repeatedly solves linear programs adding additional constraints 
>based on the results of the previous linear program.
>
>Many of the contraints generated will be redundant.
>
>Will passing redundant constraints to the GLPK cause any problems?

Theoretically redundant constraints must cause no problems. However in
practice it depends on whether the problem is well conditioned or not.
Let, for example, there be a set of linearly dependent and therefore
redundant equality constraints; in inexact arithmetic these constraints
may become almost linearly dependent and making the problem
ill conditioned may cause numerical instability. Not analyzing
a particular problem it's difficult to say a priori if this will happen
or not.

>Is there an efficient way to decide whether a given constraint is 
>redundant?  Will removing the redundant constraints significantly speed up 
>the solving of the linear program?

Detecting redundant equality constraints (i.e. linearly dependent
equations) is relatively easy using standard methods of linear algebra.
Detecting redundant inequality constraints is much harder (in general
case), because detecting *one* such constraint requires, roughly
speaking, solving an LP problem. Of course, other ways are possible,
for example, some presolving techniques might be used, but they can't
guarantee that all redundant inequality constraints will be detected.

The main reason due to which redundant constraints are undesirable and
should be removed is that they may worsen numerical properties of the
problem. If the problem remains well conditioned, such constraints
practically don't affect the efficiency of the simplex method.

Andrew Makhorin