public class SimplexSolver extends LinearOptimizer
The SimplexSolver
supports the following OptimizationData
data provided
as arguments to optimize(OptimizationData...)
:
LinearObjectiveFunction
- mandatoryLinearConstraintSet
- mandatoryGoalType
- optional, default: MINIMIZE
NonNegativeConstraint
- optional, default: truePivotSelectionRule
- optional, default PivotSelectionRule.DANTZIG
SolutionCallback
- optionalMaxIter
- 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:
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
.
Modifier and Type | Field and Description |
---|---|
private double |
cutOff
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 double |
DEFAULT_CUT_OFF
Default cut-off value.
|
private static double |
DEFAULT_EPSILON
Default amount of error to accept for algorithm convergence.
|
(package private) static int |
DEFAULT_ULPS
Default amount of error to accept in floating point comparisons (as ulps).
|
private double |
epsilon
Amount of error to accept for algorithm convergence.
|
private int |
maxUlps
Amount of error to accept in floating point comparisons (as ulps).
|
private PivotSelectionRule |
pivotSelection
The pivot selection method to use.
|
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.
|
evaluations, iterations
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.
|
Modifier and Type | Method and Description |
---|---|
protected void |
doIteration(SimplexTableau tableau)
Runs one iteration of the Simplex method on the given model.
|
PointValuePair |
doOptimize()
Performs the bulk of the optimization algorithm.
|
private java.lang.Integer |
getPivotColumn(SimplexTableau tableau)
Returns the column with the most negative coefficient in the objective function row.
|
private java.lang.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.
|
PointValuePair |
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.
|
getConstraints, getFunction, isRestrictedToNonNegative
computeObjectiveValue, getGoalType
getLowerBound, getStartPoint, getUpperBound
getConvergenceChecker, getEvaluations, getIterations, getMaxEvaluations, getMaxIterations, incrementEvaluationCount, incrementIterationCount, optimize
static final int DEFAULT_ULPS
static final double DEFAULT_CUT_OFF
private static final double DEFAULT_EPSILON
private final double epsilon
private final int maxUlps
private final double cutOff
private PivotSelectionRule pivotSelection
private SolutionCallback solutionCallback
public SimplexSolver()
public SimplexSolver(double epsilon)
epsilon
- Amount of error to accept for algorithm convergence.public SimplexSolver(double epsilon, int maxUlps)
epsilon
- Amount of error to accept for algorithm convergence.maxUlps
- Amount of error to accept in floating point comparisons.public SimplexSolver(double epsilon, int maxUlps, double cutOff)
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.public PointValuePair optimize(OptimizationData... optData) throws TooManyIterationsException
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.
optimize
in class LinearOptimizer
optData
- Optimization data. In addition to those documented in
LinearOptimizer
, this method will register the following data:
TooManyIterationsException
- if the maximal number of iterations is exceeded.protected void parseOptimizationData(OptimizationData... optData)
parseOptimizationData
in class LinearOptimizer
optData
- Optimization data.
In addition to those documented in
LinearOptimizer
, this method will register the following data:
private java.lang.Integer getPivotColumn(SimplexTableau tableau)
tableau
- Simple tableau for the problem.private boolean isValidPivotColumn(SimplexTableau tableau, int col)
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.
tableau
- simplex tableau for the problemcol
- the column to testtrue
if the pivot column is valid, false
otherwiseprivate java.lang.Integer getPivotRow(SimplexTableau tableau, int col)
tableau
- Simplex tableau for the problem.col
- Column to test the ratio of (see getPivotColumn(SimplexTableau)
).protected void doIteration(SimplexTableau tableau) throws TooManyIterationsException, UnboundedSolutionException
tableau
- Simple tableau for the problem.TooManyIterationsException
- if the allowed number of iterations has been exhausted.UnboundedSolutionException
- if the model is found not to have a bounded solution.protected void solvePhase1(SimplexTableau tableau) throws TooManyIterationsException, UnboundedSolutionException, NoFeasibleSolutionException
tableau
- Simple tableau for the problem.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?public PointValuePair doOptimize() throws TooManyIterationsException, UnboundedSolutionException, NoFeasibleSolutionException
doOptimize
in class BaseOptimizer<PointValuePair>
TooManyIterationsException
UnboundedSolutionException
NoFeasibleSolutionException
Copyright (c) 2003-2016 Apache Software Foundation