Re: [Help-glpk] [Fwd: Numerical instability may cause re-ordering] Hello Andrew
> ------------------------------------------------------------ > To: [email protected], > Robbie Morrison <[email protected]>, > [email protected] > Subject: Re: [Help-glpk] [Fwd: Numerical instability may cause re-ordering > Message-ID: <1303052058.2951.16.camel@corvax> > From: Andrew Makhorin <[email protected]> > 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) : [email protected] Webmail (preferred) : [email protected] [from Webmail client] _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
