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
FieldsModifier and TypeFieldDescriptionprivate final double
Cut-off value for entries in the tableau: values smaller than the cut-off are treated as zero to improve numerical stability.(package private) static final double
Default cut-off value.private static final double
Default amount of error to accept for algorithm convergence.(package private) static final int
Default amount of error to accept in floating point comparisons (as ulps).private final double
Amount of error to accept for algorithm convergence.private final int
Amount of error to accept in floating point comparisons (as ulps).private PivotSelectionRule
The pivot selection method to use.private 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.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 void
doIteration
(SimplexTableau tableau) Runs one iteration of the Simplex method on the given model.Performs the bulk of the optimization algorithm.private Integer
getPivotColumn
(SimplexTableau tableau) Returns the column with the most negative coefficient in the objective function row.private Integer
getPivotRow
(SimplexTableau tableau, int col) Returns the row with the minimum ratio as given by the minimum ratio test (MRT).private boolean
isValidPivotColumn
(SimplexTableau tableau, int col) Checks whether the given column is valid pivot column, i.e.optimize
(OptimizationData... optData) Stores data and performs the optimization.protected void
parseOptimizationData
(OptimizationData... optData) Scans the list of (required and optional) optimization data that characterize the problem.protected void
solvePhase1
(SimplexTableau tableau) Solves Phase 1 of the Simplex method.Methods inherited from class org.apache.commons.math3.optim.linear.LinearOptimizer
getConstraints, getFunction, isRestrictedToNonNegative
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, incrementEvaluationCount, incrementIterationCount, optimize
-
Field Details
-
DEFAULT_ULPS
static final int DEFAULT_ULPSDefault amount of error to accept in floating point comparisons (as ulps).- See Also:
-
DEFAULT_CUT_OFF
static final double DEFAULT_CUT_OFFDefault cut-off value.- See Also:
-
DEFAULT_EPSILON
private static final double DEFAULT_EPSILONDefault amount of error to accept for algorithm convergence.- See Also:
-
epsilon
private final double epsilonAmount of error to accept for algorithm convergence. -
maxUlps
private final int maxUlpsAmount of error to accept in floating point comparisons (as ulps). -
cutOff
private final double cutOffCut-off value for entries in the tableau: values smaller than the cut-off are treated as zero to improve numerical stability. -
pivotSelection
The pivot selection method to use. -
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 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:
optimize
in 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:
parseOptimizationData
in classLinearOptimizer
- Parameters:
optData
- Optimization data. In addition to those documented inLinearOptimizer
, this method will register the following data:
-
getPivotColumn
Returns the column with the most negative coefficient in the objective function row.- Parameters:
tableau
- Simple tableau for the problem.- Returns:
- the column with the most negative coefficient.
-
isValidPivotColumn
Checks whether the given column is valid pivot column, i.e. will result in a valid pivot row.When applying Bland's rule to select the pivot column, it may happen that there is no corresponding pivot row. This method will check if the selected pivot column will return a valid pivot row.
- Parameters:
tableau
- simplex tableau for the problemcol
- the column to test- Returns:
true
if the pivot column is valid,false
otherwise
-
getPivotRow
Returns the row with the minimum ratio as given by the minimum ratio test (MRT).- Parameters:
tableau
- Simplex tableau for the problem.col
- Column to test the ratio of (seegetPivotColumn(SimplexTableau)
).- Returns:
- the row with the minimum ratio.
-
doIteration
protected void doIteration(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(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:
doOptimize
in classBaseOptimizer<PointValuePair>
- Returns:
- the point/value pair giving the optimal value of the objective function.
- Throws:
TooManyIterationsException
UnboundedSolutionException
NoFeasibleSolutionException
-