You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Mark Thomas (JIRA)" <ji...@apache.org> on 2010/03/10 03:48:27 UTC
[jira] Created: (MATH-351) SimplexSolver fails to solve feasible
problem instance
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
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.
[jira] Updated: (MATH-351) SimplexSolver fails to solve feasible
problem instance
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phil Steitz updated MATH-351:
-----------------------------
Fix Version/s: (was: 2.1)
2.2
> 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.2
>
> 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.
[jira] Resolved: (MATH-351) SimplexSolver fails to solve feasible
problem instance
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Luc Maisonobe resolved MATH-351.
--------------------------------
Resolution: Invalid
solving as invalid as per last comments
> 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.2
>
> 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.
[jira] Updated: (MATH-351) SimplexSolver fails to solve feasible
problem instance
Posted by "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.
[jira] Issue Comment Edited: (MATH-351) SimplexSolver fails to
solve feasible problem instance
Posted by "Mark Thomas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12851930#action_12851930 ]
Mark Thomas edited comment on MATH-351 at 3/31/10 6:44 PM:
-----------------------------------------------------------
Good catch. Not sure how I missed this. I'm still getting an UnboundedSolutionException, even after I set the coefficients all to 1, however. Note that I'm still using the 2.0 code which was noted above to have a bug in it. Are you using 2.1?
Thanks Jurgen!
--Mark
was (Author: thomamark):
Good catch--not sure how I missed this. I'm still getting an UnboundedSolutionException, even after I set the coefficients all to 1, however. Note that I'm still using the 2.0 code which was noted above to have a bug in it--are you using 2.1?
Thanks Jurgen!
--Mark
> 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: 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.
[jira] Commented: (MATH-351) SimplexSolver fails to solve feasible
problem instance
Posted by "Jurgen Tas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12851777#action_12851777 ]
Jurgen Tas commented on MATH-351:
---------------------------------
To put it simply, you have defined a problem of the following form:
max (0*x1 + 0*x2 + 0*x3 +...) subject to the following constraints:
x1 + x2 + ... >= some number
x2 + x3 + ... >= some number
etc...(you have defined inequalities of a similar form)
x1>=0, x2>=0,....
Ofcourse such a problem is unbounded; i.e. the solution is x1 = infinitiy, x2 = infinity,.... etc..
Maybe I don't understand the problem well, but to me it seems that the Excel program gives a wrong answer.
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: 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.
[jira] Commented: (MATH-351) SimplexSolver fails to solve feasible
problem instance
Posted by "Jurgen Tas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12851779#action_12851779 ]
Jurgen Tas commented on MATH-351:
---------------------------------
I see what you have done wrong in your Java code. The coefficients in your objective function are all zero, while they need to be all one. If you change this, you get the same answer as Excel.
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: 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.
[jira] Updated: (MATH-351) SimplexSolver fails to solve feasible
problem instance
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phil Steitz updated MATH-351:
-----------------------------
Fix Version/s: 2.1
> 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: 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.
[jira] Updated: (MATH-351) SimplexSolver fails to solve feasible
problem instance
Posted by "Mark Thomas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Mark Thomas updated MATH-351:
-----------------------------
Attachment: SimplexFail.xlsx
TestSimplexFail.java
The JUnit test showing an example of a problem which fails with an UnboundedSolutionException when using SimplexSolver and the Excel spreadsheet containing the optimal solution. The two together prove (I believe) that there is something wrong with SimplexSolver.
> 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
> Attachments: 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.
[jira] Commented: (MATH-351) SimplexSolver fails to solve feasible
problem instance
Posted by "Mark Thomas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12851930#action_12851930 ]
Mark Thomas commented on MATH-351:
----------------------------------
Good catch--not sure how I missed this. I'm still getting an UnboundedSolutionException, even after I set the coefficients all to 1, however. Note that I'm still using the 2.0 code which was noted above to have a bug in it--are you using 2.1?
Thanks Jurgen!
--Mark
> 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: 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.
[jira] Commented: (MATH-351) SimplexSolver fails to solve feasible
problem instance
Posted by "Mark Thomas (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12852538#action_12852538 ]
Mark Thomas commented on MATH-351:
----------------------------------
I haven't had a chance yet to verify for myself that this works on 2.1, but if it works for you, Luc and you consider the epsilon discussion a separate issue, I'm happy with closing this as invalid (especially if it will lead to an earlier release of 2.1 =).
For other readers, it appears that there were bug fixes for Simplex which weren't in 2.0, but have been incorporated into the trunk (see: http://issues.apache.org/jira/browse/MATH-302). If this is so, we'll want to leave this link in.
Thanks guys and sorry for the mix up.
Mark
> 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.
[jira] Commented: (MATH-351) SimplexSolver fails to solve feasible
problem instance
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-351?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12852489#action_12852489 ]
Luc Maisonobe commented on MATH-351:
------------------------------------
Jurgen, your last comment on this issue is impossible to read, the images containing the equations are not inlined in the text (at least not with firefox on Linux). Could you rewrite it in simple raw text ?
Mark, do you agree to close the issue as invalid ?
> 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.