[jira] [Resolved] (MATH-1079) Performance improvements for the SimplexSolver

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

     [ https://issues.apache.org/jira/browse/MATH-1079?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Thomas Neidhart resolved MATH-1079.
-----------------------------------

       Resolution: Fixed
    Fix Version/s: 3.3

Changed in r1551735:

 * perform row operations on the corresponding row array instead
   of retrieving/setting each element via getEntry/setEntry
 * keep track of the current basic variables

Doing tests with the mps files from netlib, this has shown a speed improvement of a factor of ~2. Further improvements are hard to achieve with the standard simplex algorithm. The best solvers, like lp_solve, implement the revised simplex algorithm which is far superior for large models, as it reduces the number of required row operations which are the bottle-neck.

Suggest to add an implementation of such a revised simplex algorithm in the future to be competitive with other optimization software.

> Performance improvements for the SimplexSolver
> ----------------------------------------------
>
>                 Key: MATH-1079
>                 URL: https://issues.apache.org/jira/browse/MATH-1079
>             Project: Commons Math
>          Issue Type: Improvement
>            Reporter: Thomas Neidhart
>             Fix For: 3.3
>
>
> Tests with various larger models in mps format from netlib.org have shown that there is a lot of room for improvements for the SimplexSolver.
> Currently, the tableau is stored in a RealMatrix, and each access to an entry uses the getEntry / setEntry methods which always does bounds checking. This is inefficient and unnecessary as we know that we access the matrix within bounds.
> Suggest to access the internal array directly for various operations. The walkInXXX method of RealMatrix can not always be used for this purpose.
> Also the getBasicRow() method can be a bottle-neck as it always needs to analyze the whole tableau to determine the row in which a variable is basic. It would be better to keep track of which variables are basic in which row.



--
This message was sent by Atlassian JIRA
(v6.1.4#6159)