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 Wed, 25 Jul 2012 10:51:36 GMT

    [ 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

        

Mime
View raw message