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

java.lang.Object
  extended by org.apache.commons.math.optimization.linear.SimplexTableau
All Implemented Interfaces:
Serializable

 class SimplexTableau
extends Object
implements Serializable

A tableau for use in the Simplex method.

Example:

   W |  Z |  x1 |  x2 |  x- | s1 |  s2 |  a1 |  RHS
 ---------------------------------------------------
  -1    0    0     0     0     0     0     1     0   <= phase 1 objective
   0    1   -15   -10    0     0     0     0     0   <= phase 2 objective
   0    0    1     0     0     1     0     0     2   <= constraint 1
   0    0    0     1     0     0     1     0     3   <= constraint 2
   0    0    1     1     0     0     0     1     4   <= constraint 3
 
W: Phase 1 objective function
Z: Phase 2 objective function
x1 & x2: Decision variables
x-: Extra decision variable to allow for negative values
s1 & s2: Slack/Surplus variables
a1: Artificial variable
RHS: Right hand side

Since:
2.0
Version:
$Revision: 922713 $ $Date: 2010-03-14 02:26:13 +0100 (dim. 14 mars 2010) $

Field Summary
private  List<String> columnLabels
          The variables each column represents
private  List<LinearConstraint> constraints
          Linear constraints.
private  double epsilon
          Amount of error to accept in floating point comparisons.
private  LinearObjectiveFunction f
          Linear objective function.
private static String NEGATIVE_VAR_COLUMN_LABEL
          Column label for negative vars.
private  int numArtificialVariables
          Number of artificial variables.
private  int numDecisionVariables
          Number of decision variables.
private  int numSlackVariables
          Number of slack variables.
private  boolean restrictToNonNegative
          Whether to restrict the variables to non-negative values.
private static long serialVersionUID
          Serializable version identifier.
private  RealMatrix tableau
          Simple tableau.
 
Constructor Summary
SimplexTableau(LinearObjectiveFunction f, Collection<LinearConstraint> constraints, GoalType goalType, boolean restrictToNonNegative, double epsilon)
          Build a tableau for a linear problem.
 
Method Summary
private  void copyArray(double[] src, double[] dest)
           
protected  RealMatrix createTableau(boolean maximize)
          Create the tableau by itself.
protected  void divideRow(int dividendRow, double divisor)
          Subtracts a multiple of one row from another.
protected  void dropPhase1Objective()
          Removes the phase 1 objective function, positive cost non-artificial variables, and the non-basic artificial variables from this tableau.
 boolean equals(Object other)
          
protected  int getArtificialVariableOffset()
          Get the offset of the first artificial variable.
protected  Integer getBasicRow(int col)
          Checks whether the given column is basic.
private  int getConstraintTypeCounts(Relationship relationship)
          Get a count of constraints corresponding to a specified relationship.
protected  double[][] getData()
          Get the tableau data.
protected  double getEntry(int row, int column)
          Get an entry of the tableau.
protected  int getHeight()
          Get the height of the tableau.
protected static double getInvertedCoeffiecientSum(RealVector coefficients)
          Get the -1 times the sum of all coefficients in the given array.
protected  int getNumArtificialVariables()
          Get the number of artificial variables.
protected  int getNumDecisionVariables()
          Get the number of decision variables.
protected  int getNumObjectiveFunctions()
          Get the number of objective functions in this tableau.
protected  int getNumSlackVariables()
          Get the number of slack variables.
protected  int getOriginalNumDecisionVariables()
          Get the original number of decision variables.
protected  int getRhsOffset()
          Get the offset of the right hand side.
protected  int getSlackVariableOffset()
          Get the offset of the first slack variable.
protected  RealPointValuePair getSolution()
          Get the current solution.
protected  int getWidth()
          Get the width of the tableau.
 int hashCode()
          
protected  void initializeColumnLabels()
          Initialize the labels for the columns.
(package private)  boolean isOptimal()
          Returns whether the problem is at an optimal state.
private  LinearConstraint normalize(LinearConstraint constraint)
          Get a new equation equivalent to this one with a positive right hand side.
 List<LinearConstraint> normalizeConstraints(Collection<LinearConstraint> originalConstraints)
          Get new versions of the constraints which have positive right hand sides.
private  void readObject(ObjectInputStream ois)
          Deserialize the instance.
protected  void setEntry(int row, int column, double value)
          Set an entry of the tableau.
protected  void subtractRow(int minuendRow, int subtrahendRow, double multiple)
          Subtracts a multiple of one row from another.
private  void writeObject(ObjectOutputStream oos)
          Serialize the instance.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

NEGATIVE_VAR_COLUMN_LABEL

private static final String NEGATIVE_VAR_COLUMN_LABEL
Column label for negative vars.

See Also:
Constant Field Values

serialVersionUID

private static final long serialVersionUID
Serializable version identifier.

See Also:
Constant Field Values

f

private final LinearObjectiveFunction f
Linear objective function.


constraints

private final List<LinearConstraint> constraints
Linear constraints.


restrictToNonNegative

private final boolean restrictToNonNegative
Whether to restrict the variables to non-negative values.


columnLabels

private final List<String> columnLabels
The variables each column represents


tableau

private transient RealMatrix tableau
Simple tableau.


numDecisionVariables

private final int numDecisionVariables
Number of decision variables.


numSlackVariables

private final int numSlackVariables
Number of slack variables.


numArtificialVariables

private int numArtificialVariables
Number of artificial variables.


epsilon

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

Constructor Detail

SimplexTableau

