Class SimplexSolver


  • public class SimplexSolver
    extends LinearOptimizer
    Solves a linear problem using the "Two-Phase Simplex" method.

    The SimplexSolver supports the following OptimizationData data provided as arguments to optimize(OptimizationData...):

    Note: Depending on the problem definition, the default convergence criteria may be too strict, resulting in NoFeasibleSolutionException or TooManyIterationsException. In such a case it is advised to adjust these criteria with more appropriate values, e.g. relaxing the epsilon value.

    Default convergence criteria:

    • Algorithm convergence: 1e-6
    • Floating-point comparisons: 10 ulp
    • Cut-Off value: 1e-10

    The cut-off value has been introduced to handle the case of very small pivot elements in the Simplex tableau, as these may lead to numerical instabilities and degeneracy. Potential pivot elements smaller than this value will be treated as if they were zero and are thus not considered by the pivot selection mechanism. The default value is safe for many problems, but may need to be adjusted in case of very small coefficients used in either the LinearConstraint or LinearObjectiveFunction.

    Since:
    2.0
    • Field Detail

      • DEFAULT_ULPS

        static final int DEFAULT_ULPS
        Default amount of error to accept in floating point comparisons (as ulps).
        See Also:
        Constant Field Values
      • DEFAULT_CUT_OFF

        static final double DEFAULT_CUT_OFF
        Default cut-off value.
        See Also:
        Constant Field Values
      • DEFAULT_EPSILON

        private static final double DEFAULT_EPSILON
        Default amount of error to accept for algorithm convergence.
        See Also:
        Constant Field Values
      • epsilon

        private final double epsilon
        Amount of error to accept for algorithm convergence.
      • maxUlps

        private final int maxUlps
        Amount of error to accept in floating point comparisons (as ulps).
      • cutOff

        private final double cutOff
        Cut-off value for entries in the tableau: values smaller than the cut-off are treated as zero to improve numerical stability.
      • pivotSelection

        private PivotSelectionRule pivotSelection
        The pivot selection method to use.
      • solutionCallback

        private SolutionCallback solutionCallback
        The solution callback to access the best solution found so far in case the optimizer fails to find an optimal solution within the iteration limits.
    • Constructor Detail

      • SimplexSolver

        public SimplexSolver()
        Builds a simplex solver with default settings.
      • SimplexSolver

        public SimplexSolver​(double epsilon)
        Builds a simplex solver with a specified accepted amount of error.
        Parameters:
        epsilon - Amount of error to accept for algorithm convergence.
      • SimplexSolver

        public SimplexSolver​(double epsilon,
                             int maxUlps)
        Builds a simplex solver with a specified accepted amount of error.
        Parameters:
        epsilon - Amount of error to accept for algorithm convergence.
        maxUlps - Amount of error to accept in floating point comparisons.
      • SimplexSolver

        public SimplexSolver​(double epsilon,
                             int maxUlps,
                             double cutOff)
        Builds a simplex solver with a specified accepted amount of error.
        Parameters:
        epsilon - Amount of error to accept for algorithm convergence.
        maxUlps - Amount of error to accept in floating point comparisons.
        cutOff - Values smaller than the cutOff are treated as zero.