[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] Simplex termination 32 vs. 64 bit
From: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] Simplex termination 32 vs. 64 bit |
Date: |
Tue, 10 Apr 2012 01:25:13 +0400 |
> for the attached CPLEX-format ILP I'm observing a different termination
> behaviour on 32-Bit (doesn't terminate within the observed time frame of
> several hours) vs. 64-Bit (terminates after 0.4s) Linux. I'm running
> unpatched glpsol 4.47 (.tar.gz taken from gnu.org, built from sources)
> on Debian 6.0:
>
> Debian 6.0, 32-Bit:
> $ glpsol --lp input.cplex
> GLPSOL: GLPK LP/MIP Solver, v4.47
> Parameter(s) specified in the command line:
> --lp input.cplex
> Reading problem data from `input.cplex'...
> 332 rows, 2301 columns, 6903 non-zeros
> 2301 integer variables, all of which are binary
> 7228 lines were read
> GLPK Integer Optimizer, v4.47
> 332 rows, 2301 columns, 6903 non-zeros
> 2301 integer variables, all of which are binary
> Preprocessing...
> 314 rows, 2301 columns, 4602 non-zeros
> 2301 integer variables, all of which are binary
> Scaling...
> A: min|aij| = 1.000e+00 max|aij| = 3.000e+00 ratio = 3.000e+00
> Problem data seem to be well scaled
> Constructing initial basis...
> Size of triangular part = 314
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.47
> 314 rows, 2301 columns, 4602 non-zeros
> 0: obj = 3.372000000e+03 infeas = 2.430e+02 (0)
> * 315: obj = 3.153000000e+03 infeas = 0.000e+00 (0)
> * 500: obj = 1.321000000e+03 infeas = 1.092e-15 (0)
> * 851: obj = 5.020000000e+02 infeas = 7.401e-17 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> + 851: mip = not found yet >= -inf (1; 0)
> + 1437: >>>>> 5.040000000e+02 >= 5.020000000e+02 0.4% (50; 0)
> + 1631: >>>>> 5.030000000e+02 >= 5.020000000e+02 0.2% (65; 21)
> + 40041: mip = 5.030000000e+02 >= 5.020000000e+02 0.2% (51; 2232)
> + 76140: mip = 5.030000000e+02 >= 5.020000000e+02 0.2% (137; 4202)
> +116304: mip = 5.030000000e+02 >= 5.020000000e+02 0.2% (116; 6415)
> [... continues for hours without ever terminating ...]
>
> Debian 6.0, 64-Bit:
> $ glpsol --lp input.cplex
> GLPSOL: GLPK LP/MIP Solver, v4.47
> Parameter(s) specified in the command line:
> --lp input.cplex
> Reading problem data from `input.cplex'...
> 332 rows, 2301 columns, 6903 non-zeros
> 2301 integer variables, all of which are binary
> 7228 lines were read
> GLPK Integer Optimizer, v4.47
> 332 rows, 2301 columns, 6903 non-zeros
> 2301 integer variables, all of which are binary
> Preprocessing...
> 314 rows, 2301 columns, 4602 non-zeros
> 2301 integer variables, all of which are binary
> Scaling...
> A: min|aij| = 1.000e+00 max|aij| = 3.000e+00 ratio = 3.000e+00
> Problem data seem to be well scaled
> Constructing initial basis...
> Size of triangular part = 314
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.47
> 314 rows, 2301 columns, 4602 non-zeros
> 0: obj = 3.372000000e+03 infeas = 2.430e+02 (0)
> * 315: obj = 3.153000000e+03 infeas = 0.000e+00 (0)
> * 500: obj = 1.488000000e+03 infeas = 0.000e+00 (0)
> * 844: obj = 5.020000000e+02 infeas = 8.327e-17 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> + 844: mip = not found yet >= -inf (1; 0)
> + 2394: >>>>> 5.040000000e+02 >= 5.020000000e+02 0.4% (42; 0)
> + 3560: >>>>> 5.030000000e+02 >= 5.030000000e+02 0.0% (37; 88)
> + 3560: mip = 5.030000000e+02 >= tree is empty 0.0% (0; 171)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used: 0.4 secs
> Memory used: 2.1 Mb (2252288 bytes)
>
> The input data is attached to this email. Is it somewhat malformed, or
> did I indeed step on a GLPK bug?
No, this is not a bug.
The point is that glpk uses floating-point calculations that are
sensitive to many platform-dependent factors (compiler options, etc.).
That means that you may expect to obtain identical results only on
identical platforms. In particular, you may note that 32-bit version
performed 851 simplex iterations to solve the lp relaxation while 64-bit
one performed 844 iterations.
Your mip instance is generally hard for the branch-and-bound solver
(used by default), and it was solved quickly with the 64-bit version for
a happy chance. However, I think that the branch-and-cut solver with the
mir cuts enabled (--mir) is able to solve your mip for a short time
independently on the platform used:
GLPSOL: GLPK LP/MIP Solver, v4.48
Parameter(s) specified in the command line:
--lp input.cplex --mir --log log1.txt
Reading problem data from `input.cplex'...
332 rows, 2301 columns, 6903 non-zeros
2301 integer variables, all of which are binary
7228 lines were read
GLPK Integer Optimizer, v4.48
332 rows, 2301 columns, 6903 non-zeros
2301 integer variables, all of which are binary
Preprocessing...
314 rows, 2301 columns, 4602 non-zeros
2301 integer variables, all of which are binary
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 3.000e+00 ratio = 3.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 314
Solving LP relaxation...
GLPK Simplex Optimizer, v4.48
314 rows, 2301 columns, 4602 non-zeros
0: obj = 3.372000000e+03 infeas = 2.430e+02 (0)
* 315: obj = 3.153000000e+03 infeas = 5.551e-17 (0)
* 500: obj = 1.381000000e+03 infeas = 2.220e-16 (0)
* 821: obj = 5.020000000e+02 infeas = 2.683e-15 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
MIR cuts enabled
+ 821: mip = not found yet >= -inf (1; 0)
Cuts on level 0: mir = 7;
Cuts on level 37: mir = 7;
+ 3604: >>>>> 5.040000000e+02 >= 5.030000000e+02 0.2% (38; 0)
Cuts on level 14: mir = 9;
+ 3627: >>>>> 5.030000000e+02 >= 5.030000000e+02 < 0.1% (18; 38)
+ 3627: mip = 5.030000000e+02 >= tree is empty 0.0% (0; 75)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 2.5 secs
Memory used: 2.7 Mb (2812909 bytes)
The Gomory cuts (--gomory) also seem to be efficient:
GLPSOL: GLPK LP/MIP Solver, v4.48
Parameter(s) specified in the command line:
--lp input.cplex --gomory --log log2.txt
Reading problem data from `input.cplex'...
332 rows, 2301 columns, 6903 non-zeros
2301 integer variables, all of which are binary
7228 lines were read
GLPK Integer Optimizer, v4.48
332 rows, 2301 columns, 6903 non-zeros
2301 integer variables, all of which are binary
Preprocessing...
314 rows, 2301 columns, 4602 non-zeros
2301 integer variables, all of which are binary
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 3.000e+00 ratio = 3.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 314
Solving LP relaxation...
GLPK Simplex Optimizer, v4.48
314 rows, 2301 columns, 4602 non-zeros
0: obj = 3.372000000e+03 infeas = 2.430e+02 (0)
* 315: obj = 3.153000000e+03 infeas = 5.551e-17 (0)
* 500: obj = 1.381000000e+03 infeas = 2.220e-16 (0)
* 821: obj = 5.020000000e+02 infeas = 2.683e-15 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
Gomory's cuts enabled
+ 821: mip = not found yet >= -inf (1; 0)
Cuts on level 0: gmi = 3;
Cuts on level 31: gmi = 3;
+ 2839: >>>>> 5.030000000e+02 >= 5.030000000e+02 0.0% (32; 0)
+ 2839: mip = 5.030000000e+02 >= tree is empty 0.0% (0; 63)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 1.8 secs
Memory used: 4.1 Mb (4340753 bytes)
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Re: [Bug-glpk] Simplex termination 32 vs. 64 bit,
Andrew Makhorin <=