bug-glpk
[Top][All Lists]
Advanced

[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.


Attachment: test_glpk.LP
Description: Text document

Attachment: sol_simplex.txt
Description: Text document

Attachment: sol_interieur.txt
Description: Text document


reply via email to

[Prev in Thread] Current Thread [Next in Thread]