Class SimplexTableau
java.lang.Object
org.apache.commons.math3.optim.linear.SimplexTableau
- All Implemented Interfaces:
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 3W: 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
FieldsModifier and TypeFieldDescriptionprivate int[]
Maps rows to their corresponding basic variables.private int[]
Maps basic variables to row they are basic in.The variables each column representsprivate final List
<LinearConstraint> Linear constraints.private final double
Amount of error to accept when checking for optimality.private final LinearObjectiveFunction
Linear objective function.private final int
Amount of error to accept in floating point comparisons.private static final String
Column label for negative vars.private int
Number of artificial variables.private final int
Number of decision variables.private final int
Number of slack variables.private final boolean
Whether to restrict the variables to non-negative values.private static final long
Serializable version identifier.private Array2DRowRealMatrix
Simple tableau. -
Constructor Summary
ConstructorsConstructorDescriptionSimplexTableau
(LinearObjectiveFunction f, Collection<LinearConstraint> constraints, GoalType goalType, boolean restrictToNonNegative, double epsilon) Builds a tableau for a linear problem.SimplexTableau
(LinearObjectiveFunction f, Collection<LinearConstraint> constraints, GoalType goalType, boolean restrictToNonNegative, double epsilon, int maxUlps) Build a tableau for a linear problem. -
Method Summary
Modifier and TypeMethodDescriptionprivate 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
Removes the phase 1 objective function, positive cost non-artificial variables, and the non-basic artificial variables from this tableau.boolean
private Integer
findBasicRow
(int col) Returns the row in which the given column is basic.protected final int
Get the offset of the first artificial variable.protected 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 final double[][]
getData()
Get the tableau data.protected final double
getEntry
(int row, int column) Get an entry of the tableau.protected final int
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 final int
Get the number of artificial variables.protected final int
Get the number of decision variables.protected final int
Get the number of objective functions in this tableau.protected final int
Get the number of slack variables.protected final int
Get the original number of decision variables.protected final int
Get the offset of the right hand side.protected final double[]
getRow
(int row) Get the row from the tableau.protected final int
Get the offset of the first slack variable.protected PointValuePair
Get the current solution.protected final int
getWidth()
Get the width of the tableau.int
hashCode()
private void
initializeBasicVariables
(int startColumn) Initializes the basic variable / row mapping.protected void
Initialize the labels for the columns.(package private) boolean
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.normalizeConstraints
(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
Deserialize the instance.protected final 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
Serialize the instance.
-
Field Details
-
NEGATIVE_VAR_COLUMN_LABEL
Column label for negative vars.- See Also:
-
serialVersionUID
private static final long serialVersionUIDSerializable version identifier.- See Also:
-
f
Linear objective function. -
constraints
Linear constraints. -
restrictToNonNegative
private final boolean restrictToNonNegativeWhether to restrict the variables to non-negative values. -
columnLabels
The variables each column represents -
tableau
Simple tableau. -
numDecisionVariables
private final int numDecisionVariablesNumber of decision variables. -
numSlackVariables
private final int numSlackVariablesNumber of slack variables. -
numArtificialVariables
private int numArtificialVariablesNumber of artificial variables. -
epsilon
private final double epsilonAmount of error to accept when checking for optimality. -
maxUlps
private final int maxUlpsAmount of error to accept in floating point comparisons. -
basicVariables
private int[] basicVariablesMaps basic variables to row they are basic in. -
basicRows
private int[] basicRowsMaps rows to their corresponding basic variables.
-
-
Constructor Details
-
SimplexTableau
SimplexTableau(LinearObjectiveFunction f, 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, 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 Details
-
initializeColumnLabels
protected void initializeColumnLabels()Initialize the labels for the columns. -
createTableau
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
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
Get a count of constraints corresponding to a specified relationship.- Parameters:
relationship
- relationship to count- Returns:
- number of constraint with the specified relationship
-
getInvertedCoefficientSum
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
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
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
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
protected final int getOriginalNumDecisionVariables()Get the original number of decision variables.- Returns:
- original number of decision variables
- See Also:
-
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
-
hashCode
public int hashCode() -
writeObject
Serialize the instance.- Parameters:
oos
- stream where object should be written- Throws:
IOException
- if object cannot be written to stream
-
readObject
Deserialize the instance.- Parameters:
ois
- stream from which the object should be read- Throws:
ClassNotFoundException
- if a class in the stream cannot be foundIOException
- if object cannot be read from the stream
-