Commons Math
  1. Commons Math
  2. MATH-1079

Performance improvements for the SimplexSolver

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.3
    • Labels:
      None

      Description

      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.

        Activity

        Hide
        Luc Maisonobe added a comment -

        Closing all resolved issue now available in released 3.3 version.

        Show
        Luc Maisonobe added a comment - Closing all resolved issue now available in released 3.3 version.
        Hide
        Thomas Neidhart added a comment - - edited

        After some thoughts there were still some substantial improvements possible:

        • do not perform subtractRow if the multiplier is exactly 0, as in this case nothing will change
        • move cutOff detection from row operations to pivot selection process
        • change default cutOff threshold from 1e-12 to 1e-10

        With these changes, execution speed further increased, test case grow15 from netlib:

        • before changes: ~10s
        • after first batch of changes: ~5s
        • now: ~1.5s

        Need to add performance tests based on the samples from netlib.
        Is it possible to add the example files from netlib to subversion considering licensing issues?

        Show
        Thomas Neidhart added a comment - - edited After some thoughts there were still some substantial improvements possible: do not perform subtractRow if the multiplier is exactly 0, as in this case nothing will change move cutOff detection from row operations to pivot selection process change default cutOff threshold from 1e-12 to 1e-10 With these changes, execution speed further increased, test case grow15 from netlib: before changes: ~10s after first batch of changes: ~5s now: ~1.5s Need to add performance tests based on the samples from netlib. Is it possible to add the example files from netlib to subversion considering licensing issues?
        Hide
        Thomas Neidhart added a comment -

        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.

        Show
        Thomas Neidhart added a comment - 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.

          People

          • Assignee:
            Unassigned
            Reporter:
            Thomas Neidhart
          • Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development