Top Description Fields Constructors Methods
org.apache.commons.math3.optim.linear

pack-priv Class SimplexTableau

extends Object
implements Serializable
Class Inheritance
All Implemented Interfaces
java.io.Serializable
Imports
java.io.IOException, .ObjectInputStream, .ObjectOutputStream, .Serializable, java.util.ArrayList, .Arrays, .Collection, .HashSet, .List, .Set, .TreeSet, org.apache.commons.math3.linear.Array2DRowRealMatrix, .MatrixUtils, .RealVector, org.apache.commons.math3.optim.nonlinear.scalar.GoalType, org.apache.commons.math3.optim.PointValuePair, org.apache.commons.math3.util.Precision
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

Field Summary

Modifier and TypeField and Description
private int[]
basicRows

Maps rows to their corresponding basic variables.

private int[]
basicVariables

Maps basic variables to row they are basic in.

private final List<String>
columnLabels

The variables each column represents

private final List<LinearConstraint>
constraints

Linear constraints.

private final double
epsilon

Amount of error to accept when checking for optimality.

private final LinearObjectiveFunction
f

Linear objective function.

private final int
maxUlps

Amount of error to accept in floating point comparisons.

private static final String
NEGATIVE_VAR_COLUMN_LABEL

Column label for negative vars.

private int
numArtificialVariables

Number of artificial variables.

private final int
numDecisionVariables

Number of decision variables.

private final int
numSlackVariables

Number of slack variables.

private final boolean
restrictToNonNegative

Whether to restrict the variables to non-negative values.

private static final long
serialVersionUID

Serializable version identifier.

private transient Array2DRowRealMatrix
tableau

Simple tableau.

Constructor Summary

AccessConstructor and Description
pack-priv
SimplexTableau(final LinearObjectiveFunction
Linear objective function.
f, final Collection<LinearConstraint>
Linear constraints.
constraints, final GoalType
Optimization goal: either GoalType#MAXIMIZE or GoalType#MINIMIZE.
goalType, final boolean
Whether to restrict the variables to non-negative values.
restrictToNonNegative, final double
Amount of error to accept when checking for optimality.
epsilon)

Builds a tableau for a linear problem.

pack-priv
SimplexTableau(final LinearObjectiveFunction
linear objective function
f, final Collection<LinearConstraint>
linear constraints
constraints, final GoalType
type of optimization goal: either GoalType#MAXIMIZE or GoalType#MINIMIZE
goalType, final boolean
whether to restrict the variables to non-negative values
restrictToNonNegative, final double
amount of error to accept when checking for optimality
epsilon, final int
amount of error to accept in floating point comparisons
maxUlps)

Build a tableau for a linear problem.

Method Summary

Modifier and TypeMethod and Description
private void
copyArray(final double[]
the source array
src, final double[]
the destination array
dest)

protected Array2DRowRealMatrix

Returns:

created tableau
createTableau(final boolean
if true, goal is to maximize the objective function
maximize)

Create the tableau by itself.

protected void
divideRow(final int
index of the row
dividendRowIndex, final double
value of the divisor
divisor)

Divides one row by a given divisor.

protected void
dropPhase1Objective()

Removes the phase 1 objective function, positive cost non-artificial variables, and the non-basic artificial variables from this tableau.

public boolean
equals(Object
the reference object with which to compare.
other)

Overrides java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

private Integer

Returns:

the row that the variable is basic in, or null if the variable is not basic.
findBasicRow(final int
index of the column
col)

Returns the row in which the given column is basic.

protected final int

Returns:

offset of the first artificial variable
getArtificialVariableOffset()

Get the offset of the first artificial variable.

protected Integer

Returns:

the row that the variable is basic in. null if the column is not basic
getBasicRow(final int
index of the column to check
col)

Checks whether the given column is basic.

protected int

Returns:

the variable that is basic for this row.
getBasicVariable(final int
the index of the row to check
row)

Returns the variable that is basic in this row.

private int

Returns:

number of constraint with the specified relationship
getConstraintTypeCounts(final Relationship
relationship to count
relationship)

Get a count of constraints corresponding to a specified relationship.

protected final double[][]

Returns:

tableau data
getData()

Get the tableau data.

protected final double

Returns:

entry at (row, column)
getEntry(final int
row index
row, final int
column index
column)

Get an entry of the tableau.

protected final int

Returns:

