public class SimplexSolver extends LinearOptimizer
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 zero out very small numbers in the Simplex tableau, as these may lead to numerical instabilities due to the nature of the Simplex algorithm (the pivot element is used as a denominator). If the problem definition is very tight, the default cut-off value may be too small, thus it is advised to increase it to a larger value, in accordance with the chosen epsilon.
It may also be counter-productive to provide a too large value for MaxIter
as parameter in the call of optimize(OptimizationData...)
,
as the SimplexSolver
will use different strategies depending on the current iteration
count. After half of the allowed max iterations has already been reached, the strategy to select
pivot rows will change in order to break possible cycles due to degenerate problems.
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).
|
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).
|
protected void |
solvePhase1(SimplexTableau tableau)
Solves Phase 1 of the Simplex method.
|
getConstraints, getFunction, isRestrictedToNonNegative, optimize, parseOptimizationData
computeObjectiveValue, getGoalType
getLowerBound, getStartPoint, getUpperBound
getConvergenceChecker, getEvaluations, getIterations, getMaxEvaluations, getMaxIterations, incrementEvaluationCount, incrementIterationCount
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
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.private java.lang.Integer getPivotColumn(SimplexTableau tableau)
tableau
- Simple tableau for the problem.private java.lang.Integer getPivotRow(SimplexTableau tableau, int col)
tableau
- Simple 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-2013 Apache Software Foundation