[
https://issues.apache.org/jira/browse/MATH-842?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13767885#comment-13767885
]
Thomas Neidhart edited comment on MATH-842 at 9/15/13 7:49 PM:
---------------------------------------------------------------
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
* increase 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.
was (Author: tn):
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
