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] [Commented] (MATH-828) Not expected UnboundedSolutionException
Date Wed, 25 Jul 2012 10:47:34 GMT

    [ https://issues.apache.org/jira/browse/MATH-828?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13422151#comment-13422151
] 

Alexey Slepov commented on MATH-828:
------------------------------------

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