[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Fixing Numerical Instability Problems

From: glpk xypron
Subject: Re: [Help-glpk] Fixing Numerical Instability Problems
Date: Fri, 18 Mar 2011 21:25:57 +0100

Hello Glenn,

the presolver of GLPK 4.45 cannot eliminate duplicate rows.

I suggested to update GLPK:

You can checkout the patched version with
svn co

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

Best regards


-------- 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!

reply via email to

[Prev in Thread] Current Thread [Next in Thread]