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 Sun, 15 Sep 2013 19:47:52 GMT

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

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

In r1523495 applied the following changes to the old, deprecated SimplexSolver in the optimization.linear
package:

 * apply Bland's rule also for pivot column selection as described in http://www.stanford.edu/class/msande310/blandrule.pdf
 * add getter/setter for cyclePrevention, default is true
 * reduce default cut-off threshold to 1e-10
 * added test to demonstrate a cycle of the simplex algorithm

With these changes, the solver works very stable, also on the problem attached to MATH-828
which resulted in the addition of Bland's rule.

The change has also to be applied to the new SimplexSolver in the optim.linear package. When
copying the code there has been an additional mistake: Bland's rule was never applied as the
criteria was based on getEvaluations(), which is never incremented by the simplex solver and
not supported.
                
> 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
>
> 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