height of the tableau
getHeight()

Get the height of the tableau.

protected static double

Returns:

the -1 times the sum of all coefficients in the given array.
getInvertedCoefficientSum(final RealVector
coefficients to sum
coefficients)

Get the -1 times the sum of all coefficients in the given array.

protected final int

Returns:

number of artificial variables
getNumArtificialVariables()

Get the number of artificial variables.

protected final int

Returns:

number of decision variables
getNumDecisionVariables()

Get the number of decision variables.

protected final int

Returns:

2 for Phase 1. 1 for Phase 2.
getNumObjectiveFunctions()

Get the number of objective functions in this tableau.

protected final int

Returns:

number of slack variables
getNumSlackVariables()

Get the number of slack variables.

protected final int

Returns:

original number of decision variables
getOriginalNumDecisionVariables()

Get the original number of decision variables.

protected final int

Returns:

offset of the right hand side
getRhsOffset()

Get the offset of the right hand side.

protected final double[]

Returns:

the reference to the underlying row data
getRow(int
the row index
row)

Get the row from the tableau.

protected final int

Returns:

offset of the first slack variable
getSlackVariableOffset()

Get the offset of the first slack variable.

protected PointValuePair

Returns:

current solution
getSolution()

Get the current solution.

protected final int

Returns:

width of the tableau
getWidth()

Get the width of the tableau.

public int
hashCode()

Overrides java.lang.Object.hashCode.

Returns a hash code value for this object.

private void
initializeBasicVariables(final int
the column to start
startColumn)

Initializes the basic variable / row mapping.

protected void
initializeColumnLabels()

Initialize the labels for the columns.

pack-priv boolean

Returns:

whether the model has been solved
isOptimal()

Returns whether the problem is at an optimal state.

private LinearConstraint

Returns:

new equation
normalize(final LinearConstraint
reference constraint
constraint)

Get a new equation equivalent to this one with a positive right hand side.

public List<LinearConstraint>

Returns:

new versions of the constraints
normalizeConstraints(Collection<LinearConstraint>
original (not normalized) constraints
originalConstraints)

Get new versions of the constraints which have positive right hand sides.

protected void
performRowOperations(int
the pivot column
pivotCol, int
the pivot row
pivotRow)

Perform the row operations of the simplex algorithm with the selected pivot column and row.

private void
readObject(ObjectInputStream
stream from which the object should be read
ois)

Deserialize the instance.

protected final void
setEntry(final int
row index
row, final int
column index
column, final double
for the entry
value)

Set an entry of the tableau.

protected void
subtractRow(final int
row index
minuendRowIndex, final int
row index
subtrahendRowIndex, final double
multiplication factor
multiplier)

Subtracts a multiple of one row from another.

private void
writeObject(ObjectOutputStream
stream where object should be written
oos)

Serialize the instance.

Inherited from java.lang.Object:
clonefinalizegetClassnotifynotifyAlltoStringwaitwaitwait

Field Detail

basicRowsback to summary
private int[] basicRows

Maps rows to their corresponding basic variables.

basicVariablesback to summary
private int[] basicVariables

Maps basic variables to row they are basic in.

columnLabelsback to summary
private final List<String> columnLabels

The variables each column represents

constraintsback to summary
private final List<LinearConstraint> constraints

Linear constraints.

epsilonback to summary
private final double epsilon

Amount of error to accept when checking for optimality.

fback to summary
private final LinearObjectiveFunction f

Linear objective function.

maxUlpsback to summary
private final int maxUlps

Amount of error to accept in floating point comparisons.

NEGATIVE_VAR_COLUMN_LABELback to summary
private static final String NEGATIVE_VAR_COLUMN_LABEL

Column label for negative vars.

numArtificialVariablesback to summary
private int numArtificialVariables

Number of artificial variables.

numDecisionVariablesback to summary
private final int numDecisionVariables

Number of decision variables.

numSlackVariablesback to summary
private final int numSlackVariables

Number of slack variables.

restrictToNonNegativeback to summary
private final boolean restrictToNonNegative

Whether to restrict the variables to non-negative values.

serialVersionUIDback to summary
private static final long serialVersionUID

Serializable version identifier.

tableauback to summary
private transient Array2DRowRealMatrix tableau

Simple tableau.

Constructor Detail

