[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bug-glpk] Incorrect result from glpk-4.39
|
From: |
Arul kumar.M |
|
Subject: |
[Bug-glpk] Incorrect result from glpk-4.39 |
|
Date: |
Fri, 14 Aug 2009 12:08:59 +0400 |
I am writing to report what looks like a bug in glpk-4.39, that,
surprisingly, is not there in glpk-4.26.
Below, I first describe the problem, and its output when run with
glpk-4.39 on a pc running fedora-11. It is solved incorrectly by
glpk-4.39. Then, I will give the output of glpk-4.26, which solves it
correctly Would you please let me know if there is a bug, or if I am doing
something wrong. I do however know that I am doing the same thing in
invoking glpk-4.39 and glpk-4.26.
=============================================================
The CPLEX input file is as follows:
\* Problem: Unknown *\
Minimize
obj: + 0.25 x_1 + 0.25 x_2 + 0.25 x_3 + 0.25 x_4 + 0.25 x_5 + 0.25 x_6
+ 0.25 x_7 + 0.25 x_8 + 0.25 x_9 + 0.25 x_10 + 0.25 x_11 + 0.25 x_12
+ 0.25 x_13 + 0.25 x_14 + 0.25 x_15 + 0.25 x_16
Subject To
r_1: + 0.00246826328646297 x_8 - 0.00246826328646297 x_7
- 0.613602836556588 x_6 + 0.613602836556588 x_5
- 1.23259516440783e-32 x_4 + 1.23259516440783e-32 x_3
+ 0.612372435695794 x_2 - 0.612372435695794 x_1 = 0
r_2: + 1.23259516440783e-32 x_12 - 1.23259516440783e-32 x_11
- 0.612372435695794 x_10 + 0.612372435695794 x_9
- 0.00246826328646297 x_8 + 0.00246826328646297 x_7
+ 0.613602836556588 x_6 - 0.613602836556588 x_5 = 0
r_3: - 0.00246826328646297 x_16 + 0.00246826328646297 x_15
- 0.611134573270125 x_14 + 0.611134573270125 x_13
- 1.23259516440783e-32 x_12 + 1.23259516440783e-32 x_11
+ 0.612372435695794 x_10 - 0.612372435695794 x_9 = 0
r_4: + 0.00246826328646297 x_16 - 0.00246826328646297 x_15
+ 0.611134573270125 x_14 - 0.611134573270125 x_13
+ 1.23259516440783e-32 x_4 - 1.23259516440783e-32 x_3
- 0.612372435695794 x_2 + 0.612372435695794 x_1 = 0
r_5: + 0.000617065821615763 x_16 - 0.000617065821615763 x_15
+ 0.152783643317531 x_14 - 0.152783643317531 x_13
+ 2.16481864267984e-17 x_12 - 2.16481864267984e-17 x_11
+ 0.153093108923949 x_10 - 0.153093108923949 x_9
- 0.00061706582161572 x_8 + 0.00061706582161572 x_7
+ 0.153400709139147 x_6 - 0.153400709139147 x_5
+ 2.16481864267984e-17 x_4 - 2.16481864267984e-17 x_3
+ 0.153093108923949 x_2 - 0.153093108923949 x_1 = 0
r_6: + 0.176775618312514 x_16 - 0.176775618312514 x_15
- 0.0889222038335836 x_14 + 0.0889222038335836 x_13
+ 0.176776695296637 x_12 - 0.176776695296637 x_11
- 0.0883883476483185 x_10 + 0.0883883476483185 x_9
+ 0.176775618312514 x_8 - 0.176775618312514 x_7
- 0.0878534144789309 x_6 + 0.0878534144789309 x_5
+ 0.176776695296637 x_4 - 0.176776695296637 x_3
- 0.0883883476483185 x_2 + 0.0883883476483185 x_1 = 0.707106781186547
End
Upon calling glpk-4.39 as follows,
localhost:~> /usr/local/bin/glpsol --cpxlp outpb.lp -o foo39
GLPSOL: GLPK LP/MIP Solver 4.39
Reading problem data from `outpb.lp'...
6 rows, 16 columns, 64 non-zeros
42 lines were read
Original LP has 6 rows, 16 columns, 64 non-zeros
Presolved LP has 6 rows, 16 columns, 64 non-zeros
Scaling...
A: min|aij| = 1.233e-32 max|aij| = 6.136e-01 ratio = 4.978e+31
GM: min|aij| = 9.996e-09 max|aij| = 1.000e+08 ratio = 1.001e+16
EQ: min|aij| = 9.992e-17 max|aij| = 1.000e+00 ratio = 1.001e+16
Constructing initial basis...
Size of triangular part = 3
* 0: obj = 0.000000000e+00 infeas = 1.868e-08 (3)
* 1: obj = 0.000000000e+00 infeas = 1.868e-08 (3)
OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.0 Mb (44151 bytes)
Writing basic solution to `foo39'...
The file foo39 where output is directed is as follows:
localhost:~> cat foo39
Problem:
Rows: 6
Columns: 16
Non-zeros: 64
Status: OPTIMAL
Objective: obj = 0 (MINimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- -------------
-------------
1 r_1 NS 0 0 =
0.408248
2 r_2 NS 0 0 =
-100.878
3 r_3 NS 0 0 =
-101.286
4 r_4 B 0 0 =
5 r_5 B 0 0 =
6 r_6 B 0 0.707107 =
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- -------------
-------------
1 x_1 NL 0 0
0.5
2 x_2 B 0 0
3 x_3 NL 0 0
0.25
4 x_4 NL 0 0
0.25
5 x_5 NL 0 0
-61.8992
6 x_6 NL 0 0
62.3992
7 x_7 NL 0 0
0.5
8 x_8 B 0 0
9 x_9 NL 0 0 <
eps
10 x_10 NL 0 0
0.5
11 x_11 NL 0 0
0.25
12 x_12 NL 0 0
0.25
13 x_13 NL 0 0
62.1492
14 x_14 NL 0 0
-61.6492
15 x_15 NL 0 0
0.5
16 x_16 B 0 0
Karush-Kuhn-Tucker optimality 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 = 7.07e-01 on row 6
max.rel.err = 4.14e-01 on row 6
PRIMAL SOLUTION IS INFEASIBLE
KKT.DE: max.abs.err = 1.22e-14 on column 5
max.rel.err = 9.71e-17 on column 5
High quality
KKT.DB: max.abs.err = 6.19e+01 on column 5
max.rel.err = 6.19e+01 on column 5
DUAL SOLUTION IS INFEASIBLE
End of output
The min of the objective function is stated to be 0, while it should be 1.
The LP problem is also stated to be primal infeasible, incorrectly.
=========================================================================
I also ran this problem using glpk-4.26
localhost:~> /tmp/bin/glpsol --cpxlp outpb.lp -o foo26
lpx_read_cpxlp: reading problem data from `outpb.lp'...
lpx_read_cpxlp: 6 rows, 16 columns, 64 non-zeros
lpx_read_cpxlp: 42 lines were read
glp_simplex: original LP has 6 rows, 16 columns, 64 non-zeros
glp_simplex: presolved LP has 6 rows, 16 columns, 64 non-zeros
lpx_adv_basis: size of triangular part = 3
0: objval = 0.000000000e+00 infeas = 1.000000000e+00 (2)
2: objval = 1.002009236e+00 infeas = 7.462978535e-34 (1)
* 2: objval = 1.002009236e+00 infeas = 2.985191414e-33 (1)
* 4: objval = 1.000000000e+00 infeas = 1.415817825e-16 (1)
OPTIMAL SOLUTION FOUND
Time used: 1.0 secs
Memory used: 0.0 Mb (45916 bytes)
lpx_print_sol: writing LP problem solution to `foo26'...
The output file reads as
localhost:~> cat foo26
Problem:
Rows: 6
Columns: 16
Non-zeros: 64
Status: OPTIMAL
Objective: obj = 1 (MINimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- -------------
-------------
1 r_1 NS 0 0 =
-0.0510823
2 r_2 NS 0 0 =
0.101343
3 r_3 NS 0 0 =
0.0502603
4 r_4 B 0 0 =
5 r_5 NS 0 0 =
-0.612168
6 r_6 NS 0.707107 0.707107 =
1.41421
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- -------------
-------------
1 x_1 B 0 0
2 x_2 NL 0 0
0.5
3 x_3 NL 0 0
0.5
4 x_4 NL 0 0 <
eps
5 x_5 NL 0 0
0.125378
6 x_6 NL 0 0
0.374622
7 x_7 NL 0 0
0.5
8 x_8 B 0 0
9 x_9 B 0 0
10 x_10 NL 0 0
0.5
11 x_11 NL 0 0
0.5
12 x_12 B 4 0
13 x_13 B 0 0
14 x_14 NL 0 0
0.5
15 x_15 NL 0 0
0.499497
16 x_16 NL 0 0
0.000503326
Karush-Kuhn-Tucker optimality conditions:
KKT.PE: max.abs.err. = 8.67e-17 on row 2
max.rel.err. = 8.67e-17 on row 2
High quality
KKT.PB: max.abs.err. = 8.67e-17 on row 4
max.rel.err. = 8.67e-17 on row 4
High quality
KKT.DE: max.abs.err. = 1.14e-16 on column 13
max.rel.err. = 9.10e-17 on column 13
High quality
KKT.DB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
End of output
This is indeed the correct answer to the LP problem.
I'd appreciate any help resolving this bug.
Arul
Regards,
Arul Kumar.M
PhD scholar,Department of Mechanical Engineering,
Indian Institute of Technology, Kanpur,
Kanpur, Uttar Pradesh - 208016.
Mobil no.: 09956717722
- [Bug-glpk] Incorrect result from glpk-4.39,
Arul kumar.M <=