[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Wrong optimal solution with Glpk-4.34
|
From: |
ULDRY Marc |
|
Subject: |
Re: [Help-glpk] Wrong optimal solution with Glpk-4.34 |
|
Date: |
Mon, 6 Sep 2010 22:10:22 +0400 |
Re: [Help-glpk] Wrong optimal solution with Glpk-4.34Hello Xypron,
I have seen that you use GLPK v4.44. So I have downloaded the sources of GLPK
v4.44 and I have then compiled them with Visual Studio 2008.
The value of the optimal solution given by GLPK v4.44 for the problem is now
the same as the value given by CPLEX and Gurobi.
I have tested 30 instances where the optimal solution was wrong before using
GLPK v4.44 and for each instance, the value of the optimal solution is now the
same as the value given by CPLEX and Gurobi.
I used before the version 4.34 of Glpk that we can download with the windows
installer on the website : http://gnuwin32.sourceforge.net/packages/glpk.htm
(Complete package, except sources of the 4 December 2008). So the #8216;wrong
optimal solutions #8217; seems to come when using this #8216;old #8217;
version.
I will use the version 4.44 now.
Thank you for your help.
Best regards.
Marc Uldry
On 06.09.10 15:59, "Uldry Marc" <address@hidden> wrote:
Dear Xypron,
Thank you for your answer.
Here are some details :
The value given by Glpk-4.34 on Windows 7 is 1780 :
>glpsol -m problem.mod -d problem.dat
Reading model section from problem.mod...
37 lines were read
Reading data section from problem.dat...
20 lines were read
Generating c1...
Generating c2...
Generating obj...
Model has been successfully generated
ipp_basic_tech: 106 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 16 rows, 240 columns, 240 non-zeros
glp_intopt: 240 integer columns, all of which are binary
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Crashing...
Size of triangular part = 16
Solving LP relaxation...
* 0: obj = 2.525000000e+003 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 0: mip = not found yet >= -inf (1; 0)
+ 9: >>>>> 1.780000000e+003 >= 1.780000000e+003 0.0% (1; 0)
+ 9: mip = 1.780000000e+003 >= tree is empty 0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.4 Mb (425619 bytes)
The value given by CPLEX 12.2.0.0 on Windows 7 is 1720 :
Log started (V12.2.0.0) Mon Sep 06 15:33:46 2010
Problem 'problem.lp' read.
Read time = 0.09 sec.
Tried aggregator 1 time.
MIP Presolve eliminated 121 rows and 240 columns.
All rows and columns eliminated.
Presolve time = 0.03 sec.
Solution pool: 1 solution saved.
MIP - Integer optimal solution: Objective = 1.7200000000e+003
Solution time = 0.11 sec. Iterations = 0 Nodes = 0
The value given by Gurobi 3.0.1 on Windows 7 is 1720 :
Gurobi 3.0.1 (win32) logging started 09/06/10 15:36:59
Read LP format model from file problem.lp
Reading time = 0.00 seconds
(null): 121 Rows, 240 Columns, 480 NonZeros
Optimize a model with 121 Rows, 240 Columns and 480 NonZeros
Presolve removed 121 rows and 240 columns
Presolve time: 0.00s
Explored 0 nodes (0 simplex iterations) in 0.00 seconds
Thread count was 1 (of 1 available processors)
Optimal solution found (tolerance 1.00e-04)
Best objective 1.7200000000e+03, best bound 1.7200000000e+03, gap 0.0%
If I use Glpk-4.34 with options #8212;nomip and #8212;exact, I get the value
1720 :
>glpsol --nomip --exact -m problem.mod -d problem.dat
Reading model section from problem.mod...
37 lines were read
Reading data section from problem.dat...
20 lines were read
Generating c1...
Generating c2...
Generating obj...
Model has been successfully generated
glp_exact: 122 rows, 240 columns, 720 non-zeros
GLPK bignum module is being used
(Consider installing GNU MP to attain a much better performance.)
0: infsum = 16 (0)
16: infsum = 0 (0)
* 16: objval = 2525 (0)
* 25: objval = 1720 (0)
OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.4 Mb (384904 bytes)
Best regards.
Marc
On 03.09.10 18:43, "Xypron" <address@hidden> wrote:
Hello Marc,
please, specify which values you got in all three solvers.
My impression is that the problem is not well scaled. The coefficients in the
objective function differ by a factor of 10^16. This leads to big rounding
errors.
Do you expect the corresponding variables ever to be nonzero?
Could you use smaller penalty costs on these variables?
The effect of bad scaling can be seen when comparing the normal precision LP
solution to the exact LP solution:
glpsol --nomip -m problem.mod -d problem.dat
gives a solution of the LP relaxation of 1865 with glpk-4.44 on 32bit Linux.
glpsol --nomip --exact -m problem.mod -d problem.dat
gives a solution of the LP relaxation of 1720.
When I solve the MIP I get the following output:
$ glpsol -m problem.mod -d problem.dat
...
GLPK Simplex Optimizer, v4.44
16 rows, 240 columns, 240 non-zeros
* 0: obj = 1.600000000e+19 infeas = 0.000e+00 (0)
* 25: obj = 1.925000000e+03 infeas = 0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 25: mip = not found yet >= -inf (1; 0)
+ 25: >>>>> 1.720000000e+03 >= 1.720000000e+03 0.0% (1; 0)
+ 25: mip = 1.720000000e+03 >= tree is empty 0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
This output looks strange because for a minimization problem the MIP solution
should always be greater of equal to the LP solution.
@Andrew: Could you, please, explain why this occurs?
Best regards
Xypron
ULDRY Marc wrote:
Wrong optimal solution with Glpk-4.34Hello,
I have solved a MIP with 3 different solvers. Each solver gives an optimal
solution after a few seconds.
I want to minimize the objective function value.
The optimal solution (objective function value) given by Glpk is greater than
the optimal solution (objective function value) of the 2 other solvers (cplex
12.2 and Gurobi 3.0.1) which have both the same objective function value.
Does anybody know the reason of this difference ?
You will find in attachment the model (problem.mod) and the data (problem.dat)
of the problem and the LP file generated by Glpk from the *.mod and *.dat files
(problem.lp) which has been solved by the 3 different solvers.
Thank you for your help.
Best regards.
Marc Uldry
_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk
Hello Xypron,
I have seen that you use GLPK v4.44. So I have downloaded the sources of GLPK v4.44 and I have then compiled them with Visual Studio 2008.
The value of the optimal solution given by GLPK v4.44 for the problem is now the same as the value given by CPLEX and Gurobi.
I have tested 30 instances where the optimal solution was wrong before using GLPK v4.44 and for each instance, the value of the optimal solution is now the same as the value given by CPLEX and Gurobi.
I used before the version 4.34 of Glpk that we can download with the windows installer on the website : http://gnuwin32.sourceforge.net/packages/glpk.htm (Complete package, except sources of the 4 December 2008). So the ‘wrong optimal solutions’ seems to come when using this ‘old’ version.
I will use the version 4.44 now.
Thank you for your help.
Best regards.
Marc Uldry
On 06.09.10 15:59, "Uldry Marc" <address@hidden> wrote:
Dear Xypron,
Thank you for your answer.
Here are some details :
The value given by Glpk-4.34 on Windows 7 is 1780 :
>glpsol -m problem.mod -d problem.dat
Reading model section from problem.mod...
37 lines were read
Reading data section from problem.dat...
20 lines were read
Generating c1...
Generating c2...
Generating obj...
Model has been successfully generated
ipp_basic_tech: 106 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 16 rows, 240 columns, 240 non-zeros
glp_intopt: 240 integer columns, all of which are binary
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Crashing...
Size of triangular part = 16
Solving LP relaxation...
* 0: obj = 2.525000000e+003 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 0: mip = not found yet >= -inf (1; 0)
+ 9: >>>>> 1.780000000e+003 >= 1.780000000e+003 0.0% (1; 0)
+ 9: mip = 1.780000000e+003 >= tree is empty 0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.4 Mb (425619 bytes)
The value given by CPLEX 12.2.0.0 on Windows 7 is 1720 :
Log started (V12.2.0.0) Mon Sep 06 15:33:46 2010
Problem 'problem.lp' read.
Read time = 0.09 sec.
Tried aggregator 1 time.
MIP Presolve eliminated 121 rows and 240 columns.
All rows and columns eliminated.
Presolve time = 0.03 sec.
Solution pool: 1 solution saved.
MIP - Integer optimal solution: Objective = 1.7200000000e+003
Solution time = 0.11 sec. Iterations = 0 Nodes = 0
The value given by Gurobi 3.0.1 on Windows 7 is 1720 :
Gurobi 3.0.1 (win32) logging started 09/06/10 15:36:59
Read LP format model from file problem.lp
Reading time = 0.00 seconds
(null): 121 Rows, 240 Columns, 480 NonZeros
Optimize a model with 121 Rows, 240 Columns and 480 NonZeros
Presolve removed 121 rows and 240 columns
Presolve time: 0.00s
Explored 0 nodes (0 simplex iterations) in 0.00 seconds
Thread count was 1 (of 1 available processors)
Optimal solution found (tolerance 1.00e-04)
Best objective 1.7200000000e+03, best bound 1.7200000000e+03, gap 0.0%
If I use Glpk-4.34 with options —nomip and —exact, I get the value 1720 :
>glpsol --nomip --exact -m problem.mod -d problem.dat
Reading model section from problem.mod...
37 lines were read
Reading data section from problem.dat...
20 lines were read
Generating c1...
Generating c2...
Generating obj...
Model has been successfully generated
glp_exact: 122 rows, 240 columns, 720 non-zeros
GLPK bignum module is being used
(Consider installing GNU MP to attain a much better performance.)
0: infsum = 16 (0)
16: infsum = 0 (0)
* 16: objval = 2525 (0)
* 25: objval = 1720 (0)
OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.4 Mb (384904 bytes)
Best regards.
Marc
On 03.09.10 18:43, "Xypron" <address@hidden> wrote:
Hello Marc,
please, specify which values you got in all three solvers.
My impression is that the problem is not well scaled. The coefficients in the objective function differ by a factor of 10^16. This leads to big rounding errors.
Do you expect the corresponding variables ever to be nonzero?
Could you use smaller penalty costs on these variables?
The effect of bad scaling can be seen when comparing the normal precision LP solution to the exact LP solution:
glpsol --nomip -m problem.mod -d problem.dat
gives a solution of the LP relaxation of 1865 with glpk-4.44 on 32bit Linux.
glpsol --nomip --exact -m problem.mod -d problem.dat
gives a solution of the LP relaxation of 1720.
When I solve the MIP I get the following output:
$ glpsol -m problem.mod -d problem.dat
...
GLPK Simplex Optimizer, v4.44
16 rows, 240 columns, 240 non-zeros
* 0: obj = 1.600000000e+19 infeas = 0.000e+00 (0)
* 25: obj = 1.925000000e+03 infeas = 0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 25: mip = not found yet >= -inf (1; 0)
+ 25: >>>>> 1.720000000e+03 >= 1.720000000e+03 0.0% (1; 0)
+ 25: mip = 1.720000000e+03 >= tree is empty 0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
This output looks strange because for a minimization problem the MIP solution should always be greater of equal to the LP solution.
@Andrew: Could you, please, explain why this occurs?
Best regards
Xypron
ULDRY Marc wrote:
Wrong optimal solution with Glpk-4.34Hello,
I have solved a MIP with 3 different solvers. Each solver gives an optimal solution after a few seconds.
I want to minimize the objective function value.
The optimal solution (objective function value) given by Glpk is greater than the optimal solution (objective function value) of the 2 other solvers (cplex 12.2 and Gurobi 3.0.1) which have both the same objective function value.
Does anybody know the reason of this difference ?
You will find in attachment the model (problem.mod) and the data (problem.dat) of the problem and the LP file generated by Glpk from the *.mod and *.dat files (problem.lp) which has been solved by the 3 different solvers.
Thank you for your help.
Best regards.
Marc Uldry
_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk