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

java.lang.Object
  org.apache.commons.math.optimization.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:

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

Field Summary

private java.util.List<java.lang.String>	columnLabels The variables each column represents
private java.util.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 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)
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	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.
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

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 in floating point comparisons.

Constructor Detail

SimplexTableau

SimplexTableau(LinearObjectiveFunction f,
               java.util.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 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

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 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 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(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