Re: [Help-glpk] glpsol, arbitrary precision and large numbers

[Edd Barrett]

On Mon, Jun 25, 2012 at 05:42:23PM +0400, Andrew Makhorin wrote:
> > I guess my question is, can I model these large numbers with GLPK and if
> > so, can glpsol print the unrounded outcomes of variables? Is my approach
> > just fundamentally flawed altogether?
> 
> All glpk routines use 64-bit floating-point arithmetic. (The only
> exception is the exact simplex solver, which converts input data from
> the floating-point format to rational numbers, solves the lp instance in
> rationals, and then converts the solution from rationals back to the
> floating-point format.) Thus, it is impossible to use exact arithmetic
> in MathProg models as well as to obtain solutions in that format.

Thanks for the clarification. So I figure I should be fine to analyse 32-bit
numbers; plenty of precision.

However, I am seeing some strange results when using large numbers in
[-2^32, 2^32]. If I am interpreting the glpsol output correctly, I think
we may have a bug on our hands (or maybe I have misunderstood). Let me try to
explain:

I am looking at this constraint (in GNU mathprog syntax):

s.t. c13: -4294967296 * dcsn_lte_0 + 1 * u_EAX_4008e0 <= 4;

The idea here is that dcsn_lte_0 must equal 1 to satisfy this constraint
if u_EAX_4008e0 is strictly greater than 4. The types of these variables
are as follows:

var dcsn_lte_0, binary;
var u_EAX_4008e0, >=0, <= 4294967295;

The latter variable is representing a unsigned 32-bit integer.

When this is solved (with --exact --noscale), glpsol tells me "INTEGER
OPTIMAL SOLUTION FOUND" and the variable assignments in the solution are
as follows:

No.    Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
18 dcsn_lte_0   *              0             0             1
35 u_EAX_4008e0                9             0   4.29497e+09

and the row solution:

No.    Row name        Activity      Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
15     c13                   9                           4

If we plug the assignment into the original constraint, then we get:

-4294967296 * 0 + 1 * 9 <= 4
therefore: 9 <= 4

Which is false, so under this assignment the system in infeasible. The solver
should have either tried a different assignment of either variables, or if it
could not, then it should have reported the problem infeasible? Right?

This only seems to happen with 32-bit numbers. If I analyse 16-bit numbers, all
is well, so I wonder if it is precision based in some way.

Is this a bug, a misuse of glpk or a misunderstanding?

My environment:
OpenBSD-current/amd64 with glpk-4.47 (same result from glpk-4.44).

Also tried (with similar results) on:
Ubuntu-11.10/i686 with glpk-4.43

I am attaching my .mod file and .sol file. I apologise that the mod file is
not very readable; it was auto-generated.

I hope that is enough information. Cheers

-- 
Best Regards
Edd Barrett

http://www.theunixzoo.co.uk

glpsol.mod
Description: Text document

glpsol.sol
Description: Text document