[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bug-glpk] bug in simplex for small dimensions ?
From: |
pincon |
Subject: |
[Bug-glpk] bug in simplex for small dimensions ? |
Date: |
Thu, 24 May 2012 14:35:29 +0200 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:10.0.4) Gecko/20120424 Thunderbird/10.0.4 |
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.
test_glpk.LP
Description: Text document
sol_simplex.txt
Description: Text document
sol_interieur.txt
Description: Text document
- [Bug-glpk] bug in simplex for small dimensions ?,
pincon <=