[jira] [Comment Edited] (MATH-842) Investigate why Bland's rule in Simplex Solver still creates cycles

["Thomas Neidhart (JIRA)" <ji...@apache.org>]

    [ 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