[
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
