[jira] Updated: (MATH-351) SimplexSolver fails to solve feasible problem instance

["Jurgen Tas (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Jurgen Tas updated MATH-351:
----------------------------

    Attachment: oledata.mso
                image031.gif
                image030.wmz
                image029.gif
                image028.wmz
                image027.gif
                image026.wmz
                image025.gif
                image024.wmz
                image023.gif
                image022.wmz
                image021.gif
                image020.wmz
                image019.gif
                image018.wmz
                image017.gif
                image001.wmz

You are welcome!

 

I am using the trunk version of the code. I also found that 2.0 contained some errors. In the new versions I have not found anything strange. 

 

Interesting to me is the use of epsilon. I have found that the default value of 1e-6 works fine for most problems. However, consider the following problem:

 

 

 

The answer to this problem is trivial to find; i.e.  and .  However, for the case when we get a wrong answer; i.e. for   we find that and  (the second constraint is not satisfied), and even for  no feasible solution could be found. 

 

Too me the results of this very simple problem are obvious. But how do you determine the threshold for epsilon for general problems? Do you analyze the condition number of the constraints matrix?

 

Jurgen



> SimplexSolver fails to solve feasible problem instance 
> -------------------------------------------------------
>
>                 Key: MATH-351
>                 URL: https://issues.apache.org/jira/browse/MATH-351
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.0
>         Environment: Windows Vista Home Premium Version 6.0 Service Pack 1, Build 6001
>            Reporter: Mark Thomas
>             Fix For: 2.1
>
>         Attachments: image001.wmz, image017.gif, image018.wmz, image019.gif, image020.wmz, image021.gif, image022.wmz, image023.gif, image024.wmz, image025.gif, image026.wmz, image027.gif, image028.wmz, image029.gif, image030.wmz, image031.gif, oledata.mso, SimplexFail.xlsx, TestSimplexFail.java
>
>
> SimplexSolver throws an UnboundedSolutionException on a problem instance I can optimally solve with Excel's Solver. I've kept the parameters between the two programs the same as far as I can tell  (i.e. both have a precision/epsilon value of 1e-6 and a maxIterations value of 1000). I will attach a JUnit test  with an example problem on which SimplexSolver fails. I will also attach an Excel spreadsheet wtih the same data and successful Solver setup in place.
> I don't know a whole lot about linear programming or Simplex, but the problem I'm attempting to solve does appear to have a fairly sparse coefficient matrix, which may be part of the problem.
> It's surprisingly difficult to find a Java-based linear programming library, so I was ecstatic when I found this. Let me know how I can help!
> Thanks!

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.