Class SimplexSolver

java.lang.Object

org.apache.commons.math3.optim.BaseOptimizer<PointValuePair>

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
extends LinearOptimizer

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: 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

Fields

Modifier and Type	Field	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.
(package private) 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.
(package private) 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.

Fields inherited from class BaseOptimizer

evaluations, iterations

Constructor Summary

Constructors

Constructor	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.

Method Summary

Modifier and Type	Method	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 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.
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.

Methods inherited from class LinearOptimizer

getConstraints, getFunction, isRestrictedToNonNegative

Methods inherited from class MultivariateOptimizer

computeObjectiveValue, getGoalType

Methods inherited from class BaseMultivariateOptimizer

getLowerBound, getStartPoint, getUpperBound

Methods inherited from class BaseOptimizer

getConvergenceChecker, getEvaluations, getIterations, getMaxEvaluations, getMaxIterations, incrementEvaluationCount, incrementIterationCount, optimize

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

DEFAULT_ULPS

static final int DEFAULT_ULPS

Default amount of error to accept in floating point comparisons (as ulps).

See Also:

• Constant Field Values

DEFAULT_CUT_OFF

static final double DEFAULT_CUT_OFF

Default cut-off value.

See Also:

• Constant Field Values

DEFAULT_EPSILON

private static final double DEFAULT_EPSILON

Default amount of error to accept for algorithm convergence.

See Also:

• Constant Field Values

epsilon

private final double epsilon

Amount of error to accept for algorithm convergence.

maxUlps

private final int maxUlps

Amount of error to accept in floating point comparisons (as ulps).

cutOff

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.

pivotSelection

private PivotSelectionRule pivotSelection

The pivot selection method to use.

solutionCallback

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

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

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 call super.parseOptimizationData(optData) within that method.

Overrides:

optimize in class LinearOptimizer

Parameters:

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

• SolutionCallback
• PivotSelectionRule

Returns:

a point/value pair that satisfies the convergence criteria.

Throws:

TooManyIterationsException - if the maximal number of iterations is exceeded.

parseOptimizationData

protected void parseOptimizationData(OptimizationData... optData)

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

Overrides:

parseOptimizationData in class LinearOptimizer

Parameters:

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

• SolutionCallback
• PivotSelectionRule

getPivotColumn

private Integer getPivotColumn(SimplexTableau tableau)

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

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 - simplex tableau for the problem

col - the column to test

Returns:

true if the pivot column is valid, false otherwise

getPivotRow

private Integer getPivotRow(SimplexTableau tableau,
 int col)

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 (see getPivotColumn(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,
NoFeasibleSolutionException

Performs the bulk of the optimization algorithm.

Specified by:

doOptimize in class BaseOptimizer<PointValuePair>

Returns:

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

Throws:

TooManyIterationsException

UnboundedSolutionException

NoFeasibleSolutionException