You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Alexey Slepov (JIRA)" <ji...@apache.org> on 2012/06/30 13:42:42 UTC
[jira] [Created] (MATH-808) SimplexSolver returns values out of
constraints bounds
Alexey Slepov created MATH-808:
----------------------------------
Summary: SimplexSolver returns values out of constraints bounds
Key: MATH-808
URL: https://issues.apache.org/jira/browse/MATH-808
Project: Commons Math
Issue Type: Bug
Affects Versions: 3.0
Environment: win7 64, eclipse 3.7, Apache Math 3.0
Reporter: Alexey Slepov
Priority: Blocker
Fix For: 3.0
Attachments: InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-808) SimplexSolver returns values out of
constraints bounds
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Gilles updated MATH-808:
------------------------
Priority: Major (was: Blocker)
Fix Version/s: (was: 3.0)
3.1
Assignee: Thomas Neidhart
Has this been confirmed to still occur with the development version?
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.1
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithmTest.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-808) SimplexSolver returns values out of
constraints bounds
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13404724#comment-13404724 ]
Thomas Neidhart commented on MATH-808:
--------------------------------------
Hi,
I could not run your test code as some classes are missing.
Maybe the described behavior is related to a precision flaw that has been fixed in MATH-781 (see https://issues.apache.org/jira/browse/MATH-781). Could you please check if the same problem occurs with the latest trunk.
For the test case that Gilles mentioned you could take a look at the attached ones from MATH-781.
Thanks,
Thomas
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.0
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithmTest.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Comment Edited] (MATH-808) SimplexSolver returns values out
of constraints bounds
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13404724#comment-13404724 ]
Thomas Neidhart edited comment on MATH-808 at 7/1/12 1:42 PM:
--------------------------------------------------------------
Hi,
I could not run your test code as some classes are missing.
Maybe the described behavior is related to an accuracy flaw that has been fixed in MATH-781 (see https://issues.apache.org/jira/browse/MATH-781). Could you please check if the same problem occurs with the latest trunk.
For the test case that Gilles mentioned you could take a look at the attached ones from MATH-781.
Thanks,
Thomas
was (Author: tn):
Hi,
I could not run your test code as some classes are missing.
Maybe the described behavior is related to a precision flaw that has been fixed in MATH-781 (see https://issues.apache.org/jira/browse/MATH-781). Could you please check if the same problem occurs with the latest trunk.
For the test case that Gilles mentioned you could take a look at the attached ones from MATH-781.
Thanks,
Thomas
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.0
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithmTest.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-808) SimplexSolver returns values out of
constraints bounds
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13404497#comment-13404497 ]
Gilles commented on MATH-808:
-----------------------------
Could you please simplify the test case? It should contain the bare minimum of code necessary to show the buggy behaviour. The unit test should also contain a method from the {{org.junit.Assert}} class in order to indicate which result is expected.
Thanks.
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.0
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithmTest.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-808) SimplexSolver returns values out of
constraints bounds
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13418362#comment-13418362 ]
Alexey Slepov commented on MATH-808:
------------------------------------
Thanks Thomas for you involvement in this particular case. Now I see that the problem was out of unproper using of Math3. But! Always there is but :) the problem with this LP problem moved to MATH-828 issue. I'll be appreciated to you if you look in there again (now the code is all-sufficient and easier to read)
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.1
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithmTest.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Comment Edited] (MATH-808) SimplexSolver returns values out
of constraints bounds
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13416436#comment-13416436 ]
Thomas Neidhart edited comment on MATH-808 at 7/17/12 6:42 PM:
---------------------------------------------------------------
I further looked into the test case and finally was able to run it (create Algorithm interface myself and use MathArrays.distance to compute the euclidean distance).
Imho, the bug report is wrong, as the failing tests are due to an invalid result validation:
{noformat}
1. First equation set -q(r) + QL >= 0 <---> QL >= q(r) verifications:
1: 0.0000*t + 1.0940*0.0592 + 1.8101*0.0000 + 2.7621*0.0000 + 2.1166*0.0674 + 3.5084*0.3067 + 2.1122*0.0919 + 1.2818*0.2595 >= 1.8101 <--------> 1.81011188 >= 1.81011200
EXCEPTION: Wrong equation
java.lang.Exception: Wrong equation
at ru.hse.cst.algorithm.InputOrientedDEAAlgorithm.findEntityOptimum(InputOrientedDEAAlgorithm.java:378)
{noformat}
Actually this is based on the following check:
{noformat}
if(sum < 0) {
throw new Exception("Wrong equation");
}
{noformat}
Now, the SimplexSolver is not a perfect algorithm and has to cope with the usual limitations of floating-point arithmetic. So the solution will only be accurate within a given epsilon. The default one is 1e-6, so the result has to be evaluated taking this epsilon into account:
{noformat}
if(Precision.compareTo(sum, 0, 1e-6) < 0){
throw new Exception("Wrong equation");
}
{noformat}
With such a check the test cases run through successfully. I still encountered some "No feasible solution found" and "Max count exceeded" situations, which I have not further debugged and are most likely happening because of test setup (the coefficients are created randomly).
was (Author: tn):
I further looked into the test case and finally was able to run it (create Algorithm interface myself and use MathArrays.distance to compute the euclidean distance).
Imho, the bug report is wrong, as the failing tests are due to an invalid result validation:
{noformat}
1. First equation set -q(r) + QL >= 0 <---> QL >= q(r) verifications:
1: 0.0000*t + 1.0940*0.0592 + 1.8101*0.0000 + 2.7621*0.0000 + 2.1166*0.0674 + 3.5084*0.3067 + 2.1122*0.0919 + 1.2818*0.2595 >= 1.8101 <--------> 1.81011188 >= 1.81011200
EXCEPTION: Wrong equation
java.lang.Exception: Wrong equation
at ru.hse.cst.algorithm.InputOrientedDEAAlgorithm.findEntityOptimum(InputOrientedDEAAlgorithm.java:378)
{noformat}
Actually this is based on the following check:
{noformat}
if(sum < 0) {
throw new Exception("Wrong equation");
}
{noformat}
No, the SimplexSolver is not a perfect algorithm and has to cope with the usual limitations of floating-point arithmetic. So the solution will only be accurate within a given epsilon. The default one is 1e-6, so the result has to be evaluated taking this epsilon into account:
{noformat}
if(Precision.compareTo(sum, 0, 1e-6) < 0){
throw new Exception("Wrong equation");
}
{noformat}
With such a check the test cases run through successfully. I still encountered some "No feasible solution found" and "Max count exceeded" situations, which I have not further debugged and are most likely happening because of test setup (the coefficients are created randomly).
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.1
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithmTest.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (MATH-808) SimplexSolver returns values out of
constraints bounds
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart resolved MATH-808.
----------------------------------
Resolution: Invalid
Following my observations, I close this issue as invalid. If you encounter other problems with the simplex solver, feel free to create a new issue with test cases attached.
Thanks, Thomas
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.1
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithmTest.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-808) SimplexSolver returns values out of
constraints bounds
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13416436#comment-13416436 ]
Thomas Neidhart commented on MATH-808:
--------------------------------------
I further looked into the test case and finally was able to run it (create Algorithm interface myself and use MathArrays.distance to compute the euclidean distance).
Imho, the bug report is wrong, as the failing tests are due to an invalid result validation:
{noformat}
1. First equation set -q(r) + QL >= 0 <---> QL >= q(r) verifications:
1: 0.0000*t + 1.0940*0.0592 + 1.8101*0.0000 + 2.7621*0.0000 + 2.1166*0.0674 + 3.5084*0.3067 + 2.1122*0.0919 + 1.2818*0.2595 >= 1.8101 <--------> 1.81011188 >= 1.81011200
EXCEPTION: Wrong equation
java.lang.Exception: Wrong equation
at ru.hse.cst.algorithm.InputOrientedDEAAlgorithm.findEntityOptimum(InputOrientedDEAAlgorithm.java:378)
{noformat}
Actually this is based on the following check:
{noformat}
if(sum < 0) {
throw new Exception("Wrong equation");
}
{noformat}
No, the SimplexSolver is not a perfect algorithm and has to cope with the usual limitations of floating-point arithmetic. So the solution will only be accurate within a given epsilon. The default one is 1e-6, so the result has to be evaluated taking this epsilon into account:
{noformat}
if(Precision.compareTo(sum, 0, 1e-6) < 0){
throw new Exception("Wrong equation");
}
{noformat}
With such a check the test cases run through successfully. I still encountered some "No feasible solution found" and "Max count exceeded" situations, which I have not further debugged and are most likely happening because of test setup (the coefficients are created randomly).
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.1
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithmTest.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-808) SimplexSolver returns values out of
constraints bounds
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13416002#comment-13416002 ]
Thomas Neidhart commented on MATH-808:
--------------------------------------
No, it has not been confirmed, but I will try to extract relevant information from the attached test case and run it on trunk.
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.1
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithmTest.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-808) SimplexSolver returns values out of
constraints bounds
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Alexey Slepov updated MATH-808:
-------------------------------
Attachment: InputOrientedDEAAlgorithm.java
Source code file. Take a look into
public PointValuePair findEntityOptimum(EntityArgument entity, GoalType goalType) throws Exception
method
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.0
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-808) SimplexSolver returns values out of
constraints bounds
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Alexey Slepov updated MATH-808:
-------------------------------
Attachment: InputOrientedDEAAlgorithmTest.java
Unit test to run to repeat the unexpected SimplexSolver behavior
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.0
>
> Attachments: InputOrientedDEAAlgorithm.java, InputOrientedDEAAlgorithmTest.java, InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-808) SimplexSolver returns values out of
constraints bounds
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-808?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Alexey Slepov updated MATH-808:
-------------------------------
Attachment: InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
Test report file. Keep attention to 'EXCEPTION: Wrong equation' lines
> SimplexSolver returns values out of constraints bounds
> ------------------------------------------------------
>
> Key: MATH-808
> URL: https://issues.apache.org/jira/browse/MATH-808
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: win7 64, eclipse 3.7, Apache Math 3.0
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: SimplexSolver, constraints, math, unexpected
> Fix For: 3.0
>
> Attachments: InputOrientedDEAAlgorithm_12-6-30_15-32-52.test.txt
>
>
> SimplexSolver gives back result that doesn't match constraints
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira