[Top][All Lists]

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

Re: [Help-glpk] Working with larger numbers

From: Andrew Makhorin
Subject: Re: [Help-glpk] Working with larger numbers
Date: Wed, 30 Jul 2008 12:55:58 +0400

> I was suprised that standard glpsol reports perfect results. Then I
> tried "glpsol --exact" and the result changed. For example, using the
> attached  mps file:
>  (i) "glpsol" reports "objval =   6.750000000e+10"
>  (ii) "glpsol --exact" reports "objval =       67500000001.0831"

Gotcha! Thank you for your test instance.

In fact, glp_simplex finds an integral, correct solution. The
round-off errors appear in lpx_exact on converting problem data to
rational numbers. Currently there is no check that a floating-point
number to be converted is integral, and the converting routine just
replaces x by fraction p / q, where p and q are chosen to provide
precision with at least 9 decimal figures: |x - p / q| <= 1e-9 * |x|.
So large numbers (arc capacities in your model) are converted with
round-off error. For example, 12649896000 is converted to
(13457 / 18276) * 2^34 = 12649896017.131... .

I will made necessary changes and can post you a patched version of
lpx_exact. However, you do not need to use it, because glp_simplex
works correctly.

> Hmm. Can it be that "lpx_write_cpxlp" converts bounds this way?

No. In your model all variables are non-negative and have no upper
bounds, and for each flow there are two general constraints.

Andrew Makhorin

reply via email to

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