Re: [Help-glpk] information on presolve results

[Andrew Makhorin]

> One reason is debugging. I generate the LP problems by linearizing
> nonlinear problems. A redundant nonlinear constraint may or may not be
> nonredundant in the LP problem after linearization. Identifying
> redundant rows / columns could help me debugging the nonlinear part.
> Another reason is numerical stability and performance issues.

> What do you advise?

I think that using the lp presolver for such kind of debugging is not
a good idea.

If you need to know whether some constraint is redundant or not in the
primal space, you can compute its implied bounds by minimizing and
maximizing the corresponding linear form. For example, if you have
a constraint 3 <= x1 + 2 x2 + 3 x3 <= 7, and minimizing x1 + 2 x2 + 3 x3
gives 3.5, then the lower bound, which is 3, is redundant, since this
bound cannot be active. Note that the same can be applied to bounds of
variables.

Redundancy may also appear in the dual space, when zero bounds of some
Lagrange multipliers (i.e. reduced costs) cannot be active, due to which
corresponding primal variables (slacks and structurals) can only be
non-basic and therefore fixed at their bounds. To take this into
consideration you may include in the instance the following equality
constraint: sum c[j] * x[j] = z*, where sum c[j] * x[j] is the objective
function, z* is its optimal value. This constraint reduces the polyhedron
of primal feasible solutions to the polyhedron of optimal solutions in
the primal space.

Probably the following four articles by Harvey Greenberg might be
interesting to you http://www-math.cudenver.edu/~hgreenbe/pubs.shtml :

How to analyze results of linear programs, Part 1: Preliminaries,
Interfaces 23:4 (1993), 56-67. (Available as pdf file.)

How to analyze results of linear programs, Part 2: Price interpretation,
Interfaces 23:5 (1993), 97-114. (Available as pdf file.)

How to analyze results of linear programs, Part 3: Infeasibility
diagnosis, Interfaces 23:6 (1993), 120-139. (Available as pdf file.)

How to analyze results of linear programs, Part 4: Forcing
substructures, Interfaces 24:1 (1994), 121-130. (Available as pdf file.)