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
var u_EBX_4008e5_blk_ex, >=0, <= 4294967295;
var u_EAX_4008e0_blk_ex_T, >=0, <= 4294967295;
var u_EBX_4008e7_blk_ex, >=0, <= 4294967295;
var l_EAX_4008e0, >=0, <= 4294967295;
var l_EAX_4008e3, >=0, <= 4294967295;
var l_EAX_4008e5, >=0, <= 4294967295;
var l_EAX_4008e7, >=0, <= 4294967295;
var l_EAX_4008e6, >=0, <= 4294967295;
var u_EAX_4008e0_blk_ex_F, >=0, <= 4294967295;
var rch_blk_4008e0_ent, binary;
var u_EAX_4008e5_blk_ex, >=0, <= 4294967295;
var u_EBX_4008e0_blk_ex_F, >=0, <= 4294967295;
var l_EAX_4008e0_blk_ex_T, >=0, <= 4294967295;
var l_EAX_4008e7_blk_ex, >=0, <= 4294967295;
var dcsn_lte_3, binary;
var dcsn_lte_2, binary;
var dcsn_lte_1, binary;
var dcsn_lte_0, binary;
var l_EAX_4008e0_blk_ex_F, >=0, <= 4294967295;
var u_EBX_4008e0_blk_ex_T, >=0, <= 4294967295;
var l_EBX_4008e5_blk_ex, >=0, <= 4294967295;
var rch_blk_4008e0_ex_F, binary;
var u_EBX_4008e0, >=0, <= 4294967295;
var u_EBX_4008e3, >=0, <= 4294967295;
var u_EBX_4008e5, >=0, <= 4294967295;
var u_EBX_4008e7, >=0, <= 4294967295;
var u_EBX_4008e6, >=0, <= 4294967295;
var rch_blk_4008e0_ex_T, binary;
var u_EAX_4008e5, >=0, <= 4294967295;
var rch_blk_4008e0_pred_T, binary;
var l_EBX_4008e7_blk_ex, >=0, <= 4294967295;
var rch_blk_4008e5_ex, binary;
var rch_blk_4008e5_ent, binary;
var u_EAX_4008e3, >=0, <= 4294967295;
var u_EAX_4008e0, >=0, <= 4294967295;
var u_EAX_4008e6, >=0, <= 4294967295;
var u_EAX_4008e7, >=0, <= 4294967295;
var rch_blk_4008e0_pred_F, binary;
var l_EAX_4008e5_blk_ex, >=0, <= 4294967295;
var rch_blk_4008e7_ex, binary;
var l_EBX_4008e0_blk_ex_F, >=0, <= 4294967295;
var l_EBX_4008e3, >=0, <= 4294967295;
var l_EBX_4008e0, >=0, <= 4294967295;
var l_EBX_4008e6, >=0, <= 4294967295;
var l_EBX_4008e7, >=0, <= 4294967295;
var rch_blk_4008e7_ent, binary;
var l_EBX_4008e5, >=0, <= 4294967295;
var u_EAX_4008e7_blk_ex, >=0, <= 4294967295;
var dcsn_and_5, binary;
var dcsn_and_4, binary;
var l_EBX_4008e0_blk_ex_T, >=0, <= 4294967295;
minimize obj_fn: + 1 * u_EAX_4008e0 -1 * l_EAX_4008e0 + 1 * u_EBX_4008e0 -1 *
l_EBX_4008e0 + 1 * u_EAX_4008e3 -1 * l_EAX_4008e3 + 1 * u_EBX_4008e3 -1 *
l_EBX_4008e3 + 1 * u_EAX_4008e0_blk_ex_T -1 * l_EAX_4008e0_blk_ex_T + 1 *
u_EBX_4008e0_blk_ex_T -1 * l_EBX_4008e0_blk_ex_T + 1 * u_EAX_4008e0_blk_ex_F -1
* l_EAX_4008e0_blk_ex_F + 1 * u_EBX_4008e0_blk_ex_F -1 * l_EBX_4008e0_blk_ex_F
+ 1 * u_EAX_4008e7 -1 * l_EAX_4008e7 + 1 * u_EBX_4008e7 -1 * l_EBX_4008e7 + 1 *
u_EAX_4008e7_blk_ex -1 * l_EAX_4008e7_blk_ex + 1 * u_EBX_4008e7_blk_ex -1 *
l_EBX_4008e7_blk_ex + 1 * u_EAX_4008e5 -1 * l_EAX_4008e5 + 1 * u_EBX_4008e5 -1
* l_EBX_4008e5 + 1 * u_EAX_4008e6 -1 * l_EAX_4008e6 + 1 * u_EBX_4008e6 -1 *
l_EBX_4008e6 + 1 * u_EAX_4008e5_blk_ex -1 * l_EAX_4008e5_blk_ex + 1 *
u_EBX_4008e5_blk_ex -1 * l_EBX_4008e5_blk_ex ;
s.t. c0: + 1 * l_EAX_4008e0 -1 * u_EAX_4008e0 <= 0;
s.t. c1: + 1 * l_EBX_4008e0 -1 * u_EBX_4008e0 <= 0;
s.t. c2: + 1 * l_EAX_4008e3 -1 * u_EAX_4008e3 <= 0;
s.t. c3: + 1 * l_EBX_4008e3 -1 * u_EBX_4008e3 <= 0;
s.t. c4: + 1 * l_EAX_4008e3 -1 * l_EAX_4008e0 = 0;
s.t. c5: + 1 * u_EAX_4008e3 -1 * u_EAX_4008e0 = 0;
s.t. c6: + 1 * l_EBX_4008e3 -1 * l_EBX_4008e0 = 0;
s.t. c7: + 1 * u_EBX_4008e3 -1 * u_EBX_4008e0 = 0;
s.t. c8: + 1 * l_EAX_4008e0_blk_ex_T -1 * u_EAX_4008e0_blk_ex_T <= 0;
s.t. c9: + 1 * l_EBX_4008e0_blk_ex_T -1 * u_EBX_4008e0_blk_ex_T <= 0;
s.t. c10: + 1 * l_EAX_4008e0_blk_ex_F -1 * u_EAX_4008e0_blk_ex_F <= 0;
s.t. c11: + 1 * l_EBX_4008e0_blk_ex_F -1 * u_EBX_4008e0_blk_ex_F <= 0;
s.t. c12: + 4294967296 * dcsn_lte_0 -1 * u_EAX_4008e0 <= 4294967291;
s.t. c13: -4294967296 * dcsn_lte_0 + 1 * u_EAX_4008e0 <= 4;
s.t. c14: + 1 * rch_blk_4008e0_pred_T -1 * dcsn_lte_0 = 0;
s.t. c15: -1 * u_EAX_4008e0 + 1 * u_EAX_4008e0_blk_ex_T = 0;
s.t. c16: -1 * l_EAX_4008e0 + 4294967296 * dcsn_lte_1 <= 4294967291;
s.t. c17: + 1 * l_EAX_4008e0 -4294967296 * dcsn_lte_1 <= 4;
s.t. c18: + 1 * l_EAX_4008e0_blk_ex_T -1 * l_EAX_4008e0 + 4294967296 *
dcsn_lte_1 <= 4294967296;
s.t. c19: + 1 * l_EAX_4008e0_blk_ex_T -4294967296 * dcsn_lte_1 <= 5;
s.t. c20: + 4294967296 * dcsn_lte_2 + 1 * l_EAX_4008e0 <= 4294967300;
s.t. c21: -4294967296 * dcsn_lte_2 -1 * l_EAX_4008e0 <= -5;
s.t. c22: + 1 * rch_blk_4008e0_pred_F -1 * dcsn_lte_2 = 0;
s.t. c23: -1 * l_EAX_4008e0 + 1 * l_EAX_4008e0_blk_ex_F = 0;
s.t. c24: + 4294967296 * dcsn_lte_3 + 1 * u_EAX_4008e0 <= 4294967300;
s.t. c25: -4294967296 * dcsn_lte_3 -1 * u_EAX_4008e0 <= -5;
s.t. c26: + 4294967296 * dcsn_lte_3 -1 * u_EAX_4008e0_blk_ex_F + 1 *
u_EAX_4008e0 <= 4294967296;
s.t. c27: -4294967296 * dcsn_lte_3 -1 * u_EAX_4008e0_blk_ex_F <= -4;
s.t. c28: + 1 * l_EBX_4008e0_blk_ex_T -1 * l_EBX_4008e3 = 0;
s.t. c29: + 1 * u_EBX_4008e0_blk_ex_T -1 * u_EBX_4008e3 = 0;
s.t. c30: + 1 * l_EBX_4008e0_blk_ex_F -1 * l_EBX_4008e3 = 0;
s.t. c31: + 1 * u_EBX_4008e0_blk_ex_F -1 * u_EBX_4008e3 = 0;
s.t. c32: -2 * dcsn_and_4 + 1 * rch_blk_4008e0_ent + 1 * rch_blk_4008e0_pred_T
<= 1;
s.t. c33: + 2 * dcsn_and_4 -1 * rch_blk_4008e0_ent -1 * rch_blk_4008e0_pred_T
<= 0;
s.t. c34: + 1 * rch_blk_4008e0_ex_T -1 * dcsn_and_4 = 0;
s.t. c35: + 1 * rch_blk_4008e0_pred_F + 1 * rch_blk_4008e0_ent -2 * dcsn_and_5
<= 1;
s.t. c36: -1 * rch_blk_4008e0_pred_F -1 * rch_blk_4008e0_ent + 2 * dcsn_and_5
<= 0;
s.t. c37: + 1 * rch_blk_4008e0_ex_F -1 * dcsn_and_5 = 0;
s.t. c38: + 1 * l_EAX_4008e7 -1 * u_EAX_4008e7 <= 0;
s.t. c39: + 1 * l_EBX_4008e7 -1 * u_EBX_4008e7 <= 0;
s.t. c40: + 1 * l_EAX_4008e7_blk_ex -1 * u_EAX_4008e7_blk_ex <= 0;
s.t. c41: + 1 * l_EBX_4008e7_blk_ex -1 * u_EBX_4008e7_blk_ex <= 0;
s.t. c42: + 1 * l_EAX_4008e7_blk_ex -1 * l_EAX_4008e7 = 0;
s.t. c43: + 1 * u_EAX_4008e7_blk_ex -1 * u_EAX_4008e7 = 0;
s.t. c44: + 1 * l_EBX_4008e7_blk_ex -1 * l_EBX_4008e7 = 0;
s.t. c45: + 1 * u_EBX_4008e7_blk_ex -1 * u_EBX_4008e7 = 0;
s.t. c46: + 1 * rch_blk_4008e7_ex -1 * rch_blk_4008e7_ent = 0;
s.t. c47: + 1 * l_EAX_4008e5 -1 * u_EAX_4008e5 <= 0;
s.t. c48: + 1 * l_EBX_4008e5 -1 * u_EBX_4008e5 <= 0;
s.t. c49: + 1 * l_EAX_4008e6 -1 * u_EAX_4008e6 <= 0;
s.t. c50: + 1 * l_EBX_4008e6 -1 * u_EBX_4008e6 <= 0;
s.t. c51: + 1 * l_EAX_4008e6 -1 * l_EAX_4008e5 = 0;
s.t. c52: + 1 * u_EAX_4008e6 -1 * u_EAX_4008e5 = 0;
s.t. c53: + 1 * l_EBX_4008e6 -1 * l_EBX_4008e5 = 0;
s.t. c54: + 1 * u_EBX_4008e6 -1 * u_EBX_4008e5 = 0;
s.t. c55: + 1 * l_EAX_4008e5_blk_ex -1 * u_EAX_4008e5_blk_ex <= 0;
s.t. c56: + 1 * l_EBX_4008e5_blk_ex -1 * u_EBX_4008e5_blk_ex <= 0;
s.t. c57: + 1 * l_EAX_4008e5_blk_ex -1 * l_EAX_4008e6 = 0;
s.t. c58: + 1 * u_EAX_4008e5_blk_ex -1 * u_EAX_4008e6 = 0;
s.t. c59: + 1 * l_EBX_4008e5_blk_ex -1 * l_EBX_4008e6 = 0;
s.t. c60: + 1 * u_EBX_4008e5_blk_ex -1 * u_EBX_4008e6 = 0;
s.t. c61: + 1 * rch_blk_4008e5_ex -1 * rch_blk_4008e5_ent = 0;
s.t. c62: + 1 * l_EAX_4008e0 = 8;
s.t. c63: + 1 * u_EAX_4008e0 = 9;
s.t. c64: + 1 * l_EBX_4008e0 = 0;
s.t. c65: + 1 * u_EBX_4008e0 = 4294967295;
s.t. c66: + 1 * rch_blk_4008e0_ent = 1;
s.t. c67: + 1 * rch_blk_4008e7_ent -1 * rch_blk_4008e0_ex_T = 0;
s.t. c68: -1 * l_EAX_4008e0_blk_ex_T + 1 * l_EAX_4008e7 + 4294967296 *
rch_blk_4008e7_ent <= 4294967296;
s.t. c69: + 4294967296 * rch_blk_4008e7_ent + 1 * u_EAX_4008e0_blk_ex_T -1 *
u_EAX_4008e7 <= 4294967296;
s.t. c70: + 4294967296 * rch_blk_4008e7_ent -1 * l_EBX_4008e0_blk_ex_T + 1 *
l_EBX_4008e7 <= 4294967296;
s.t. c71: + 1 * u_EBX_4008e0_blk_ex_T + 4294967296 * rch_blk_4008e7_ent -1 *
u_EBX_4008e7 <= 4294967296;
s.t. c72: + 1 * rch_blk_4008e5_ent -1 * rch_blk_4008e0_ex_F = 0;
s.t. c73: + 1 * l_EAX_4008e5 + 4294967296 * rch_blk_4008e5_ent -1 *
l_EAX_4008e0_blk_ex_F <= 4294967296;
s.t. c74: -1 * u_EAX_4008e5 + 4294967296 * rch_blk_4008e5_ent + 1 *
u_EAX_4008e0_blk_ex_F <= 4294967296;
s.t. c75: + 1 * l_EBX_4008e5 + 4294967296 * rch_blk_4008e5_ent -1 *
l_EBX_4008e0_blk_ex_F <= 4294967296;
s.t. c76: -1 * u_EBX_4008e5 + 4294967296 * rch_blk_4008e5_ent + 1 *
u_EBX_4008e0_blk_ex_F <= 4294967296;
Problem: glpsol
Rows: 78
Columns: 51 (15 integer, 15 binary)
Non-zeros: 199
Status: INTEGER OPTIMAL
Objective: obj_fn = 1.717986918e+10 (MINimum)
No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 obj_fn 1.71799e+10
2 c0 -1 -0
3 c1 -4.29497e+09 -0
4 c2 -1 -0
5 c3 -4.29497e+09 -0
6 c4 0 -0 =
7 c5 0 -0 =
8 c6 0 -0 =
9 c7 0 -0 =
10 c8 -1 -0
11 c9 -4.29497e+09 -0
12 c10 0 -0
13 c11 -4.29497e+09 -0
14 c12 -9 4.29497e+09
15 c13 9 4
16 c14 0 -0 =
17 c15 0 -0 =
18 c16 4.29497e+09 4.29497e+09
19 c17 -4.29497e+09 4
20 c18 4.29497e+09 4.29497e+09
21 c19 -4.29497e+09 5
22 c20 8 4.29497e+09
23 c21 -8 -5
24 c22 0 -0 =
25 c23 0 -0 =
26 c24 9 4.29497e+09
27 c25 -9 -5
28 c26 1 4.29497e+09
29 c27 -8 -4
30 c28 0 -0 =
31 c29 0 -0 =
32 c30 0 -0 =
33 c31 0 -0 =
34 c32 1 1
35 c33 -1 -0
36 c34 0 -0 =
37 c35 1 1
38 c36 -1 -0
39 c37 0 -0 =
40 c38 0 -0
41 c39 0 -0
42 c40 0 -0
43 c41 0 -0
44 c42 0 -0 =
45 c43 0 -0 =
46 c44 0 -0 =
47 c45 0 -0 =
48 c46 0 -0 =
49 c47 0 -0
50 c48 0 -0
51 c49 0 -0
52 c50 0 -0
53 c51 0 -0 =
54 c52 0 -0 =
55 c53 0 -0 =
56 c54 0 -0 =
57 c55 0 -0
58 c56 0 -0
59 c57 0 -0 =
60 c58 0 -0 =
61 c59 0 -0 =
62 c60 0 -0 =
63 c61 0 -0 =
64 c62 8 8 =
65 c63 9 9 =
66 c64 0 -0 =
67 c65 4.29497e+09 4.29497e+09 =
68 c66 1 1 =
69 c67 0 -0 =
70 c68 -8 4.29497e+09
71 c69 9 4.29497e+09
72 c70 0 4.29497e+09
73 c71 4.29497e+09 4.29497e+09
74 c72 0 -0 =
75 c73 -8 4.29497e+09
76 c74 8 4.29497e+09
77 c75 0 4.29497e+09
78 c76 4.29497e+09 4.29497e+09
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 u_EBX_4008e5_blk_ex
0 0 4.29497e+09
2 u_EAX_4008e0_blk_ex_T
9 0 4.29497e+09
3 u_EBX_4008e7_blk_ex
0 0 4.29497e+09
4 l_EAX_4008e0 8 0 4.29497e+09
5 l_EAX_4008e3 8 0 4.29497e+09
6 l_EAX_4008e5 0 0 4.29497e+09
7 l_EAX_4008e7 0 0 4.29497e+09
8 l_EAX_4008e6 0 0 4.29497e+09
9 u_EAX_4008e0_blk_ex_F
8 0 4.29497e+09
10 rch_blk_4008e0_ent
* 1 0 1
11 u_EAX_4008e5_blk_ex
0 0 4.29497e+09
12 u_EBX_4008e0_blk_ex_F
4.29497e+09 0 4.29497e+09
13 l_EAX_4008e0_blk_ex_T
8 0 4.29497e+09
14 l_EAX_4008e7_blk_ex
0 0 4.29497e+09
15 dcsn_lte_3 * 0 0 1
16 dcsn_lte_2 * 0 0 1
17 dcsn_lte_1 * 1 0 1
18 dcsn_lte_0 * 0 0 1
19 l_EAX_4008e0_blk_ex_F
8 0 4.29497e+09
20 u_EBX_4008e0_blk_ex_T
4.29497e+09 0 4.29497e+09
21 l_EBX_4008e5_blk_ex
0 0 4.29497e+09
22 rch_blk_4008e0_ex_F
* 0 0 1
23 u_EBX_4008e0 4.29497e+09 0 4.29497e+09
24 u_EBX_4008e3 4.29497e+09 0 4.29497e+09
25 u_EBX_4008e5 0 0 4.29497e+09
26 u_EBX_4008e7 0 0 4.29497e+09
27 u_EBX_4008e6 0 0 4.29497e+09
28 rch_blk_4008e0_ex_T
* 0 0 1
29 u_EAX_4008e5 0 0 4.29497e+09
30 rch_blk_4008e0_pred_T
* 0 0 1
31 l_EBX_4008e7_blk_ex
0 0 4.29497e+09
32 rch_blk_4008e5_ex
* 0 0 1
33 rch_blk_4008e5_ent
* 0 0 1
34 u_EAX_4008e3 9 0 4.29497e+09
35 u_EAX_4008e0 9 0 4.29497e+09
36 u_EAX_4008e6 0 0 4.29497e+09
37 u_EAX_4008e7 0 0 4.29497e+09
38 rch_blk_4008e0_pred_F
* 0 0 1
39 l_EAX_4008e5_blk_ex
0 0 4.29497e+09
40 rch_blk_4008e7_ex
* 0 0 1
41 l_EBX_4008e0_blk_ex_F
0 0 4.29497e+09
42 l_EBX_4008e3 0 0 4.29497e+09
43 l_EBX_4008e0 0 0 4.29497e+09
44 l_EBX_4008e6 0 0 4.29497e+09
45 l_EBX_4008e7 0 0 4.29497e+09
46 rch_blk_4008e7_ent
* 0 0 1
47 l_EBX_4008e5 0 0 4.29497e+09
48 u_EAX_4008e7_blk_ex
0 0 4.29497e+09
49 dcsn_and_5 * 0 0 1
50 dcsn_and_4 * 0 0 1
51 l_EBX_4008e0_blk_ex_T
0 0 4.29497e+09
Integer feasibility conditions:
KKT.PE: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
KKT.PB: max.abs.err = 5.00e+00 on row 15
max.rel.err = 1.00e+00 on row 15
SOLUTION IS INFEASIBLE
End of output
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
