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.

Since:
2.0
Version:
$Id: SimplexSolver.java 1416643 2012-12-03 19:37:14Z tn $

Field Summary
private static double DEFAULT_EPSILON
          Default amount of error to accept for algorithm convergence.
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, int maxUlps)
          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  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.
 
Methods inherited from class org.apache.commons.math3.optim.linear.LinearOptimizer
getConstraints, getFunction, isRestrictedToNonNegative, optimize
 
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

DEFAULT_EPSILON

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

See Also:
Constant Field Values

DEFAULT_ULPS

private static final int DEFAULT_ULPS
Default amount of error to accept in floating point comparisons (as ulps).

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

Constructor Detail

SimplexSolver

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


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.
Method Detail

getPivotColumn

private java.lang.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.

getPivotRow

private java.lang.Integer getPivotRow(SimplexTableau tableau,
                                      int col)
Returns the row with the minimum ratio as given by the minimum ratio test (MRT).

Parameters:
tableau - Simple 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


Copyright (c) 2003-2013 Apache Software Foundation