Apache Commons Math 3.6.1 · org.apache.commons.math3.optim.linear.SimplexSolver

Solves a linear problem using the "Two-Phase Simplex" method.

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, default PivotSelectionRule#DANTZIG
callback for the best solution: SolutionCallback - optional
maximum number of iterations: org.apache.commons.math3.optim.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.

Field Summary

Modifier and Type	Field and Description
private final double	cutOff Cut-off value for entries in the tableau: values smaller than the cut-off are treated as zero to improve numerical stability.
pack-priv static final double	DEFAULT_CUT_OFF Default cut-off value.
private static final double	DEFAULT_EPSILON Default amount of error to accept for algorithm convergence.
pack-priv static final int	DEFAULT_ULPS Default amount of error to accept in floating point comparisons (as ulps).
private final double	epsilon Amount of error to accept for algorithm convergence.
private final 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.

Constructor Summary

Access	Constructor and Description
public	SimplexSolver() Builds a simplex solver with default settings.
public	SimplexSolver(final double Amount of error to accept for algorithm convergence. epsilon) Builds a simplex solver with a specified accepted amount of error.
public	SimplexSolver(final double Amount of error to accept for algorithm convergence. epsilon, final int Amount of error to accept in floating point comparisons. maxUlps) Builds a simplex solver with a specified accepted amount of error.
public	SimplexSolver(final double Amount of error to accept for algorithm convergence. epsilon, final int Amount of error to accept in floating point comparisons. maxUlps, final double Values smaller than the cutOff are treated as zero. cutOff) Builds a simplex solver with a specified accepted amount of error.

Method Summary

Modifier and Type	Method and Description
protected void	doIteration(final SimplexTableau Simple tableau for the problem. tableau) Runs one iteration of the Simplex method on the given model.
public PointValuePair	doOptimize() Implements abstract org.apache.commons.math3.optim.BaseOptimizer.doOptimize. Performs the bulk of the optimization algorithm.
private Integer	Returns: the column with the most negative coefficient. getPivotColumn(SimplexTableau Simple tableau for the problem. tableau) Returns the column with the most negative coefficient in the objective function row.
private Integer	Returns: the row with the minimum ratio. getPivotRow(SimplexTableau Simplex tableau for the problem. tableau, final int Column to test the ratio of (see `getPivotColumn(SimplexTableau)`). col) Returns the row with the minimum ratio as given by the minimum ratio test (MRT).
private boolean	Returns: `true` if the pivot column is valid, `false` otherwise isValidPivotColumn(SimplexTableau simplex tableau for the problem tableau, int the column to test col) Checks whether the given column is valid pivot column, i.e. will result in a valid pivot row.
public PointValuePair	Returns: a point/value pair that satisfies the convergence criteria. optimize(OptimizationData... Optimization data. In addition to those documented in `LinearOptimizer`, this method will register the following data: `SolutionCallback` `PivotSelectionRule` optData) Overrides org.apache.commons.math3.optim.linear.LinearOptimizer.optimize. Stores data and performs the optimization.
protected void	parseOptimizationData(OptimizationData... Optimization data. In addition to those documented in `LinearOptimizer`, this method will register the following data: `SolutionCallback` `PivotSelectionRule` optData) Overrides org.apache.commons.math3.optim.linear.LinearOptimizer.parseOptimizationData. Scans the list of (required and optional) optimization data that characterize the problem.
protected void	solvePhase1(final SimplexTableau Simple tableau for the problem. tableau) Solves Phase 1 of the Simplex method.

Inherited from org.apache.commons.math3.optim.linear.LinearOptimizer:: getConstraints getFunction isRestrictedToNonNegative

Field Detail

cutOff	back to summary
private final double cutOff Cut-off value for entries in the tableau: values smaller than the cut-off are treated as zero to improve numerical stability.

DEFAULT_CUT_OFF	back to summary
pack-priv static final double DEFAULT_CUT_OFF Default cut-off value.

DEFAULT_EPSILON	back to summary
private static final double DEFAULT_EPSILON Default amount of error to accept for algorithm convergence.

DEFAULT_ULPS	back to summary
pack-priv static final int DEFAULT_ULPS Default amount of error to accept in floating point comparisons (as ulps).

epsilon	back to summary
private final double epsilon Amount of error to accept for algorithm convergence.

