org.apache.commons.math.optimization.linear
Class SimplexSolver

java.lang.Object
  extended by org.apache.commons.math.optimization.linear.AbstractLinearOptimizer
      extended by org.apache.commons.math.optimization.linear.SimplexSolver
All Implemented Interfaces:
LinearOptimizer

public class SimplexSolver
extends AbstractLinearOptimizer

Solves a linear problem using the Two-Phase Simplex Method.

Since:
2.0
Version:
$Revision: 797801 $ $Date: 2009-07-25 13:22:06 -0400 (Sat, 25 Jul 2009) $

Field Summary
private static double DEFAULT_EPSILON
          Default amount of error to accept in floating point comparisons.
protected  double epsilon
          Amount of error to accept in floating point comparisons.
 
Fields inherited from class org.apache.commons.math.optimization.linear.AbstractLinearOptimizer
constraints, DEFAULT_MAX_ITERATIONS, f, goalType, restrictToNonNegative
 
Constructor Summary
SimplexSolver()
          Build a simplex solver with default settings.
SimplexSolver(double epsilon)
          Build 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.
 RealPointValuePair doOptimize()
          Perform the bulk of optimization algorithm.
private  Integer getPivotColumn(SimplexTableau tableau)
          Returns the column with the most negative coefficient in the objective function row.
private  Integer getPivotRow(int col, SimplexTableau tableau)
          Returns the row with the minimum ratio as given by the minimum ratio test (MRT).
 boolean isOptimal(SimplexTableau tableau)
          Returns whether the problem is at an optimal state.
private  boolean isPhase1Solved(SimplexTableau tableau)
          Checks whether Phase 1 is solved.
protected  void solvePhase1(SimplexTableau tableau)
          Solves Phase 1 of the Simplex method.
 
Methods inherited from class org.apache.commons.math.optimization.linear.AbstractLinearOptimizer
getIterations, getMaxIterations, incrementIterationsCounter, optimize, setMaxIterations
 
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 in floating point comparisons.

See Also:
Constant Field Values

epsilon

protected final double epsilon
Amount of error to accept in floating point comparisons.

Constructor Detail

SimplexSolver

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


SimplexSolver

public SimplexSolver(double epsilon)
Build a simplex solver with a specified accepted amount of error

Parameters:
epsilon - the amount of error to accept in floating point comparisons
Method Detail

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:
column with the most negative coefficient

getPivotRow

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

Parameters:
tableau - simple tableau for the problem
col - the column to test the ratio of. See getPivotColumn(SimplexTableau)
Returns:
row with the minimum ratio

doIteration

protected void doIteration(SimplexTableau tableau)
                    throws OptimizationException
Runs one iteration of the Simplex method on the given model.

Parameters:
tableau - simple tableau for the problem
Throws:
OptimizationException - if the maximal iteration count has been exceeded or if the model is found not to have a bounded solution

isPhase1Solved

private boolean isPhase1Solved(SimplexTableau tableau)
Checks whether Phase 1 is solved.

Parameters:
tableau - simple tableau for the problem
Returns:
whether Phase 1 is solved

isOptimal

public boolean isOptimal(SimplexTableau tableau)
Returns whether the problem is at an optimal state.

Parameters:
tableau - simple tableau for the problem
Returns:
whether the model has been solved

solvePhase1

protected void solvePhase1(SimplexTableau tableau)
                    throws OptimizationException
Solves Phase 1 of the Simplex method.

Parameters:
tableau - simple tableau for the problem
Throws:
OptimizationException - if the maximal number of iterations is exceeded, or if the problem is found not to have a bounded solution, or if there is no feasible solution

doOptimize

public RealPointValuePair doOptimize()
                              throws OptimizationException
Perform the bulk of optimization algorithm.

Specified by:
doOptimize in class AbstractLinearOptimizer
Returns:
the point/value pair giving the optimal value for objective function
Throws:
OptimizationException - if no solution fulfilling the constraints can be found in the allowed number of iterations


Copyright (c) 2003-2010 Apache Software Foundation