org.apache.commons.math3.optim.linear

Class SimplexSolver

java.lang.Object

org.apache.commons.math3.optim.BaseOptimizer<PAIR>

org.apache.commons.math3.optim.BaseMultivariateOptimizer<PointValuePair>

org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer

org.apache.commons.math3.optim.linear.LinearOptimizer

org.apache.commons.math3.optim.linear.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...):

• objective function: LinearObjectiveFunction - mandatory
• linear constraints LinearConstraintSet - mandatory
• type of optimization: GoalType - optional, default: MINIMIZE
• whether to allow negative values as solution: NonNegativeConstraint - optional, default: true
• pivot selection rule: PivotSelectionRule - optional, default PivotSelectionRule.DANTZIG
• callback for the best solution: SolutionCallback - optional
• maximum number of iterations: MaxIter - optional, default: Integer.MAX_VALUE

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

Constructor Summary

Constructors

Constructor and Description
SimplexSolver() Builds a simplex solver with default settings.
SimplexSolver(double epsilon) Builds a simplex solver with a specified accepted amount of error.
SimplexSolver(double epsilon, int maxUlps) Builds a simplex solver with a specified accepted amount of error.
SimplexSolver(double epsilon, int maxUlps, double cutOff) Builds a simplex solver with a specified accepted amount of error.

Method Summary

Modifier and Type	Method and Description
PointValuePair	doOptimize() Performs the bulk of the optimization algorithm.
PointValuePair	optimize(OptimizationData... optData) Stores data and performs the optimization.

Methods inherited from class org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer

computeObjectiveValue, getGoalType

Methods inherited from class org.apache.commons.math3.optim.BaseMultivariateOptimizer

getLowerBound, getStartPoint, getUpperBound

Methods inherited from class org.apache.commons.math3.optim.BaseOptimizer

getConvergenceChecker, getEvaluations, getIterations, getMaxEvaluations, getMaxIterations, optimize

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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.

Method Detail

optimize

public PointValuePair optimize(OptimizationData... optData)
                        throws TooManyIterationsException

Stores data and performs the optimization.

The list of parameters is open-ended so that sub-classes can extend it with arguments specific to their concrete implementations.

When the method is called multiple times, instance data is overwritten only when actually present in the list of arguments: when not specified, data set in a previous call is retained (and thus is optional in subsequent calls).

Important note: Subclasses must override BaseOptimizer.parseOptimizationData(OptimizationData[]) if they need to register their own options; but then, they must also call super.parseOptimizationData(optData) within that method.

Overrides:

optimize in class LinearOptimizer

Parameters:

optData - Optimization data. In addition to those documented in LinearOptimizer, this method will register the following data:

• SolutionCallback
• PivotSelectionRule

Returns:

a point/value pair that satisfies the convergence criteria.

Throws:

TooManyIterationsException - if the maximal number of iterations is exceeded.

doOptimize

public PointValuePair doOptimize()
                          throws TooManyIterationsException,
                                 UnboundedSolutionException,
                                 NoFeasibleSolutionException

Performs the bulk of the optimization algorithm.

Returns:

the point/value pair giving the optimal value of the objective function.

Throws:

TooManyIterationsException

UnboundedSolutionException

NoFeasibleSolutionException