maxUlps	back to summary
private final int maxUlps Amount of error to accept in floating point comparisons (as ulps).

pivotSelection	back to summary
private PivotSelectionRule pivotSelection The pivot selection method to use.

solutionCallback	back to summary
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.

Constructor Detail

SimplexSolver	back to summary
public SimplexSolver() Builds a simplex solver with default settings.

SimplexSolver	back to summary
public SimplexSolver(final double epsilon) Builds a simplex solver with a specified accepted amount of error. Parameters epsilon:double Amount of error to accept for algorithm convergence.

SimplexSolver

back to summary

public SimplexSolver(final double epsilon)

Builds a simplex solver with a specified accepted amount of error.

Parameters

epsilon:double: Amount of error to accept for algorithm convergence.

SimplexSolver	back to summary
public SimplexSolver(final double epsilon, final int maxUlps) Builds a simplex solver with a specified accepted amount of error. Parameters epsilon:double Amount of error to accept for algorithm convergence. maxUlps:int Amount of error to accept in floating point comparisons.

SimplexSolver

back to summary

public SimplexSolver(final double epsilon, final int maxUlps)

Builds a simplex solver with a specified accepted amount of error.

Parameters

epsilon:double: Amount of error to accept for algorithm convergence.
maxUlps:int: Amount of error to accept in floating point comparisons.

SimplexSolver	back to summary
public SimplexSolver(final double epsilon, final int maxUlps, final double cutOff) Builds a simplex solver with a specified accepted amount of error. Parameters epsilon:double Amount of error to accept for algorithm convergence. maxUlps:int Amount of error to accept in floating point comparisons. cutOff:double Values smaller than the cutOff are treated as zero.

SimplexSolver

back to summary

public SimplexSolver(final double epsilon, final int maxUlps, final double cutOff)

Builds a simplex solver with a specified accepted amount of error.

Parameters

epsilon:double: Amount of error to accept for algorithm convergence.
maxUlps:int: Amount of error to accept in floating point comparisons.
cutOff:double: Values smaller than the cutOff are treated as zero.

Method Detail

doIteration	back to summary
protected void doIteration(final SimplexTableau tableau) throws TooManyIterationsException, UnboundedSolutionException Runs one iteration of the Simplex method on the given model. Parameters tableau:SimplexTableau Simple tableau for the problem. Exceptions TooManyIterationsException: if the allowed number of iterations has been exhausted. UnboundedSolutionException: if the model is found not to have a bounded solution.

doIteration

back to summary

protected void doIteration(final SimplexTableau tableau) throws TooManyIterationsException, UnboundedSolutionException

Runs one iteration of the Simplex method on the given model.

Parameters

tableau:SimplexTableau: Simple tableau for the problem.

Exceptions

TooManyIterationsException:: if the allowed number of iterations has been exhausted.
UnboundedSolutionException:: if the model is found not to have a bounded solution.

doOptimize	back to summary
public PointValuePair doOptimize() throws TooManyIterationsException, UnboundedSolutionException, NoFeasibleSolutionException Implements abstract org.apache.commons.math3.optim.BaseOptimizer.doOptimize. Doc from org.apache.commons.math3.optim.BaseOptimizer.doOptimize. Performs the bulk of the optimization algorithm. Returns:PointValuePair the point/value pair giving the optimal value of the objective function. Annotations @Override

doOptimize

back to summary

public PointValuePair doOptimize() throws TooManyIterationsException, UnboundedSolutionException, NoFeasibleSolutionException

Implements abstract org.apache.commons.math3.optim.BaseOptimizer.doOptimize.

Doc from org.apache.commons.math3.optim.BaseOptimizer.doOptimize.

Performs the bulk of the optimization algorithm.

Returns:PointValuePair

the point/value pair giving the optimal value of the objective function.

Annotations

@Override

getPivotColumn	back to summary
private Integer getPivotColumn(SimplexTableau tableau) Returns the column with the most negative coefficient in the objective function row. Parameters tableau:SimplexTableau Simple tableau for the problem. Returns:Integer the column with the most negative coefficient.

getPivotColumn

back to summary

private Integer getPivotColumn(SimplexTableau tableau)

Returns the column with the most negative coefficient in the objective function row.

Parameters

tableau:SimplexTableau: Simple tableau for the problem.

Returns:Integer

the column with the most negative coefficient.

getPivotRow back to summary

