Class 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 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
      • 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
      • 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: 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,
                       java.util.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 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 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()
      • 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 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