|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.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
Solves a linear problem using the "Two-Phase Simplex" method.
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.
Field Summary | |
---|---|
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). |
Fields inherited from class org.apache.commons.math3.optim.BaseOptimizer |
---|
evaluations, iterations |
Constructor Summary | |
---|---|
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 | |
---|---|
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 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). |
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, optimize, parseOptimizationData |
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 |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
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
Constructor Detail |
---|
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.Method Detail |
---|
private Integer getPivotColumn(SimplexTableau tableau)
tableau
- Simple tableau for the problem.
private 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
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |