Hello,
on the following problem :
Minimize
func: - x1 - x2
Subject To
cst1: 0.9510565162951536 x1 + 6.909830056250525e-01 x2 <=
2.5930960382153598
cst2: -0.3632712640026803 x1 + 1.118033988749895e+00 x2 <=
1.7058192410423680
cst3: -1.1755705045849463 x1 + 2.220446049250313e-16 x2 <=
-0.2245139882897925
cst4: -0.3632712640026806 x1 - 1.118033988749895e+00 x2 <=
-0.5302487364574219
cst5: 0.9510565162951534 x1 - 6.909830056250528e-01 x2 <=
1.2111300269652543
End
the simplex and interior methods give 2 very different solutions.
glpsol --lp test_glpk.LP --interior -o sol_interieur.txt
glpsol --lp test_glpk.LP --simplex -o sol_simplex.txt
I have tested this with v4.47 and v4.44. The interior solution
is the good one, the simplex one doesn't verify constraints.
I use the v4.44 version provided by the rpm package of my
linux distribution (mageia 1) and I have compiled the v4.47
(so as to test with glpsol which is apparently not provided
with the v4.44 rpm mageia package). My machine is a dell
6420 laptop running the 64 bits linux (mageia 1).
hth
Bruno
===========================================
PS : I discover this problem in glpk
with a simple production problem : the
constraints define a polygon with vertices
regularly located on the circle of center
(1,1) and of radius 1. The cost function is
f(x1,x2) = -x1-x2 so the minimum is the
vertex nearest the point [1+sqrt(2)/2, 1+sqrt(2)/2].
The previus specific problem is got when the
polygon has 5 edges (the circle discretisation
beginning at theta = 0). With 8 edges the simplex
solution is good but is generally not the good one
for small discretisation. When the discretisation
is large enough the simplex solution seems
always good.
\ small test
Minimize
func: - x1 - x2
Subject To
cst1: 0.9510565162951536 x1 + 6.909830056250525e-01 x2 <= 2.5930960382153598
cst2: -0.3632712640026803 x1 + 1.118033988749895e+00 x2 <= 1.7058192410423680
cst3: -1.1755705045849463 x1 + 2.220446049250313e-16 x2 <= -0.2245139882897925
cst4: -0.3632712640026806 x1 - 1.118033988749895e+00 x2 <= -0.5302487364574219
cst5: 0.9510565162951534 x1 - 6.909830056250528e-01 x2 <= 1.2111300269652543
End
Problem:
Rows: 5
Columns: 2
Non-zeros: 10
Status: OPTIMAL
Objective: func = -3.680881291 (MINimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 cst1 NU 2.5931 2.5931 -1.44721
2 cst2 B 3.83245 1.70582
3 cst3 NU -0.224514 -0.224514 -0.32017
4 cst4 B -3.9712 -0.530249
5 cst5 B -2.22982 1.21113
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 x1 B 0.190983 0
2 x2 B 3.4899 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 = 2.13e+00 on row 2
max.rel.err = 7.86e-01 on row 2
PRIMAL SOLUTION IS INFEASIBLE
KKT.DE: max.abs.err = 2.22e-16 on column 1
max.rel.err = 5.92e-17 on column 1
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
Problem:
Rows: 5
Columns: 2
Non-zeros: 10
Status: OPTIMAL
Objective: func = -3.260073499 (MINimum)
No. Row name Activity Lower bound Upper bound Marginal
------ ------------ ------------- ------------- ------------- -------------
1 cst1 2.5931 2.5931 -1.12704
2 cst2 1.70582 1.70582 -0.197876
3 cst3 -1.53884 -0.224514 1.55136e-09
4 cst4 -2.65688 -0.530249 < eps
5 cst5 -0.103198 1.21113 < eps
No. Column name Activity Lower bound Upper bound Marginal
------ ------------ ------------- ------------- ------------- -------------
1 x1 1.30902 0 -6.09734e-09
2 x2 1.95106 0 < eps
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 = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
KKT.DE: max.abs.err = 0.00e+00 on column 0
max.rel.err = 0.00e+00 on column 0
High quality
KKT.DB: max.abs.err = 6.10e-09 on column 1
max.rel.err = 6.10e-09 on column 1
Medium quality
End of output
_______________________________________________
Bug-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/bug-glpk
