org.apache.commons.math3.optim.linear
Class SimplexSolver

java.lang.Object
  extended by org.apache.commons.math3.optim.BaseOptimizer<PAIR>
      extended by org.apache.commons.math3.optim.BaseMultivariateOptimizer<PointValuePair>
          extended by org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer
              extended by org.apache.commons.math3.optim.linear.LinearOptimizer
                  extended by org.apache.commons.math3.optim.linear.SimplexSolver

public class SimplexSolver
extends LinearOptimizer

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.

Since:
2.0
Version:
$Id: SimplexSolver.java 1462503 2013-03-29 15:48:27Z luc $

Field Summary
 
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(org.apache.commons.math3.optim.linear.SimplexTableau tableau)
          Runs one iteration of the Simplex method on the given model.
 PointValuePair doOptimize()
          Performs the bulk of the optimization algorithm.
protected  void solvePhase1(org.apache.commons.math3.optim.linear.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
 

Constructor Detail

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 Detail

doIteration

protected void doIteration(org.apache.commons.math3.optim.linear.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(org.apache.commons.math3.optim.linear.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


Copyright © 2003-2013 The Apache Software Foundation. All Rights Reserved.