Thank you for your detailed response, it is very helpful. I hoped that the presolve might help, but indeed it is not a good idea.
Ali On Jan 10, 2008 5:37 PM, Andrew Makhorin <[EMAIL PROTECTED]> wrote: > > 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