getPivotRow	back to summary
private Integer getPivotRow(SimplexTableau tableau, final int col) Returns the row with the minimum ratio as given by the minimum ratio test (MRT). Parameters tableau:SimplexTableau Simplex tableau for the problem. col:int Column to test the ratio of (see `getPivotColumn(SimplexTableau)`). Returns:Integer the row with the minimum ratio.

private Integer getPivotRow(SimplexTableau tableau, final int col)

Returns the row with the minimum ratio as given by the minimum ratio test (MRT).

Parameters

tableau:SimplexTableau: Simplex tableau for the problem.
col:int: Column to test the ratio of (see getPivotColumn(SimplexTableau)).

Returns:Integer

the row with the minimum ratio.

isValidPivotColumn back to summary

isValidPivotColumn	back to summary
private boolean isValidPivotColumn(SimplexTableau tableau, int col) 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:SimplexTableau simplex tableau for the problem col:int the column to test Returns:boolean `true` if the pivot column is valid, `false` otherwise

private boolean isValidPivotColumn(SimplexTableau tableau, int col)

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:SimplexTableau: simplex tableau for the problem
col:int: the column to test

Returns:boolean

true if the pivot column is valid, false otherwise

optimize back to summary

optimize	back to summary
public PointValuePair optimize(OptimizationData... optData) throws TooManyIterationsException Overrides org.apache.commons.math3.optim.linear.LinearOptimizer.optimize. Doc from org.apache.commons.math3.optim.linear.LinearOptimizer.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 `parseOptimizationData(OptimizationData[])` if they need to register their own options; but then, they must also call `super.parseOptimizationData(optData)` within that method. Parameters optData:OptimizationData[] Optimization data. In addition to those documented in `LinearOptimizer`, this method will register the following data: `SolutionCallback` `PivotSelectionRule` Returns:PointValuePair a point/value pair that satisfies the convergence criteria. Annotations @Override Exceptions TooManyIterationsException: if the maximal number of iterations is exceeded.

public PointValuePair optimize(OptimizationData... optData) throws TooManyIterationsException

Overrides org.apache.commons.math3.optim.linear.LinearOptimizer.optimize.

Doc from org.apache.commons.math3.optim.linear.LinearOptimizer.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 parseOptimizationData(OptimizationData[]) if they need to register their own options; but then, they must also call super.parseOptimizationData(optData) within that method.

Parameters

optData:OptimizationData[]

Optimization data. In addition to those documented in LinearOptimizer, this method will register the following data:

Returns:PointValuePair

a point/value pair that satisfies the convergence criteria.

Annotations

@Override

Exceptions

TooManyIterationsException:: if the maximal number of iterations is exceeded.

parseOptimizationData back to summary

parseOptimizationData	back to summary
protected void parseOptimizationData(OptimizationData... optData) Overrides org.apache.commons.math3.optim.linear.LinearOptimizer.parseOptimizationData. Doc from org.apache.commons.math3.optim.linear.LinearOptimizer.parseOptimizationData. Scans the list of (required and optional) optimization data that characterize the problem. Parameters optData:OptimizationData[] Optimization data. In addition to those documented in `LinearOptimizer`, this method will register the following data: `SolutionCallback` `PivotSelectionRule` Annotations @Override

protected void parseOptimizationData(OptimizationData... optData)

Overrides org.apache.commons.math3.optim.linear.LinearOptimizer.parseOptimizationData.

Doc from org.apache.commons.math3.optim.linear.LinearOptimizer.parseOptimizationData.

Scans the list of (required and optional) optimization data that characterize the problem.

Parameters

optData:OptimizationData[]

Optimization data. In addition to those documented in LinearOptimizer, this method will register the following data:

Annotations

@Override

solvePhase1	back to summary
protected void solvePhase1(final SimplexTableau tableau) throws TooManyIterationsException, UnboundedSolutionException, NoFeasibleSolutionException Solves Phase 1 of the Simplex method. Parameters tableau:SimplexTableau Simple tableau for the problem. Exceptions 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?

solvePhase1

back to summary

protected void solvePhase1(final SimplexTableau tableau) throws TooManyIterationsException, UnboundedSolutionException, NoFeasibleSolutionException

Solves Phase 1 of the Simplex method.

Parameters

tableau:SimplexTableau: Simple tableau for the problem.

Exceptions

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 Class SimplexSolver

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail