commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Thomas Neidhart (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MATH-842) Investigate why Bland's rule in Simplex Solver still creates cycles
Date Wed, 18 Sep 2013 10:59:55 GMT

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

Thomas Neidhart commented on MATH-842:
--------------------------------------

No, not really.

The options object would be just a container for lots of int/double/boolean/enum fields/flags
that would be provided to the solver, either before or during the optimize call. These options
are also very specific to the solver, so there is no need to generalize them in one way or
another. Implementing OptimizationData would allow to specify it during the call to optimize,
but I would also be fine to make it part of the solver interface, e.g. SimplexSolver.withSolverOptions(SimplexSolverOptions).

What I did not like about the OptimizationData is that we attempted to create a common interface
for things that are different, and that it was not clear which optimizer uses or requires
which input. It would make sense to unify things if you could replace one instance with another,
but this is clearly not the case: you can not use e.g. a BrentOptimizer to solve a linear
problem, yet the API allows it (at least theoretically).

We also did not gain anything wrt thread-safety, as each optimizer stores all the passed OptimizationData
in its instance (not that I think thread-safety for algorithm classes should be the main design
goal), and I did not see the benefit of providing all the required inputs as part of the call
to a generic optimize method.

What we should have done: exclude the optimize method from the BaseOptimizer class and provide
specific ones for classes of optimizers that support the Liskov substitution principle, e.g.
the LinearOptimizer defines a optimize method with a signature that *all* LinearOptimizer
instances support. Then you could create e.g. a DualSimplex or PrimalSimplex optimizer both
implementing the same interface, and you can exchange one implementation with another.
                
> Investigate why Bland's rule in Simplex Solver still creates cycles
> -------------------------------------------------------------------
>
>                 Key: MATH-842
>                 URL: https://issues.apache.org/jira/browse/MATH-842
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.1
>            Reporter: Thomas Neidhart
>            Assignee: Thomas Neidhart
>         Attachments: MATH-842.patch
>
>
> As a consequence of MATH-828, Bland's rule has been introduced to prevent cycling. Now
there are cases where cycles can still occur (see testMath828Cycle in SimplexSolverTest).
These cases have for now been solved with a simple heuristic:
>  * after maxIterations / 2 -> ignore Bland's rule
> This issue has been created to further investigate the problem and come up with a cleaner
solution.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira

Mime
View raw message