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

[Edd Barrett]

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

On Jun 29, 2012 8:32 PM, "Andrew Makhorin" <address@hidden> wrote:

> 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?
>

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 round-off
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 (1e-7 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.