Re: [Help-glpk] information on presolve results

[Ali Baharev]

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 <address@hidden> 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.)
>
>
>