From issues-return-28521-apmail-commons-issues-archive=commons.apache.org@commons.apache.org Fri Jul 27 13:51:35 2012
Return-Path:
X-Original-To: apmail-commons-issues-archive@minotaur.apache.org
Delivered-To: apmail-commons-issues-archive@minotaur.apache.org
Received: from mail.apache.org (hermes.apache.org [140.211.11.3])
by minotaur.apache.org (Postfix) with SMTP id A736DD4D5
for ; Fri, 27 Jul 2012 13:51:35 +0000 (UTC)
Received: (qmail 44114 invoked by uid 500); 27 Jul 2012 13:51:35 -0000
Delivered-To: apmail-commons-issues-archive@commons.apache.org
Received: (qmail 43995 invoked by uid 500); 27 Jul 2012 13:51:35 -0000
Mailing-List: contact issues-help@commons.apache.org; run by ezmlm
Precedence: bulk
List-Help:
List-Unsubscribe:
List-Post:
List-Id:
Reply-To: issues@commons.apache.org
Delivered-To: mailing list issues@commons.apache.org
Received: (qmail 43917 invoked by uid 99); 27 Jul 2012 13:51:35 -0000
Received: from issues-vm.apache.org (HELO issues-vm) (140.211.11.160)
by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 27 Jul 2012 13:51:35 +0000
Received: from isssues-vm.apache.org (localhost [127.0.0.1])
by issues-vm (Postfix) with ESMTP id 0714D142856
for ; Fri, 27 Jul 2012 13:51:35 +0000 (UTC)
Date: Fri, 27 Jul 2012 13:51:35 +0000 (UTC)
From: "Alexey Slepov (JIRA)"
To: issues@commons.apache.org
Message-ID: <1093440420.110443.1343397095031.JavaMail.jiratomcat@issues-vm>
In-Reply-To: <375400049.75910.1342710455545.JavaMail.jiratomcat@issues-vm>
Subject: [jira] [Comment Edited] (MATH-828) Not expected
UnboundedSolutionException
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394
[ 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