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

[Robbie Morrison]

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
re-ordering
> 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
fashion.

> 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.Math.Special_functions.Next
  Boost floating-point representation distance (ULP) library
  
http://www.boost.org/doc/libs/1_46_1/libs/math/doc/sf_and_dist/html/math_toolkit/utils/next_float.html

> 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":

  http://en.wikipedia.org/wiki/Minimum_cost_flow_problem
  http://en.wikipedia.org/wiki/Flow_network

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]