
From:  Edd Barrett 
Subject:  Re: [Helpglpk] glpsol, arbitrary precision and large numbers 
Date:  Sat, 30 Jun 2012 01:12:21 +0100 
I see. One further question; am I likely to run into similar problems using other solvers?
For example PPL has been used to verify C and C++ code. Thus, 32 and 64 bit numbers mist be analysed.
And thanks for your help. Most appreciated.
Cheers
> 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 32bit 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 32bit numbers. If I analyse 16bit 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?
>
Being numerical procedures both the glpk integer optimizer and
underlying simplex solver work with a finite relative precision, and you
should not expect that the simplex solver is able to obtain an exact
solution even if your input data are integral (i.e. free of roundoff
errors). In other word, the constraint actually used on obtaining basic
solutions is the following:
s.t. c13: 4294967296 * dcsn_lte_0 + 1 * u_EAX_4008e0 <= 4 + eps;
where eps is a relative tolerance (1e7 by default). Because of very
large constraint coefficient (4294967296) there appears a large absolute
error on computing the values of dcsn_lte_0 and u_EAX_4008e0 in basic
solutions, that in turn leads to wrong results.
To avoid such error you need to reformulate your instance to avoid large
constraint coefficients as well as large rhs's.
[Prev in Thread]  Current Thread  [Next in Thread] 