[ 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