SimplexTableauback to summary
pack-priv SimplexTableau(final LinearObjectiveFunction f, final Collection<LinearConstraint> constraints, final GoalType goalType, final boolean restrictToNonNegative, final double epsilon)

Builds a tableau for a linear problem.

Parameters
f:LinearObjectiveFunction

Linear objective function.

constraints:Collection<LinearConstraint>

Linear constraints.

goalType:GoalType

Optimization goal: either GoalType#MAXIMIZE or GoalType#MINIMIZE.

restrictToNonNegative:boolean

Whether to restrict the variables to non-negative values.

epsilon:double

Amount of error to accept when checking for optimality.

SimplexTableauback to summary
pack-priv SimplexTableau(final LinearObjectiveFunction f, final Collection<LinearConstraint> constraints, final GoalType goalType, final boolean restrictToNonNegative, final double epsilon, final int maxUlps)

Build a tableau for a linear problem.

Parameters
f:LinearObjectiveFunction

linear objective function

constraints:Collection<LinearConstraint>

linear constraints

goalType:GoalType

type of optimization goal: either GoalType#MAXIMIZE or GoalType#MINIMIZE

restrictToNonNegative:boolean

whether to restrict the variables to non-negative values

epsilon:double

amount of error to accept when checking for optimality

maxUlps:int

amount of error to accept in floating point comparisons

Method Detail

copyArrayback to summary
private void copyArray(final double[] src, final double[] dest)
Parameters
src:double[]

the source array

dest:double[]

the destination array

createTableauback to summary
protected Array2DRowRealMatrix createTableau(final boolean maximize)

Create the tableau by itself.

Parameters
maximize:boolean

if true, goal is to maximize the objective function

Returns:Array2DRowRealMatrix

created tableau

divideRowback to summary
protected void divideRow(final int dividendRowIndex, final double divisor)

Divides one row by a given divisor.

After application of this operation, the following will hold: 

dividendRow = dividendRow / divisor
Parameters
dividendRowIndex:int

index of the row

divisor:double

value of the divisor

dropPhase1Objectiveback to summary
protected void dropPhase1Objective()

Removes the phase 1 objective function, positive cost non-artificial variables, and the non-basic artificial variables from this tableau.

equalsback to summary
public boolean equals(Object other)

Overrides java.lang.Object.equals.

Doc from java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

The equals method implements an equivalence relation on non-null object references:

  • It is reflexive: for any non-null reference value x, x.equals(x) should return true.
  • It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
  • It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
  • It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
  • For any non-null reference value x, x.equals(null) should return false.

An equivalence relation partitions the elements it operates on into equivalence classes; all the members of an equivalence class are equal to each other. Members of an equivalence class are substitutable for each other, at least for some purposes.

Parameters
other:Object

the reference object with which to compare.

Returns:boolean

true if this object is the same as the obj argument; false otherwise.

Annotations
@Override
findBasicRowback to summary
private Integer findBasicRow(final int col)

Returns the row in which the given column is basic.

Parameters
col:int

index of the column

Returns:Integer

the row that the variable is basic in, or null if the variable is not basic.

getArtificialVariableOffsetback to summary
protected final int getArtificialVariableOffset()

Get the offset of the first artificial variable.

Returns:int

offset of the first artificial variable

getBasicRowback to summary
protected Integer getBasicRow(final int col)

Checks whether the given column is basic.

Parameters
col:int

index of the column to check

Returns:Integer

the row that the variable is basic in. null if the column is not basic

getBasicVariableback to summary
protected int getBasicVariable(final int row)

Returns the variable that is basic in this row.

Parameters
row:int

the index of the row to check

Returns:int

the variable that is basic for this row.

getConstraintTypeCountsback to summary
private int getConstraintTypeCounts(final Relationship relationship)

Get a count of constraints corresponding to a specified relationship.

Parameters
relationship:Relationship

relationship to count

Returns:int

number of constraint with the specified relationship

getDataback to summary
protected final double[][] getData()

Get the tableau data.

Returns:double[][]

tableau data

getEntryback to summary
protected final double getEntry(final int row, final int column)

Get an entry of the tableau.

Parameters
row:int

row index

column:int

column index

Returns:double

entry at (row, column)

getHeightback to summary
protected final int getHeight()

Get the height of the tableau.

Returns:int

height of the tableau

getInvertedCoefficientSumback to summary
protected static double getInvertedCoefficientSum(final RealVector coefficients)

