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 Fri, 20 Jul 2012 09:01:35 GMT

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

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

Thomas, thanks for reference that the solver is already configured to restrict variables to
non-negative values. That signally decreased time the solver needed to find solution as much
as decreased the number of UnboundedSolutionExceptions.

As to the objective, there is a misunderstanding I believe.
I use the definition of the objective as it's declared in http://commons.apache.org/math/apidocs/org/apache/commons/math/optimization/linear/LinearObjectiveFunction.html
and theta is x1 and there are R+1 variables. R is the number of objects the omtimum is to
find for (ENTITIES_COUNT) that is equal to the number of lambdas l(i). And as it shown in
the very first test of the JUnit test where Q = [1,2], X = [2,1] and L = T[l1, l2] the solver
gives an expected result. That is the indicator that equations are written properly. In other
words for every single of N entities there has to be an objective with N + 1 variables. For
the case of 2 entities the 3 dimension space is used to build a surface that has it's theta
or x(1) coordinate set to minimum, for the case of 3 entities the 4 dimension space is used
to build a shape that has it's theta or x(1) coordinate set to minimum and etc.

Here is how it looks for the simplest case (JUnit test #0)

Model name: DEA problem
                 t       L1       L2 
Minimize         1        0        0 
R1               0        2        1 >=        1
R2               2       -1       -2 >=        0
R3               0        1        0 >=        0
R4               0        0        1 >=        0
Type          Real     Real     Real 
upbo           Inf      Inf      Inf 
lowbo            0        0        0 

the objective is to be 0.25 and theta = 0.25 and L1 = 0.5, L2 = 0
The solver gives the same result for the case.
But only I add more entities to find minimum for as the same add more lambdas the solver gives
back wrong answer, unbounded solution or theta greater than 1 (that is wrong due to the problem
condition)

I'm sure it's been really too early to close the issue :( 
                
> 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
>              Labels: linear, math, programming
>             Fix For: 3.0
>
>         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