Class SimplexTableau
- java.lang.Object
-
- 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
-
-
Field Summary
Fields Modifier and Type Field Description private int[]
basicRows
Maps rows to their corresponding basic variables.private int[]
basicVariables
Maps basic variables to row they are basic in.private java.util.List<java.lang.String>
columnLabels
The variables each column representsprivate java.util.List<LinearConstraint>
constraints
Linear constraints.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 Array2DRowRealMatrix
tableau
Simple tableau.
-
Constructor Summary
Constructors Constructor Description 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
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
copyArray(double[] src, double[] dest)
protected Array2DRowRealMatrix
createTableau(boolean maximize)
Create the tableau by itself.protected void
divideRow(int dividendRowIndex, double 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.boolean
equals(java.lang.Object other)
private java.lang.Integer
findBasicRow(int col)
Returns the row in which the given column is basic.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.protected int
getBasicVariable(int row)
Returns the variable that is basic in this row.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 double[]
getRow(int row)
Get the row from the tableau.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()
private void
initializeBasicVariables(int startColumn)
Initializes the basic variable / row mapping.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.protected void
performRowOperations(int pivotCol, int pivotRow)
Perform the row operations of the simplex algorithm with the selected pivot column and row.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 minuendRowIndex, int subtrahendRowIndex, double multiplier)
Subtracts a multiple of one row from another.private void
writeObject(java.io.ObjectOutputStream oos)
Serialize the instance.
-
-
-
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 Array2DRowRealMatrix 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.
-
basicVariables
private int[] basicVariables
Maps basic variables to row they are basic in.
-
basicRows
private int[] basicRows
Maps rows to their corresponding basic variables.
-
-
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: eitherGoalType.MAXIMIZE
orGoalType.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 functionconstraints
- linear constraintsgoalType
- type of optimization goal: eitherGoalType.MAXIMIZE
orGoalType.MINIMIZE
restrictToNonNegative
- whether to restrict the variables to non-negative valuesepsilon
- amount of error to accept when checking for optimalitymaxUlps
- amount of error to accept in floating point comparisons
-
-
Method Detail
-
initializeColumnLabels
protected void initializeColumnLabels()
Initialize the labels for the columns.
-
createTableau
protected Array2DRowRealMatrix 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
-
getBasicVariable
protected int getBasicVariable(int row)
Returns the variable that is basic in this row.- Parameters:
row
- the index of the row to check- Returns:
- the variable that is basic for this row.
-
initializeBasicVariables
private void initializeBasicVariables(int startColumn)
Initializes the basic variable / row mapping.- Parameters:
startColumn
- the column to start
-
findBasicRow
private java.lang.Integer findBasicRow(int col)
Returns the row in which the given column is basic.- Parameters:
col
- index of the column- Returns:
- the row that the variable is basic in, or
null
if the variable 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 arraydest
- 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
-
performRowOperations
protected void performRowOperations(int pivotCol, int pivotRow)
Perform the row operations of the simplex algorithm with the selected pivot column and row.- Parameters:
pivotCol
- the pivot columnpivotRow
- the pivot row
-
divideRow
protected void divideRow(int dividendRowIndex, double divisor)
Divides one row by a given divisor.After application of this operation, the following will hold:
dividendRow = dividendRow / divisor
- Parameters:
dividendRowIndex
- index of the rowdivisor
- value of the divisor
-
subtractRow
protected void subtractRow(int minuendRowIndex, int subtrahendRowIndex, 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
- row indexsubtrahendRowIndex
- row indexmultiplier
- 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 indexcolumn
- 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 indexcolumn
- column indexvalue
- 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
-
getRow
protected final double[] getRow(int row)
Get the row from the tableau.- Parameters:
row
- the row index- Returns:
- the reference to the underlying row data
-
getData
protected final double[][] getData()
Get the tableau data.- Returns:
- tableau data
-
equals
public boolean equals(java.lang.Object other)
- Overrides:
equals
in classjava.lang.Object
-
hashCode
public int hashCode()
- Overrides:
hashCode
in classjava.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 foundjava.io.IOException
- if object cannot be read from the stream
-
-