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