Re: [Help-glpk] Fixing Numerical Instability Problems

[glpk xypron]

Hello Glenn,

the presolver of GLPK 4.45 cannot eliminate duplicate rows.

I suggested to update GLPK:
http://lists.gnu.org/archive/html/help-glpk/2010-10/msg00045.html
http://lists.gnu.org/archive/html/help-glpk/2010-11/msg00013.html

You can checkout the patched version with
svn co http://www.xypron.de/svn/glpk/branches/glpk-4.44-npp

Hopefully Andrew will include duplicate row removal in a future
release of GLPK.

Best regards

Xypron


-------- Original-Nachricht --------
> Datum: Thu, 17 Mar 2011 17:26:13 -0500
> Betreff: [Help-glpk] Fixing Numerical Instability Problems

> 
> Hi,
> 
> I have an application that solves tens of million of tiny LPs coming
> from matrix games.  On checking the kkt optimality conditions, there
> are a dozen cases where both the primal and dual solutions are
> incorrect, and about one hundred cases with low quality dual or primal
> feasibility.  The LPs were scaled using the parameter "GLP_SF_AUTO".
>  I'm hoping there is some way to fix these problem cases by re-solving
> the LP with different parameters.  The problem cases generally seem to
> have multiple constraints that are identical; I suspect that this is
> the source of the problem.
> 
> I'm thinking that I might be able to fix this by enabling the
> presolver.  For efficiency reasons, it seems to make sense to
> selectively enable the presolver for the LPs that don't satisfy the kkt
> optimality conditions? But quoting the manual -- "Presolving may be
> used when the problem instance is solved for the first time.  However,
> on performing re-optimization the presolver should be disabled."  This
> seems to imply that I shouldn't solve a problem with presolver disabled
> and then try to correct it by re-optimizing with the presolver.  I.e. I
> should use the presolver on all instances.  Is this right?  Also, since
> the LPs are of the same size and are dense, I set up the LP once and
> then on successive LPs, change the matrix values and reload it.  Does
> this qualify as a re-optimization where the presolver should be
> disabled? 
> 
> -- Glenn C. Rhoads

-- 
Empfehlen Sie GMX DSL Ihren Freunden und Bekannten und wir
belohnen Sie mit bis zu 50,- Euro! https://freundschaftswerbung.gmx.de