Package org.apache.commons.math3.optim.linear

Class SimplexTableau

java.lang.Object
org.apache.commons.math3.optim.linear.SimplexTableau
All Implemented Interfaces:
Serializable
class SimplexTableau extends Object implements 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 Details

    • NEGATIVE_VAR_COLUMN_LABEL

      private static final String NEGATIVE_VAR_COLUMN_LABEL
      Column label for negative vars.
      See Also:

    • serialVersionUID

      private static final long serialVersionUID
      Serializable version identifier.
      See Also:

    • f

      private final LinearObjectiveFunction f
      Linear objective function.

    • constraints

      private final List<LinearConstraint> constraints
      Linear constraints.

    • restrictToNonNegative

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

    • columnLabels

      private final List<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 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: 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, 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 Details

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

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

    • 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 column
      pivotRow - 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 row
      divisor - 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 index
      subtrahendRowIndex - row index
      multiplier - 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

      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

      public boolean equals(Object other)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • writeObject

      private void writeObject(ObjectOutputStream oos) throws IOException
      Serialize the instance.
      Parameters:
      oos - stream where object should be written
      Throws:
      IOException - if object cannot be written to stream

    • readObject

      private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException
      Deserialize the instance.
      Parameters:
      ois - stream from which the object should be read
      Throws:
      ClassNotFoundException - if a class in the stream cannot be found
      IOException - if object cannot be read from the stream