[Top][All Lists]

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

Re: [Help-glpk] [Fwd: Numerical instability may cause re-ordering]

From: Robbie Morrison
Subject: Re: [Help-glpk] [Fwd: Numerical instability may cause re-ordering]
Date: Mon, 18 Apr 2011 21:19:13 +1200 (NZST)
User-agent: SquirrelMail/1.4.17

Re: [Help-glpk] [Fwd: Numerical instability may cause re-ordering]

Hello Andrew

> ------------------------------------------------------------
> To:          address@hidden,
>              Robbie Morrison <address@hidden>,
>              address@hidden
> Subject:     Re: [Help-glpk] [Fwd: Numerical instability may cause
> Message-ID: <address@hidden>
> From:        Andrew Makhorin <address@hidden>
> Date:        Sun, 17 Apr 2011 18:54:17 +0400
> ------------------------------------------------------------
>> My application creates lots of flow network problems,
>> some are max-flow, some are min-cost. This one is
>> min-cost.
>> I have been recovering spurious results whenever I hit
>> the following problem:
>>   Warning: numerical instability (dual simplex, phase II)
> Your instance is badly scaled:
>>  A: min|aij| =  4.649e-08  max|aij| =  2.967e+08  ratio =  6.383e+15
> In this case using the geometric mean scaling is not
> reliable, so I'd suggest either to use only the
> equilibration scaling, or do not use the scaling at
> all.

Just a thought.  GLPK could be adaptive in this regard?
Or simply provide a "Hint: " to the console?  Or is
the underlying rule more complex than that?

On a similar note, is there any way of finding out
programmatically if the solver has issued warnings?
That way my code could react in a more intelligent

> You might remove tiny constraint coefficients by
> replacing them with exact zeros (looks like they are
> result of computations, where numeric cancellation does
> not occur due to round-off errors). However, if tiny
> constraint coefficients are result of using a "big M",
> then your M is too big.

I do use a big M to shutdown lightly loaded power plant
(just as a station operator would) but the M is carefully
sized each time.

But I am just about to code up a numerical zero
coefficient replacement routine using the following
fantastic little C++ header-only library:

  Boost floating-point representation distance (ULP) library

> In many cases a badly scaled instance leads to
> ill-conditioned basis matrices, in which case it is
> impossible to find basic solutions with sufficient
> accuracy.

One issue I face is that 1 kg of natural gas, when burnt
in air, produces 45e6 J of heat and around 50% of that is
convertible to electricity.  I currently carry base SI
units throughout, but there would be a good case for
using kg for mass and MJ for energy.

> PS: Your problem does not look like mincost. Any
> mincost problem has a 0-1 constraint matrix, which is
> the incidence matrix of a network.

Perhaps I should have said "minimum cost flow problem":

Thanks for pointing this out.  Many thanks too for your
informative reply, as always.  Robbie
Robbie Morrison
PhD student -- policy-oriented energy system simulation
Technical University of Berlin (TU-Berlin), Germany
University email (redirected) : address@hidden
Webmail (preferred)           : address@hidden
[from Webmail client]

reply via email to

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