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

java.lang.Object
  extended by org.apache.commons.math3.optim.linear.SimplexTableau
All Implemented Interfaces:
java.io.Serializable

 class SimplexTableau
extends java.lang.Object
implements java.io.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:
$Id: SimplexTableau.java 1416643 2012-12-03 19:37:14Z tn $

Field Summary
private  java.util.List<java.lang.String> columnLabels
          The variables each column represents
private  java.util.List<LinearConstraint> constraints
          Linear constraints.
private static double CUTOFF_THRESHOLD
          The cut-off threshold to zero-out entries.
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 when checking for optimality.
private  LinearObjectiveFunction f
          Linear objective function.
private  int maxUlps
          Amount of error to accept in floating point comparisons.
private static java.lang.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, java.util.Collection<LinearConstraint> constraints, GoalType goalType, boolean restrictToNonNegative, double epsilon)
          Builds a tableau for a linear problem.
SimplexTableau(LinearObjectiveFunction f, java.util.Collection<LinearConstraint> constraints, GoalType goalType, boolean restrictToNonNegative, double epsilon, int maxUlps)
          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(java.lang.Object other)
           
protected  int getArtificialVariableOffset()
          Get the offset of the first artificial variable.
protected  java.lang.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 getInvertedCoefficientSum(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  PointValuePair 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.
 java.util.List<LinearConstraint> normalizeConstraints(java.util.Collection<LinearConstraint> originalConstraints)
          Get new versions of the constraints which have positive right hand sides.
private  void readObject(java.io.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(java.io.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 java.lang.String NEGATIVE_VAR_COLUMN_LABEL
Column label for negative vars.

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

CUTOFF_THRESHOLD

private static final double CUTOFF_THRESHOLD
The cut-off threshold to zero-out entries.

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 java.util.List<LinearConstraint> constraints
Linear constraints.


restrictToNonNegative

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


columnLabels

private final java.util.List<java.lang.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 when checking for optimality.


maxUlps

private final int maxUlps
Amount of error to accept in floating point comparisons.

Constructor Detail

SimplexTableau

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

Parameters:
f - Linear objective function.
constraints - Linear constraints.
goalType - Optimization goal: either GoalType.MAXIMIZE or GoalType.MINIMIZE.
restrictToNonNegative - Whether to restrict the variables to non-negative values.
epsilon - Amount of error to accept when checking for optimality.

SimplexTableau

SimplexTableau(LinearObjectiveFunction f,
               java.util.Collection<LinearConstraint> constraints,
               GoalType goalType,
               boolean restrictToNonNegative,
               double epsilon,
               int maxUlps)
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 when checking for optimality
maxUlps - 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 java.util.List<LinearConstraint> normalizeConstraints(java.util.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

getInvertedCoefficientSum

protected static double getInvertedCoefficientSum(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 java.lang.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 PointValuePair 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(java.lang.Object other)
Overrides:
equals in class java.lang.Object

hashCode

public int hashCode()
Overrides:
hashCode in class java.lang.Object

writeObject

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

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

readObject

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

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


Copyright (c) 2003-2013 Apache Software Foundation