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" <m...@gnu.org> 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. > > >
_______________________________________________ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