SimplexTableau(LinearObjectiveFunction f,
               Collection<LinearConstraint> constraints,
               GoalType goalType,
               boolean restrictToNonNegative,
               double epsilon)
Build a tableau for a linear problem.

Parameters:
f - linear objective function
constraints - linear constraints
goalType - type of optimization goal: either GoalType.MAXIMIZE or GoalType.MINIMIZE
restrictToNonNegative - whether to restrict the variables to non-negative values
epsilon - amount of error to accept in floating point comparisons
Method Detail

initializeColumnLabels

protected void initializeColumnLabels()
Initialize the labels for the columns.


createTableau

protected RealMatrix createTableau(boolean maximize)
Create the tableau by itself.

Parameters:
maximize - if true, goal is to maximize the objective function
Returns:
created tableau

normalizeConstraints

public List<LinearConstraint> normalizeConstraints(Collection<LinearConstraint> originalConstraints)
Get new versions of the constraints which have positive right hand sides.

Parameters:
originalConstraints - original (not normalized) constraints
Returns:
new versions of the constraints

normalize

private LinearConstraint normalize(LinearConstraint constraint)
Get a new equation equivalent to this one with a positive right hand side.

Parameters:
constraint - reference constraint
Returns:
new equation

getNumObjectiveFunctions

protected final int getNumObjectiveFunctions()
Get the number of objective functions in this tableau.

Returns:
2 for Phase 1. 1 for Phase 2.

getConstraintTypeCounts

private int getConstraintTypeCounts(Relationship relationship)
Get a count of constraints corresponding to a specified relationship.

Parameters:
relationship - relationship to count
Returns:
number of constraint with the specified relationship

getInvertedCoeffiecientSum

protected static double getInvertedCoeffiecientSum(RealVector coefficients)
Get the -1 times the sum of all coefficients in the given array.

Parameters:
coefficients - coefficients to sum
Returns:
the -1 times the sum of all coefficients in the given array.

getBasicRow

protected Integer getBasicRow(int col)
Checks whether the given column is basic.

Parameters:
col - index of the column to check
Returns:
the row that the variable is basic in. null if the column is not basic

dropPhase1Objective

protected void dropPhase1Objective()
Removes the phase 1 objective function, positive cost non-artificial variables, and the non-basic artificial variables from this tableau.


copyArray

private void copyArray(double[] src,
                       double[] dest)
Parameters:
src - the source array
dest - the destination array

isOptimal

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

Returns:
whether the model has been solved

getSolution

protected RealPointValuePair getSolution()
Get the current solution.

Returns:
current solution

divideRow

protected void divideRow(int dividendRow,
                         double divisor)
Subtracts a multiple of one row from another.

After application of this operation, the following will hold: minuendRow = minuendRow - multiple * subtrahendRow

Parameters:
dividendRow - index of the row
divisor - value of the divisor

subtractRow

protected void subtractRow(int minuendRow,
                           int subtrahendRow,
                           double multiple)
Subtracts a multiple of one row from another.

After application of this operation, the following will hold: minuendRow = minuendRow - multiple * subtrahendRow

Parameters:
minuendRow - row index
subtrahendRow - row index
multiple - multiplication factor

getWidth

protected final int getWidth()
Get the width of the tableau.

Returns:
width of the tableau

getHeight

protected final int getHeight()
Get the height of the tableau.

Returns:
height of the tableau

getEntry

protected final double getEntry(int row,
                                int column)
Get an entry of the tableau.

Parameters:
row - row index
column - column index
Returns:
entry at (row, column)

setEntry

protected final void setEntry(int row,
                              int column,
                              double value)
Set an entry of the tableau.

Parameters:
row - row index
column - column index
value - for the entry

getSlackVariableOffset

protected final int getSlackVariableOffset()
Get the offset of the first slack variable.

Returns:
offset of the first slack variable

getArtificialVariableOffset

protected final int getArtificialVariableOffset()
Get the offset of the first artificial variable.

Returns:
offset of the first artificial variable

getRhsOffset

protected final int getRhsOffset()
Get the offset of the right hand side.

Returns:
offset of the right hand side

getNumDecisionVariables

protected final int getNumDecisionVariables()
Get the number of decision variables.

If variables are not restricted to positive values, this will include 1 extra decision variable to represent the absolute value of the most negative variable.

Returns:
number of decision variables
See Also:
getOriginalNumDecisionVariables()

getOriginalNumDecisionVariables

protected final int getOriginalNumDecisionVariables()
Get the original number of decision variables.

Returns:
original number of decision variables
See Also:
getNumDecisionVariables()

getNumSlackVariables

protected final int getNumSlackVariables()
Get the number of slack variables.

Returns:
number of slack variables

getNumArtificialVariables

protected final int getNumArtificialVariables()
Get the number of artificial variables.

Returns:
number of artificial variables

getData

protected final double[][] getData()
Get the tableau data.

Returns:
tableau data

equals

public boolean equals(Object other)

Overrides:
equals in class Object

hashCode

public int hashCode()

Overrides:
hashCode in class Object

writeObject

private void writeObject(ObjectOutputStream oos)
                  throws IOException
Serialize the instance.

Parameters:
oos - stream where object should be written
Throws:
IOException - if object cannot be written to stream

readObject

private void readObject(ObjectInputStream ois)
                 throws ClassNotFoundException,
                        IOException
Deserialize the instance.

Parameters:
ois - stream from which the object should be read
Throws:
ClassNotFoundException - if a class in the stream cannot be found
IOException - if object cannot be read from the stream


Copyright (c) 2003-2011 Apache Software Foundation