commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alexey Slepov (JIRA)" <j...@apache.org>
Subject [jira] [Comment Edited] (MATH-828) Not expected UnboundedSolutionException
Date Fri, 27 Jul 2012 13:51:35 GMT

    [ 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

        

Mime
View raw message