Class SimplexSolver
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, defaultPivotSelectionRule.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
-
Field Summary
Fields inherited from class org.apache.commons.math3.optim.BaseOptimizer
evaluations, iterations -
Constructor Summary
ConstructorsConstructorDescriptionBuilds 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 TypeMethodDescriptionprotected voiddoIteration(org.apache.commons.math3.optim.linear.SimplexTableau tableau) Runs one iteration of the Simplex method on the given model.Performs the bulk of the optimization algorithm.optimize(OptimizationData... optData) Stores data and performs the optimization.protected voidparseOptimizationData(OptimizationData... optData) Scans the list of (required and optional) optimization data that characterize the problem.protected voidsolvePhase1(org.apache.commons.math3.optim.linear.SimplexTableau tableau) Solves Phase 1 of the Simplex method.Methods inherited from class org.apache.commons.math3.optim.linear.LinearOptimizer
getConstraints, getFunction, isRestrictedToNonNegativeMethods inherited from class org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer
computeObjectiveValue, getGoalTypeMethods inherited from class org.apache.commons.math3.optim.BaseMultivariateOptimizer
getLowerBound, getStartPoint, getUpperBoundMethods inherited from class org.apache.commons.math3.optim.BaseOptimizer
getConvergenceChecker, getEvaluations, getIterations, getMaxEvaluations, getMaxIterations, incrementEvaluationCount, incrementIterationCount, optimize
-
Constructor Details
-
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 Details
-
optimize
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 callsuper.parseOptimizationData(optData)within that method.- Overrides:
optimizein classLinearOptimizer- Parameters:
optData- Optimization data. In addition to those documented inLinearOptimizer, this method will register the following data:- Returns:
- a point/value pair that satisfies the convergence criteria.
- Throws:
TooManyIterationsException- if the maximal number of iterations is exceeded.
-
parseOptimizationData
Scans the list of (required and optional) optimization data that characterize the problem.- Overrides:
parseOptimizationDatain classLinearOptimizer- Parameters:
optData- Optimization data. In addition to those documented inLinearOptimizer, this method will register the following data:
-
doIteration
protected void doIteration(org.apache.commons.math3.optim.linear.SimplexTableau tableau) throws TooManyIterationsException, UnboundedSolutionException Runs one iteration of the Simplex method on the given model.- Parameters:
tableau- Simple tableau for the problem.- Throws:
TooManyIterationsException- if the allowed number of iterations has been exhausted.UnboundedSolutionException- if the model is found not to have a bounded solution.
-
solvePhase1
protected void solvePhase1(org.apache.commons.math3.optim.linear.SimplexTableau tableau) throws TooManyIterationsException, UnboundedSolutionException, NoFeasibleSolutionException Solves Phase 1 of the Simplex method.- Parameters:
tableau- Simple tableau for the problem.- Throws:
TooManyIterationsException- if the allowed number of iterations has been exhausted.UnboundedSolutionException- if the model is found not to have a bounded solution.NoFeasibleSolutionException- if there is no feasible solution?
-
doOptimize
public PointValuePair doOptimize() throws TooManyIterationsException, UnboundedSolutionException, NoFeasibleSolutionExceptionPerforms the bulk of the optimization algorithm.- Specified by:
doOptimizein classBaseOptimizer<PointValuePair>- Returns:
- the point/value pair giving the optimal value of the objective function.
- Throws:
TooManyIterationsExceptionUnboundedSolutionExceptionNoFeasibleSolutionException
-