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/07/19 17:07:35 UTC
[jira] [Created] (MATH-828) Not expected UnboundedSolutionException
Alexey Slepov created MATH-828:
----------------------------------
Summary: Not expected UnboundedSolutionException
Key: MATH-828
URL: https://issues.apache.org/jira/browse/MATH-828
Project: Commons Math
Issue Type: Bug
Affects Versions: 3.0
Environment: Intel Core i5-2300 Windows XP SP3
Reporter: Alexey Slepov
Priority: Blocker
Fix For: 3.0
SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
The problem is formulated as
min(1*t + 0*L) (for every r-th subject)
s.t.
-q(r) + QL >= 0
x(r)t - XL >= 0
L >= 0
where
r = 1..R,
L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
Q - coefficients matrix MxR
X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13420526#comment-13420526 ]
Gilles commented on MATH-828:
-----------------------------
bq. [...] I need to use SVN to get 3.1 [...]
The link refers to the development branch (it's not yet 3.1).
Yes, that's the way to get the up-to-date version of the code.
If you don't want to compile the code (which requires the "maven" software), you could also download a snapshot JAR:
https://repository.apache.org/content/repositories/snapshots/org/apache/commons/commons-math3/3.1-SNAPSHOT/
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13423874#comment-13423874 ]
Alexey Slepov edited comment on MATH-828 at 7/27/12 1:50 PM:
-------------------------------------------------------------
Another parameter I've playd around with is maxUlps
As far as I see it's Precision.equals(double x, double y, int maxUlps) where maxUlps is used
public static boolean equals(double x, double y, int maxUlps) {
long xInt = Double.doubleToLongBits(x);
long yInt = Double.doubleToLongBits(y);
// Make lexicographically ordered as a two's-complement integer.
if (xInt < 0) {
xInt = SGN_MASK - xInt;
}
if (yInt < 0) {
yInt = SGN_MASK - yInt;
}
final boolean isEqual = FastMath.abs(xInt - yInt) <= maxUlps;
return isEqual && !Double.isNaN(x) && !Double.isNaN(y);
}
I've made several more experiments. Notice that on each iteration
SimplexSolver solver = new SimplexSolver(epsilon, maxUlps);
try
{
solver.setMaxIterations(maxIterationsCount);
PointValuePair optimum = solver.optimize(objectiveFunction, constraints, GoalType.MINIMIZE, true);
code is called for each entity. I.e. when 1024 iterations there are 1024*ENTITIES_COUNT = 1024*15 calls of new instances of SimplexSolver
Sum of input and output arguments is equal to number of variables - 1. In this case there were 8 variables for the objective function.
These below are results of experiments with different maxUlps values
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 0
8 unbounded solutions of 1024 iterations ( = 0.0078125 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
48 maxcount exceeded exception of 1024 iterations ( = 0.046875 of 1)
Total 56.0 failures of 1024 iterations ( = 0.0546875 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 2
13 unbounded solutions of 1024 iterations ( = 0.0126953125 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
67 maxcount exceeded exception of 1024 iterations ( = 0.0654296875 of 1)
Total 80.0 failures of 1024 iterations ( = 0.078125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 4
16 unbounded solutions of 1024 iterations ( = 0.015625 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
45 maxcount exceeded exception of 1024 iterations ( = 0.0439453125 of 1)
Total 62.0 failures of 1024 iterations ( = 0.060546875 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 6
21 unbounded solutions of 1024 iterations ( = 0.0205078125 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
50 maxcount exceeded exception of 1024 iterations ( = 0.048828125 of 1)
Total 71.0 failures of 1024 iterations ( = 0.0693359375 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 8
13 unbounded solutions of 1024 iterations ( = 0.0126953125 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
39 maxcount exceeded exception of 1024 iterations ( = 0.0380859375 of 1)
Total 53.0 failures of 1024 iterations ( = 0.0517578125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 25
24 unbounded solutions of 1024 iterations ( = 0.0234375 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
44 maxcount exceeded exception of 1024 iterations ( = 0.04296875 of 1)
Total 69.0 failures of 1024 iterations ( = 0.0673828125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 30
19 unbounded solutions of 1024 iterations ( = 0.0185546875 of 1)
2 nofeasible solutions of 1024 iterations ( = 0.001953125 of 1)
43 maxcount exceeded exception of 1024 iterations ( = 0.0419921875 of 1)
Total 64.0 failures of 1024 iterations ( = 0.0625 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 35
15 unbounded solutions of 1024 iterations ( = 0.0146484375 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
36 maxcount exceeded exception of 1024 iterations ( = 0.03515625 of 1)
Total 52.0 failures of 1024 iterations ( = 0.05078125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 40
33 unbounded solutions of 1024 iterations ( = 0.0322265625 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
44 maxcount exceeded exception of 1024 iterations ( = 0.04296875 of 1)
Total 78.0 failures of 1024 iterations ( = 0.076171875 of 1)
It seems that maxUlps gives not much to the state of the problem.
I used https://repository.apache.org/content/repositories/snapshots/org/apache/commons/commons-math3/3.1-SNAPSHOT/commons-math3-3.1-20120726.144152-154.jar SNAPSHOT for this expirement set
was (Author: alexeyslepov):
Another parameter I've playd around with is maxUlps
As far as I see it's Precision.equals(double x, double y, int maxUlps) where maxUlps is used
public static boolean equals(double x, double y, int maxUlps) {
long xInt = Double.doubleToLongBits(x);
long yInt = Double.doubleToLongBits(y);
// Make lexicographically ordered as a two's-complement integer.
if (xInt < 0) {
xInt = SGN_MASK - xInt;
}
if (yInt < 0) {
yInt = SGN_MASK - yInt;
}
final boolean isEqual = FastMath.abs(xInt - yInt) <= maxUlps;
return isEqual && !Double.isNaN(x) && !Double.isNaN(y);
}
I've made several more experiments. Notice that on each iteration
SimplexSolver solver = new SimplexSolver(epsilon, maxUlps);
try
{
solver.setMaxIterations(maxIterationsCount);
PointValuePair optimum = solver.optimize(objectiveFunction, constraints, GoalType.MINIMIZE, true);
code is called for each entity. I.e. when 1024 iterations there are 1024*ENTITIES_COUNT = 1024*15 calls of new instances of SimplexSolver
Sum of input and output arguments is equal to number of variables - 1. In this case there were 8 variables for the objective function.
These below are results of experiments with different maxUlps values
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 0
8 unbounded solutions of 1024 iterations ( = 0.0078125 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
48 maxcount exceeded exception of 1024 iterations ( = 0.046875 of 1)
Total 56.0 failures of 1024 iterations ( = 0.0546875 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 2
13 unbounded solutions of 1024 iterations ( = 0.0126953125 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
67 maxcount exceeded exception of 1024 iterations ( = 0.0654296875 of 1)
Total 80.0 failures of 1024 iterations ( = 0.078125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 4
16 unbounded solutions of 1024 iterations ( = 0.015625 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
45 maxcount exceeded exception of 1024 iterations ( = 0.0439453125 of 1)
Total 62.0 failures of 1024 iterations ( = 0.060546875 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 6
21 unbounded solutions of 1024 iterations ( = 0.0205078125 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
50 maxcount exceeded exception of 1024 iterations ( = 0.048828125 of 1)
Total 71.0 failures of 1024 iterations ( = 0.0693359375 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 8
13 unbounded solutions of 1024 iterations ( = 0.0126953125 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
39 maxcount exceeded exception of 1024 iterations ( = 0.0380859375 of 1)
Total 53.0 failures of 1024 iterations ( = 0.0517578125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 25
24 unbounded solutions of 1024 iterations ( = 0.0234375 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
44 maxcount exceeded exception of 1024 iterations ( = 0.04296875 of 1)
Total 69.0 failures of 1024 iterations ( = 0.0673828125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 30
19 unbounded solutions of 1024 iterations ( = 0.0185546875 of 1)
2 nofeasible solutions of 1024 iterations ( = 0.001953125 of 1)
43 maxcount exceeded exception of 1024 iterations ( = 0.0419921875 of 1)
Total 64.0 failures of 1024 iterations ( = 0.0625 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 35
15 unbounded solutions of 1024 iterations ( = 0.0146484375 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
36 maxcount exceeded exception of 1024 iterations ( = 0.03515625 of 1)
Total 52.0 failures of 1024 iterations ( = 0.05078125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 40
33 unbounded solutions of 1024 iterations ( = 0.0322265625 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
44 maxcount exceeded exception of 1024 iterations ( = 0.04296875 of 1)
Total 78.0 failures of 1024 iterations ( = 0.076171875 of 1)
It seems that maxUlps gives not much to the state of the problem.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart updated MATH-828:
---------------------------------
Priority: Major (was: Blocker)
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13422151#comment-13422151 ]
Alexey Slepov edited comment on MATH-828 at 7/25/12 10:51 AM:
--------------------------------------------------------------
I've made several launches of the program with different values. Here is the result
These
final int INPUT_ARGUMENTS_COUNT = 4;
final int OUTPUT_ARGUMENTS_COUNT = 3;
final int MIN_ARGUMENT_VALUE = 1;
final int MAX_ARGUMENT_VALUE = 100;
final int ITERATIONS_COUNT = 512;
and
maxIterationsCount = 65536;
stay the same over all experiments
Experiment 1
final int ENTITIES_COUNT = 20;
final double EPSILON = 1E-5;
final boolean IS_INTEGER = false;
/*
IS_INTEGER is using in the source code as
value = MIN_ARGUMENT_VALUE + rand.nextInt(MAX_ARGUMENT_VALUE);
if(!IS_INTEGER){
value += rand.nextDouble();
}
where value is an entity' coefficient value that is a cell of Q and X matrices
*/
gives
13 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
34 maxcount exceeded exception of 512 iterations
Total 47.0 failures of 512 iterations ( = 0.091796875 of 1)
Experiment 2
final int ENTITIES_COUNT = 20;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
13 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
37 maxcount exceeded exception of 512 iterations
Total 50.0 failures of 512 iterations ( = 0.09765625 of 1)
Experiment 3
final int ENTITIES_COUNT = 20;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = true;
gives
11 unbounded solutions of 512 iterations
3 nofeasible solutions of 512 iterations
33 maxcount exceeded exception of 512 iterations
Total 47.0 failures of 512 iterations ( = 0.091796875 of 1)
Experiment 4
final int ENTITIES_COUNT = 15;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
10 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
18 maxcount exceeded exception of 512 iterations
Total 28.0 failures of 512 iterations ( = 0.0546875 of 1)
Experiment 5
final int ENTITIES_COUNT = 10;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
7 unbounded solutions of 512 iterations
1 nofeasible solutions of 512 iterations
16 maxcount exceeded exception of 512 iterations
Total 24.0 failures of 512 iterations ( = 0.046875 of 1)
Experiment 6
final int ENTITIES_COUNT = 5;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
3 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
0 maxcount exceeded exception of 512 iterations
Total 3.0 failures of 512 iterations ( = 0.005859375 of 1)
As you can see the most influence to the amount of failures gives the number of variables. When there are 5 of them the amount of failure is about a half of a precent which is satisfyingly. When there are 10 or more variables the amount of failures becomes unacceptable.
Please pay attention to the dependence of the amount of failures on the number of variables that is shown through experiments 3, 4, 5, 6
variables failures
20 47
15 28
10 24
5 3
These failures numbers would change from one experiment launch to another of course but not much, +/- 2 failures
was (Author: alexeyslepov):
I've made several launches of the program with different values. Here is the result
These
final int INPUT_ARGUMENTS_COUNT = 4;
final int OUTPUT_ARGUMENTS_COUNT = 3;
final int MIN_ARGUMENT_VALUE = 1;
final int MAX_ARGUMENT_VALUE = 100;
final int ITERATIONS_COUNT = 512;
and
maxIterationsCount = 65536;
stay the same over all experiments
Experiment 1
final int ENTITIES_COUNT = 20;
final double EPSILON = 1E-5;
final boolean IS_INTEGER = false;
/*
IS_INTEGER is using in the source code as
value = MIN_ARGUMENT_VALUE + rand.nextInt(MAX_ARGUMENT_VALUE);
if(!IS_INTEGER){
value += rand.nextDouble();
}
where value is an entity' coefficient value that is a cell of Q and X matrices
*/
gives
13 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
34 maxcount exceeded exception of 512 iterations
Total 47.0 failures of 512 iterations ( = 0.091796875 of 1)
Experiment 2
final int ENTITIES_COUNT = 20;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
13 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
37 maxcount exceeded exception of 512 iterations
Total 50.0 failures of 512 iterations ( = 0.09765625 of 1)
Experiment 3
final int ENTITIES_COUNT = 20;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = true;
gives
11 unbounded solutions of 512 iterations
3 nofeasible solutions of 512 iterations
33 maxcount exceeded exception of 512 iterations
Total 47.0 failures of 512 iterations ( = 0.091796875 of 1)
Experiment 4
final int ENTITIES_COUNT = 15;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
10 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
18 maxcount exceeded exception of 512 iterations
Total 28.0 failures of 512 iterations ( = 0.0546875 of 1)
Experiment 5
final int ENTITIES_COUNT = 10;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
7 unbounded solutions of 512 iterations
1 nofeasible solutions of 512 iterations
16 maxcount exceeded exception of 512 iterations
Total 24.0 failures of 512 iterations ( = 0.046875 of 1)
Experiment 6
final int ENTITIES_COUNT = 5;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
3 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
0 maxcount exceeded exception of 512 iterations
Total 3.0 failures of 512 iterations ( = 0.005859375 of 1)
As you can see the most influence to the amount of failures gives the number of variables. When there are 5 of them the amount of failure is about a half of a precent which is satisfyingly. When there are 10 or more variables the amount of failures becomes unacceptable.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13420518#comment-13420518 ]
Alexey Slepov commented on MATH-828:
------------------------------------
Thank you Thomas for reopenning and your confirmation that I use math3 properly. I'll play around with maxUIps setting and will try GLPK that I've heard about but haven't tryed yet.
Gilles am I right thinking that I need to use SVN to get 3.1 (r12317576)
svn checkout http://svn.apache.org/repos/asf/commons/proper/math/trunk commons-math3
?
or if I'm wrong please refer me to the proper link.
Thanks
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13418356#comment-13418356 ]
Alexey Slepov commented on MATH-828:
------------------------------------
And there is one more strange thing I see. Solutions of the problem that are not unbounded give value of t = 1 every single time while they are supposed to be within [0, 1]. E.g. in the predifend variables values case in the first iteration t1 is 1 and t2 is 0.25 (see Test #1)
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13427277#comment-13427277 ]
Gilles commented on MATH-828:
-----------------------------
Hi Thomas.
Wouldn't it be clearer (cf. description and subject of this issue) to open a new issue for the problem which you identified (cycling) together with a test case that induces it?
The new issue can reference this report so that the history can be recovered easily.
This will allow to resolve this issue, which accurately reflects its state from the perspective of the problem raised.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13423889#comment-13423889 ]
Gilles commented on MATH-828:
-----------------------------
Lines 74-78 in {{SimplexSolver}} look strange:
{code}
if (Precision.compareTo(entry, minValue, maxUlps) < 0) {
minValue = entry;
minPos = i;
}
{code}
Its seems like the "minValue" will not really be most negative negative coefficient, as claimed in the doc.
The larger "maxUlps", the most likely it will not be, in line with what you observe...
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected UnboundedSolutionException
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Gilles updated MATH-828:
------------------------
Fix Version/s: (was: 3.0)
3.1
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13418345#comment-13418345 ]
Alexey Slepov edited comment on MATH-828 at 7/19/12 3:15 PM:
-------------------------------------------------------------
ApacheSimplexWrapperTest.java is the entry point
ApacheSimplexWrapper.java is the main class
commons-math3-3.0.jar is that same Apache Math 3 Lib I use
Source code contatins come auxiliary method, almost all for printing. Just run ApacheSimplexWrapperTest.java with a debugger and run straight forward to the line 160 in ApacheSimplexWrapper.java where things happen
was (Author: alexeyslepov):
ApacheSimplexWrapperTest.java is the entry point
ApacheSimplexWrapper.java is the main class
commons-math3-3.0.jar is that same Apache Math 3 Lib I use
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13427252#comment-13427252 ]
Thomas Neidhart commented on MATH-828:
--------------------------------------
The first fix introduced Bland's rule to prevent cycling. In fact cycling still occurs, thats why I added the additional heuristic.
We need to better understand why cycling still occurs with Bland's rule and better fix this problem, than trying to circumvent it with a rule like it is implemented now.
It should hopefully not affect you, as with the latest version your problems seem to work pretty well, but I want a more general solution. The current fix may break for other type of problems.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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] [Reopened] (MATH-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart reopened MATH-828:
----------------------------------
Hi Alexey,
you are right, I was too quick to draw a conclusion, the way you setup the problem is indeed correct.
What I have seen is that you use a very small maxUlps setting in your solver. The default it 10 and should work better atm. I will further look into it, it seems to be related to numerical instabilities.
Solving the same problems with glpk seems to be more robust, which maybe due to the scaling that is applied there to improve numerical properties of the constraint matrix.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13418345#comment-13418345 ]
Alexey Slepov edited comment on MATH-828 at 7/19/12 3:09 PM:
-------------------------------------------------------------
ApacheSimplexWrapperTest.java is the entry point
ApacheSimplexWrapper.java is the main class
commons-math3-3.0.jar is that same Apache Math 3 Lib I use
was (Author: alexeyslepov):
ApacheSimplexWrapperTest.java is the entry point
ApacheSimplexWrapper.java is the main class
commons-math3-3.0.jar is exactly the Apache Math 3 Lib I use
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13424847#comment-13424847 ]
Thomas Neidhart commented on MATH-828:
--------------------------------------
Thanks for the feedback, I will further investigate the remaining maxcount exceptions.
In my dev environment I mainly tested with 15 entities.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13427918#comment-13427918 ]
Alexey Slepov commented on MATH-828:
------------------------------------
Thomas, when you'll open a new thread for further investigation of the issue, post here a link to that thread, please
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13422151#comment-13422151 ]
Alexey Slepov commented on MATH-828:
------------------------------------
I've made several launches of the program with different values. Here is the result
These
final int INPUT_ARGUMENTS_COUNT = 4;
final int OUTPUT_ARGUMENTS_COUNT = 3;
final int MIN_ARGUMENT_VALUE = 1;
final int MAX_ARGUMENT_VALUE = 100;
final int ITERATIONS_COUNT = 512;
and
maxIterationsCount = 65536;
stay the same over all experiments
Experiment 1
final int ENTITIES_COUNT = 20;
final double EPSILON = 1E-5;
final boolean IS_INTEGER = false;
/*
IS_INTEGER is using in the source code as
value = MIN_ARGUMENT_VALUE + rand.nextInt(MAX_ARGUMENT_VALUE);
if(!IS_INTEGER){
value += rand.nextDouble();
}
where value is an entity' coefficient value that is a cell of Q and X matrices
*/
gives
13 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
34 maxcount exceeded exception of 512 iterations
Total 47.0 failures of 512 iterations ( = 0.091796875 of 1)
Experiment 2
final int ENTITIES_COUNT = 20;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
13 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
37 maxcount exceeded exception of 512 iterations
Total 50.0 failures of 512 iterations ( = 0.09765625 of 1)
Experiment 3
final int ENTITIES_COUNT = 20;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = true;
gives
11 unbounded solutions of 512 iterations
3 nofeasible solutions of 512 iterations
33 maxcount exceeded exception of 512 iterations
Total 47.0 failures of 512 iterations ( = 0.091796875 of 1)
Experiment 4
final int ENTITIES_COUNT = 15;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
10 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
18 maxcount exceeded exception of 512 iterations
Total 28.0 failures of 512 iterations ( = 0.0546875 of 1)
Experiment 5
final int ENTITIES_COUNT = 10;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
7 unbounded solutions of 512 iterations
1 nofeasible solutions of 512 iterations
16 maxcount exceeded exception of 512 iterations
Total 24.0 failures of 512 iterations ( = 0.046875 of 1)
Experiment 6
final int ENTITIES_COUNT = 5;
final double EPSILON = 1E-8;
final boolean IS_INTEGER = false;
gives
3 unbounded solutions of 512 iterations
0 nofeasible solutions of 512 iterations
0 maxcount exceeded exception of 512 iterations
Total 3.0 failures of 512 iterations ( = 0.005859375 of 1)
As you can see the most influence to the amount of failures gives the number of variables. When there are 5 of them the amount of failure is about a half of a precent which is satisfyingly. When there are 10 or more variables the amount of failures becomes unacceptable.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13428876#comment-13428876 ]
Thomas Neidhart commented on MATH-828:
--------------------------------------
Hi Alexey,
I linked the newly created issue to this one.
Thomas
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13425154#comment-13425154 ]
Thomas Neidhart commented on MATH-828:
--------------------------------------
I further investigated the remaining problems and came up with an empirical heuristic:
* If we have not found a solution after half of maxIterations, ignore Bland's rule and revert to the top-most row
I did extensive tests with your provided test case and did not receive any exceptions anymore.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13423874#comment-13423874 ]
Alexey Slepov commented on MATH-828:
------------------------------------
Another parameter I've playd around with is maxUlps
As far as I see it's Precision.equals(double x, double y, int maxUlps) where maxUlps is used
public static boolean equals(double x, double y, int maxUlps) {
long xInt = Double.doubleToLongBits(x);
long yInt = Double.doubleToLongBits(y);
// Make lexicographically ordered as a two's-complement integer.
if (xInt < 0) {
xInt = SGN_MASK - xInt;
}
if (yInt < 0) {
yInt = SGN_MASK - yInt;
}
final boolean isEqual = FastMath.abs(xInt - yInt) <= maxUlps;
return isEqual && !Double.isNaN(x) && !Double.isNaN(y);
}
I've made several more experiments. Notice that on each iteration
SimplexSolver solver = new SimplexSolver(epsilon, maxUlps);
try
{
solver.setMaxIterations(maxIterationsCount);
PointValuePair optimum = solver.optimize(objectiveFunction, constraints, GoalType.MINIMIZE, true);
code is called for each entity. I.e. when 1024 iterations there are 1024*ENTITIES_COUNT = 1024*15 calls of new instances of SimplexSolver
Sum of input and output arguments is equal to number of variables - 1. In this case there were 8 variables for the objective function.
These below are results of experiments with different maxUlps values
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 0
8 unbounded solutions of 1024 iterations ( = 0.0078125 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
48 maxcount exceeded exception of 1024 iterations ( = 0.046875 of 1)
Total 56.0 failures of 1024 iterations ( = 0.0546875 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 2
13 unbounded solutions of 1024 iterations ( = 0.0126953125 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
67 maxcount exceeded exception of 1024 iterations ( = 0.0654296875 of 1)
Total 80.0 failures of 1024 iterations ( = 0.078125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 4
16 unbounded solutions of 1024 iterations ( = 0.015625 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
45 maxcount exceeded exception of 1024 iterations ( = 0.0439453125 of 1)
Total 62.0 failures of 1024 iterations ( = 0.060546875 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 6
21 unbounded solutions of 1024 iterations ( = 0.0205078125 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
50 maxcount exceeded exception of 1024 iterations ( = 0.048828125 of 1)
Total 71.0 failures of 1024 iterations ( = 0.0693359375 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 8
13 unbounded solutions of 1024 iterations ( = 0.0126953125 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
39 maxcount exceeded exception of 1024 iterations ( = 0.0380859375 of 1)
Total 53.0 failures of 1024 iterations ( = 0.0517578125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 25
24 unbounded solutions of 1024 iterations ( = 0.0234375 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
44 maxcount exceeded exception of 1024 iterations ( = 0.04296875 of 1)
Total 69.0 failures of 1024 iterations ( = 0.0673828125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 30
19 unbounded solutions of 1024 iterations ( = 0.0185546875 of 1)
2 nofeasible solutions of 1024 iterations ( = 0.001953125 of 1)
43 maxcount exceeded exception of 1024 iterations ( = 0.0419921875 of 1)
Total 64.0 failures of 1024 iterations ( = 0.0625 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 35
15 unbounded solutions of 1024 iterations ( = 0.0146484375 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
36 maxcount exceeded exception of 1024 iterations ( = 0.03515625 of 1)
Total 52.0 failures of 1024 iterations ( = 0.05078125 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8, maxUlps = 40
33 unbounded solutions of 1024 iterations ( = 0.0322265625 of 1)
1 nofeasible solutions of 1024 iterations ( = 9.765625E-4 of 1)
44 maxcount exceeded exception of 1024 iterations ( = 0.04296875 of 1)
Total 78.0 failures of 1024 iterations ( = 0.076171875 of 1)
It seems that maxUlps gives not much to the state of the problem.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13424762#comment-13424762 ]
Alexey Slepov commented on MATH-828:
------------------------------------
Thank you very much, Thomas! Now it works well!
5 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-6, maxUlps = 10
0 unbounded solutions of 1024 iterations ( = 0.0 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
0 maxcount exceeded exception of 1024 iterations ( = 0.0 of 1)
Total 0.0 failures of 1024 iterations ( = 0.0 of 1)
10 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-6, maxUlps = 10
0 unbounded solutions of 1024 iterations ( = 0.0 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
0 maxcount exceeded exception of 1024 iterations ( = 0.0 of 1)
Total 0.0 failures of 1024 iterations ( = 0.0 of 1)
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-6, maxUlps = 10
0 unbounded solutions of 1024 iterations ( = 0.0 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
0 maxcount exceeded exception of 1024 iterations ( = 0.0 of 1)
Total 0.0 failures of 1024 iterations ( = 0.0 of 1)
20 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-6, maxUlps = 10
0 unbounded solutions of 1024 iterations ( = 0.0 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
2 maxcount exceeded exception of 1024 iterations ( = 0.001953125 of 1)
Total 2.0 failures of 1024 iterations ( = 0.001953125 of 1)
25 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-6, maxUlps = 10
0 unbounded solutions of 1024 iterations ( = 0.0 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
2 maxcount exceeded exception of 1024 iterations ( = 0.001953125 of 1)
Total 2.0 failures of 1024 iterations ( = 0.001953125 of 1)
30 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-6, maxUlps = 10
0 unbounded solutions of 1024 iterations ( = 0.0 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
3 maxcount exceeded exception of 1024 iterations ( = 0.0029296875 of 1)
Total 3.0 failures of 1024 iterations ( = 0.0029296875 of 1)
https://repository.apache.org/content/repositories/snapshots/org/apache/commons/commons-math3/3.1-SNAPSHOT/commons-math3-3.1-20120729.124827-157.jar
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13426926#comment-13426926 ]
Thomas Neidhart commented on MATH-828:
--------------------------------------
Hmm, I am no so sure if the last fix is the right way to go. I will leave this issue open and will investigate more on the topic.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13424375#comment-13424375 ]
Thomas Neidhart commented on MATH-828:
--------------------------------------
In r1366707, I committed the following changes to the SimplexSolver:
* do not use maxUlps in getPivotColumn and getPivotRow when trying to find a minimum
this is contra-productive, and the check should be strict
* implement Bland's rule to prevent cycling when selecting the pivot row in case of multiple candidates
* to improve numerical stability, introduce a CUTOFF_THRESHOLD (currently 1e-12) to zero-out
values that are smaller than this threshold in SimplexTableau.subtractRow
With these changes your tests run through without any errors. Could you please verify yourself and confirm.
Thanks,
Thomas
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart resolved MATH-828.
----------------------------------
Resolution: Fixed
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13425638#comment-13425638 ]
Alexey Slepov commented on MATH-828:
------------------------------------
I confirm that those new improvements erased errors were remaining.
Tests of
https://repository.apache.org/content/repositories/snapshots/org/apache/commons/commons-math3/3.1-SNAPSHOT/commons-math3-3.1-20120730.205101-159.jar
gives
15 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8
0 unbounded solutions of 1024 iterations ( = 0.0 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
0 maxcount exceeded exception of 1024 iterations ( = 0.0 of 1)
Total 0.0 failures of 1024 iterations ( = 0.0 of 1)
25 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8
0 unbounded solutions of 1024 iterations ( = 0.0 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
0 maxcount exceeded exception of 1024 iterations ( = 0.0 of 1)
Total 0.0 failures of 1024 iterations ( = 0.0 of 1)
35 entities, 4 input arguments, 3 output arguments, epsilon = 1.0E-8
0 unbounded solutions of 1024 iterations ( = 0.0 of 1)
0 nofeasible solutions of 1024 iterations ( = 0.0 of 1)
0 maxcount exceeded exception of 1024 iterations ( = 0.0 of 1)
Total 0.0 failures of 1024 iterations ( = 0.0 of 1)
Excellent! Thank you, Thomas!
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13418350#comment-13418350 ]
Alexey Slepov edited comment on MATH-828 at 7/19/12 3:13 PM:
-------------------------------------------------------------
Source code contatins come auxiliary method, almost all for printing. Just run ApacheSimplexWrapperTest.java with a debugger and run straight forward to the line 160 in ApacheSimplexWrapper.java where things happen
was (Author: alexeyslepov):
Source code contatins come auxiliary method, almost for printing. Just run ApacheSimplexWrapperTest.java with a debugger and run straight forward to the line 160 in ApacheSimplexWrapper.java where things happen
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13418591#comment-13418591 ]
Thomas Neidhart commented on MATH-828:
--------------------------------------
Hi Alexey,
I have looked at your updated test case, and my observation is as follows:
You create lots of constraints (L >= 0) that are unnecessary as the solver is already configured to restrict variables to non-negative values.
I also think you use the objective function in a wrong way. It is defined as:
{noformat}
c1*x1 + ... cn*xn + d
{noformat}
so at index 0 you have the coefficient for the first variable, .... and the last index is for the constant term. Now you use something called theta, which you put on index 0 which is wrong imho.
If I remove all the unnecessary constraints, and move the theta variable to the end of the objective function vector, the tests run through successfully.
Thomas
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Alexey Slepov updated MATH-828:
-------------------------------
Attachment: commons-math3-3.0.jar
ApacheSimplexWrapperTest.java
ApacheSimplexWrapper.java
Entity.java
ApacheSimplexWrapperTest.java is the entry point
ApacheSimplexWrapper.java is the main class
commons-math3-3.0.jar is exactly the Apache Math 3 Lib I use
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13420534#comment-13420534 ]
Alexey Slepov commented on MATH-828:
------------------------------------
Now with 3.1-SNAPSHOT things are going better. Number of unbounded exceptions and unexpected theta values (> 1) are fewer versus math 3.0.
Now the picture of failures and successes for
25 entities (i.e. 25 + 1 variables) with 7 constraint equations, 3 for -q(r) + QL >= 0 and 4 for x(r)*t - XL >= 0
looks like
Iteration 1 of 64
Iteration 2 of 64
Iteration 3 of 64
Iteration 4 of 64
Iteration 5 of 64
EXCEPTION: illegal state: maximal count (32,768) exceeded
Iteration 6 of 64
Iteration 7 of 64
EXCEPTION: illegal state: maximal count (32,768) exceeded
Iteration 8 of 64
Iteration 9 of 64
Iteration 10 of 64
Iteration 11 of 64
Iteration 12 of 64
Iteration 13 of 64
Iteration 14 of 64
Iteration 15 of 64
Iteration 16 of 64
Iteration 17 of 64
Iteration 18 of 64
Iteration 19 of 64
Iteration 20 of 64
EXCEPTION: illegal state: maximal count (32,768) exceeded
Iteration 21 of 64
Iteration 22 of 64
Iteration 23 of 64
EXCEPTION: illegal state: maximal count (32,768) exceeded
Iteration 24 of 64
Iteration 25 of 64
Iteration 26 of 64
EXCEPTION: unbounded solution
Iteration 27 of 64
Iteration 28 of 64
Iteration 29 of 64
Iteration 30 of 64
Iteration 31 of 64
Iteration 32 of 64
Iteration 33 of 64
EXCEPTION: illegal state: maximal count (32,768) exceeded
Iteration 34 of 64
EXCEPTION: illegal state: maximal count (32,768) exceeded
Iteration 35 of 64
Iteration 36 of 64
Iteration 37 of 64
EXCEPTION: illegal state: maximal count (32,768) exceeded
Iteration 38 of 64
Iteration 39 of 64
EXCEPTION: illegal state: maximal count (32,768) exceeded
Iteration 40 of 64
Iteration 41 of 64
Iteration 42 of 64
Iteration 43 of 64
Iteration 44 of 64
Iteration 45 of 64
EXCEPTION: illegal state: maximal count (32,768) exceeded
Iteration 46 of 64
Iteration 47 of 64
Iteration 48 of 64
Iteration 49 of 64
Iteration 50 of 64
Iteration 51 of 64
Iteration 52 of 64
Iteration 53 of 64
Iteration 54 of 64
Iteration 55 of 64
Iteration 56 of 64
Iteration 57 of 64
Iteration 58 of 64
Iteration 59 of 64
Iteration 60 of 64
Iteration 61 of 64
Iteration 62 of 64
EXCEPTION: illegal state: maximal count (32,768) exceeded
Iteration 63 of 64
Iteration 64 of 64
for the code
SimplexSolver solver = new SimplexSolver(epsilon, 15);
try
{
solver.setMaxIterations(32768);
PointValuePair optimum = solver.optimize(objectiveFunction, constraints, GoalType.MINIMIZE, true);
...
It's much better but it's still to risky to use math 3 to solve problems of this kind in real-world projects.
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Alexey Slepov updated MATH-828:
-------------------------------
Comment: was deleted
(was: Source code contatins come auxiliary method, almost all for printing. Just run ApacheSimplexWrapperTest.java with a debugger and run straight forward to the line 160 in ApacheSimplexWrapper.java where things happen)
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13427914#comment-13427914 ]
Thomas Neidhart commented on MATH-828:
--------------------------------------
Hi Gilles,
the cycling problem has been fixed (+ test case) but in a way that may be very specific to the problem definition of Alexey.
But I am fine with closing this issue and creating a new one to further investigate the issue.
Thomas
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13418468#comment-13418468 ]
Gilles commented on MATH-828:
-----------------------------
Did you test with a recent development snapshot?
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13419013#comment-13419013 ]
Alexey Slepov commented on MATH-828:
------------------------------------
Thomas, thanks for reference that the solver is already configured to restrict variables to non-negative values. That signally decreased time the solver needed to find solution as much as decreased the number of UnboundedSolutionExceptions.
As to the objective, there is a misunderstanding I believe.
I use the definition of the objective as it's declared in http://commons.apache.org/math/apidocs/org/apache/commons/math/optimization/linear/LinearObjectiveFunction.html
and theta is x1 and there are R+1 variables. R is the number of objects the omtimum is to find for (ENTITIES_COUNT) that is equal to the number of lambdas l(i). And as it shown in the very first test of the JUnit test where Q = [1,2], X = [2,1] and L = T[l1, l2] the solver gives an expected result. That is the indicator that equations are written properly. In other words for every single of N entities there has to be an objective with N + 1 variables. For the case of 2 entities the 3 dimension space is used to build a surface that has it's theta or x(1) coordinate set to minimum, for the case of 3 entities the 4 dimension space is used to build a shape that has it's theta or x(1) coordinate set to minimum and etc.
Here is how it looks for the simplest case (JUnit test #0)
Model name: DEA problem
t L1 L2
Minimize 1 0 0
R1 0 2 1 >= 1
R2 2 -1 -2 >= 0
R3 0 1 0 >= 0
R4 0 0 1 >= 0
Type Real Real Real
upbo Inf Inf Inf
lowbo 0 0 0
the objective is to be 0.25 and theta = 0.25 and L1 = 0.5, L2 = 0
The solver gives the same result for the case.
But only I add more entities to find minimum for as the same add more lambdas the solver gives back wrong answer, unbounded solution or theta greater than 1 (that is wrong due to the problem condition)
I'm sure it's been really too early to close the issue :(
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13418350#comment-13418350 ]
Alexey Slepov commented on MATH-828:
------------------------------------
Source code contatins come auxiliary method, almost for printing. Just run ApacheSimplexWrapperTest.java with a debugger and run straight forward to the line 160 in ApacheSimplexWrapper.java where things happen
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Priority: Blocker
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Alexey Slepov (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13427211#comment-13427211 ]
Alexey Slepov commented on MATH-828:
------------------------------------
What can go wrong with the last fix?
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Assignee: Thomas Neidhart
> Labels: linear, math, programming
> Fix For: 3.1
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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-828) Not expected
UnboundedSolutionException
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart resolved MATH-828.
----------------------------------
Resolution: Invalid
I close this issue also as invalid, as there is nothing wrong with the solver itself. You may also ask questions regarding the use of the simplex solver on the commons-user mailinglist.
Thomas
> Not expected UnboundedSolutionException
> ---------------------------------------
>
> Key: MATH-828
> URL: https://issues.apache.org/jira/browse/MATH-828
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.0
> Environment: Intel Core i5-2300 Windows XP SP3
> Reporter: Alexey Slepov
> Labels: linear, math, programming
> Fix For: 3.0
>
> Attachments: ApacheSimplexWrapper.java, ApacheSimplexWrapperTest.java, Entity.java, commons-math3-3.0.jar
>
>
> SimplexSolver throws UnboundedSolutionException when trying to solve minimization linear programming problem. The number of exception thrown depends on the number of variables.
> In order to see that behavior of SimplexSolver first try to run JUnit test setting a final variable ENTITIES_COUNT = 2 and that will give almost good result and then set it to 15 and you'll get a massive of unbounded exceptions.
> First iteration is runned with predefined set of input data with which the Solver gives back an appropriate result.
> The problem itself is well tested by it's authors (mathematicians who I believe know what they developed) using Matlab 10 with no unbounded solutions on the same rules of creatnig random variables values.
> What is strange to me is the dependence of the number of UnboundedSolutionException exceptions on the number of variables in the problem.
> The problem is formulated as
> min(1*t + 0*L) (for every r-th subject)
> s.t.
> -q(r) + QL >= 0
> x(r)t - XL >= 0
> L >= 0
> where
> r = 1..R,
> L = {l(1), l(2), ..., l(R)} (vector of R rows and 1 column),
> Q - coefficients matrix MxR
> X - coefficients matrix NxR
--
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