Re: [Bug-glpk] Difference, 32bit build - 64bit build

[Andrew Makhorin]

> I have a difference with solving a larger problem on 32bit and 64bit
> linux, libglpk 4.31 build from tarball, no patches, gcc-4.1, no fancy
> optimizations, -O0.

> On 32bit, I get:

> address@hidden:/local/cullmann/build/libglpk.default/usr/bin$
> ./glpsol --cpxlp ~/value_15318949093.lp
> glp_read_lp: reading problem data from
> `/home/cullmann/value_15318949093.lp'...
> glp_read_lp: 1015 rows, 1577 columns, 3513 non-zeros
> glp_read_lp: 1577 integer columns, none of which are binary
> glp_read_lp: 2949 lines were read
> glp_simplex: original LP has 1015 rows, 1577 columns, 3513 non-zeros
> glp_simplex: presolved LP has 712 rows, 874 columns, 1942 non-zeros
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  6.000e+00  ratio =  6.000e+00
> Problem data seem to be well scaled
> Crashing...
> Size of triangular part = 666
>       0: obj =   1.877000000e+03  infeas =  2.400e+01 (46)
> *     3: obj =   1.877000000e+03  infeas =  0.000e+00 (46)
> *   200: obj =   1.383603996e+10  infeas =  0.000e+00 (0)
> *   400: obj =   1.495135855e+10  infeas =  0.000e+00 (0)
> *   558: obj =   1.531894909e+10  infeas =  0.000e+00 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> +   558: mip =     not found yet <=              +inf        (1; 0)
> +   558: mip =     not found yet <=     tree is empty        (0; 1)
> PROBLEM HAS NO INTEGER FEASIBLE SOLUTION

> While on 64bit, the same problem yields a solution:

> address@hidden:/local/cullmann/build/glpsolve.default/usr/bin$
> ./glpsol --cpxlp ~/value_15318949093.lp
> glp_read_lp: reading problem data from
> `/home/cullmann/value_15318949093.lp'...
> glp_read_lp: 1015 rows, 1577 columns, 3513 non-zeros
> glp_read_lp: 1577 integer columns, none of which are binary
> glp_read_lp: 2949 lines were read
> glp_simplex: original LP has 1015 rows, 1577 columns, 3513 non-zeros
> glp_simplex: presolved LP has 712 rows, 874 columns, 1942 non-zeros
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  6.000e+00  ratio =  6.000e+00
> Problem data seem to be well scaled
> Crashing...
> Size of triangular part = 666
>       0: obj =   1.877000000e+03  infeas =  2.400e+01 (46)
> *     3: obj =   1.877000000e+03  infeas =  0.000e+00 (46)
> *   200: obj =   1.383603996e+10  infeas =  0.000e+00 (0)
> *   400: obj =   1.495135855e+10  infeas =  0.000e+00 (0)
> *   559: obj =   1.531894909e+10  infeas =  0.000e+00 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> +   559: mip =     not found yet <=              +inf        (1; 0)
> +   559: >>>>>   1.531894909e+10 <=   1.531894909e+10   0.0% (1; 0)
> +   559: mip =   1.531894909e+10 <=     tree is empty   0.0% (0; 1)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used:   0.1 secs
> Memory used: 1.3 Mb (1400268 bytes)

> I have verified the 64bit solution using CPLEX, which yields the same
> value.

> Any ideas, what this might cause?
> Interesting sidenote: the debian shipped glpsol, version 4.16 works on
> both 32bit and 64bit linux systems with same sane result.

> The input LP is attached, CPLEX format. Any advice welcome :)

Thank you for your report.

The glpk mip solver indicates that the problem has no integer feasible
solution because lp relaxation of the root subproblem is almost primal
infeasible; more precisely, the dual simplex which is used to solve
lp relaxations cannot choose non-basic variable to keep the current
basis dual feasible within a tolerance, so it concludes that there
is no primal feasible solution to the lp relaxation. This, of course,
happens because the glpk dual simplex is still not as sufficiently
robust as the primal simplex.

On the other hand, I should say that your problem is badly formulated:
there are used unbounded integer variables, and most of them have large
values in the optimal solution to lp relaxation. When I introduced upper
bound 1e8 for all integer variables in your instance:

\ Lower Bounds
Bounds
xe49 <= 1e8
xf8e <= 1e8
x1d67 <= 1e8
x1be4 <= 1e8
x155b <= 1e8
. . .

I could solve it with 32-bit glpsol 4.31:

glp_read_lp: reading problem data from `value_15318949093.lp'...
glp_read_lp: 1015 rows, 1577 columns, 3513 non-zeros
glp_read_lp: 1577 integer columns, none of which are binary
glp_read_lp: 2949 lines were read
glp_simplex: original LP has 1015 rows, 1577 columns, 3513 non-zeros
glp_simplex: presolved LP has 942 rows, 1320 columns, 3072 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  6.000e+00  ratio =  6.000e+00
Problem data seem to be well scaled
Crashing...
Size of triangular part = 896
      0: obj =   1.877000000e+03  infeas =  2.400e+01 (46)
*     3: obj =   1.877000000e+03  infeas =  0.000e+00 (46)
*   200: obj =   1.399802172e+10  infeas =  0.000e+00 (0)
*   400: obj =   1.525441700e+10  infeas =  0.000e+00 (0)
*   478: obj =   1.531894909e+10  infeas =  1.552e-10 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   478: mip =     not found yet <=              +inf        (1; 0)
+   478: >>>>>   1.531894909e+10 <=   1.531894909e+10   0.0% (1; 0)
+   478: mip =   1.531894909e+10 <=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.7 secs
Memory used: 1.3 Mb (1357527 bytes)

As to 64-bit version and glpsol 4.16, it was just a happy chance due
to small differences caused by round-off errors, and insignificant
changes in the problem data mought cause the same error.


Andrew Makhorin