Get the -1 times the sum of all coefficients in the given array.

Parameters
coefficients:RealVector

coefficients to sum

Returns:double

the -1 times the sum of all coefficients in the given array.

getNumArtificialVariablesback to summary
protected final int getNumArtificialVariables()

Get the number of artificial variables.

Returns:int

number of artificial variables

getNumDecisionVariablesback to summary
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:int

number of decision variables

See Also
getOriginalNumDecisionVariables()
getNumObjectiveFunctionsback to summary
protected final int getNumObjectiveFunctions()

Get the number of objective functions in this tableau.

Returns:int

2 for Phase 1. 1 for Phase 2.

getNumSlackVariablesback to summary
protected final int getNumSlackVariables()

Get the number of slack variables.

Returns:int

number of slack variables

getOriginalNumDecisionVariablesback to summary
protected final int getOriginalNumDecisionVariables()

Get the original number of decision variables.

Returns:int

original number of decision variables

See Also
getNumDecisionVariables()
getRhsOffsetback to summary
protected final int getRhsOffset()

Get the offset of the right hand side.

Returns:int

offset of the right hand side

getRowback to summary
protected final double[] getRow(int row)

Get the row from the tableau.

Parameters
row:int

the row index

Returns:double[]

the reference to the underlying row data

getSlackVariableOffsetback to summary
protected final int getSlackVariableOffset()

Get the offset of the first slack variable.

Returns:int

offset of the first slack variable

getSolutionback to summary
protected PointValuePair getSolution()

Get the current solution.

Returns:PointValuePair

current solution

getWidthback to summary
protected final int getWidth()

Get the width of the tableau.

Returns:int

width of the tableau

hashCodeback to summary
public int hashCode()

Overrides java.lang.Object.hashCode.

Doc from java.lang.Object.hashCode.

Returns a hash code value for this object. This method is supported for the benefit of hash tables such as those provided by java.util.HashMap.

The general contract of hashCode is:

  • Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
  • If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.
  • It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
Returns:int

a hash code value for this object

Annotations
@Override
initializeBasicVariablesback to summary
private void initializeBasicVariables(final int startColumn)

Initializes the basic variable / row mapping.

Parameters
startColumn:int

the column to start

initializeColumnLabelsback to summary
protected void initializeColumnLabels()

Initialize the labels for the columns.

isOptimalback to summary
pack-priv boolean isOptimal()

Returns whether the problem is at an optimal state.

Returns:boolean

whether the model has been solved

normalizeback to summary
private LinearConstraint normalize(final LinearConstraint constraint)

Get a new equation equivalent to this one with a positive right hand side.

Parameters
constraint:LinearConstraint

reference constraint

Returns:LinearConstraint

new equation

normalizeConstraintsback to summary
public List<LinearConstraint> normalizeConstraints(Collection<LinearConstraint> originalConstraints)

Get new versions of the constraints which have positive right hand sides.

Parameters
originalConstraints:Collection<LinearConstraint>

original (not normalized) constraints

Returns:List<LinearConstraint>

new versions of the constraints

performRowOperationsback to summary
protected void performRowOperations(int pivotCol, int pivotRow)

Perform the row operations of the simplex algorithm with the selected pivot column and row.

Parameters
pivotCol:int

the pivot column

pivotRow:int

the pivot row

readObjectback to summary
private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException

Deserialize the instance.

Parameters
ois:ObjectInputStream

stream from which the object should be read

Exceptions
ClassNotFoundException:
if a class in the stream cannot be found
IOException:
if object cannot be read from the stream
setEntryback to summary
protected final void setEntry(final int row, final int column, final double value)

Set an entry of the tableau.

Parameters
row:int

row index

column:int

column index

value:double

for the entry

subtractRowback to summary
protected void subtractRow(final int minuendRowIndex, final int subtrahendRowIndex, final double multiplier)

Subtracts a multiple of one row from another.

After application of this operation, the following will hold: 

minuendRow = minuendRow - multiple * subtrahendRow
Parameters
minuendRowIndex:int

row index

subtrahendRowIndex:int

row index

multiplier:double

multiplication factor

writeObjectback to summary
private void writeObject(ObjectOutputStream oos) throws IOException

Serialize the instance.

Parameters
oos:ObjectOutputStream

stream where object should be written

Exceptions
IOException:
if object cannot be written to stream