c

scalation.minima

DualSimplex

class DualSimplex extends MinimizerLP

The DualSimplex class solves Linear Programming (LP) problems using a tableau based Dual Simplex Algorithm. It is particularly useful when re-optimizing after a constraint has been added. The algorithm starts with an infeasible super-optimal solution and moves toward (primal) feasibility and optimality.

Given a constraint matrix 'a', limit/RHS vector 'b' and cost vector 'c', find values for the solution/decision vector 'x' that minimize the objective function f(x), while satisfying all of the constraints, i.e.,

minimize f(x) = c x subject to a x <= b, x >= 0

Creates an 'MM-by-NN' simplex tableau with -- [0..M-1, 0..N-1] = a (constraint matrix) -- [0..M-1, N..M+N-1] = s (slack/surplus variable matrix) -- [0..M-1, NN-1] = b (limit/RHS vector) -- [M, 0..NN-2] = c (cost vector)

Linear Supertypes
MinimizerLP, Error, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. DualSimplex
  2. MinimizerLP
  3. Error
  4. AnyRef
  5. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new DualSimplex(a: MatrixD, b: VectorD, c: VectorD, x_B: Array[Int])

    a

    the M-by-N constraint matrix

    b

    the M-length limit/RHS vector (input b_i negative for surplus)

    c

    the N-length cost vector

    x_B

    the indices of the initial basis (e.g., from primal Simplex)

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. val EPSILON: Double
    Attributes
    protected
    Definition Classes
    MinimizerLP
  5. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  6. def check(x: VectoD, y: VectoD, f: Double): Boolean

    Determine whether the current solution is correct.

    Determine whether the current solution is correct.

    x

    the primal solution vector x

    y

    the dual solution vector y

    f

    the minimum value of the objective function

    Definition Classes
    MinimizerLP
  7. val checker: CheckLP
    Definition Classes
    DualSimplexMinimizerLP
  8. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native() @HotSpotIntrinsicCandidate()
  9. def dual: VectorD

    Return the dual solution vector y (cost row (M) under the slack columns).

  10. def entering(k: Int): Int

    Find the best variable x_l to enter the basis given that x_k is leaving the basis.

    Find the best variable x_l to enter the basis given that x_k is leaving the basis. Determine the index of the entering variable corresponding to COLUMN l by selecting the minimum ratio. Return -1 to indicate no such column.

    k

    the variable that is leaving the basis

  11. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  12. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  13. final def flaw(method: String, message: String): Unit
    Definition Classes
    Error
  14. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  15. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  16. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  17. def leaving(): Int

    Find the best variable x_k to leave the basis.

    Find the best variable x_k to leave the basis. Determine the index of the leaving variable corresponding to ROW k by selecting the most negative RHS value. Return -1 to indicate no such row.

  18. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  19. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  20. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  21. def objF(x: VectoD): Double

    Return the value of the objective function f(x) = c x.

    Return the value of the objective function f(x) = c x.

    x

    the coordinate values of the current point

    Definition Classes
    DualSimplexMinimizerLP
  22. def pivot(k: Int, l: Int): Unit

    Pivot on entry (k, l) using Gauss-Jordan elimination to replace variable x_k with x_l in the basis.

    Pivot on entry (k, l) using Gauss-Jordan elimination to replace variable x_k with x_l in the basis.

    k

    the leaving variable (row)

    l

    the entering variable (column)

  23. def primal: VectorD

    Return the primal solution vector x (only the basic variables are non-zero).

  24. def showTableau(iter: Int): Unit

    Show the current tableau.

    Show the current tableau.

    iter

    the number of iterations do far

  25. def solve(): VectorD

    Run the simplex algorithm starting from an initial BFS and iteratively find a non-basic variable to replace a variable in the current basis so long as the objective function improves.

    Run the simplex algorithm starting from an initial BFS and iteratively find a non-basic variable to replace a variable in the current basis so long as the objective function improves. Return the optimal vector x.

    Definition Classes
    DualSimplexMinimizerLP
  26. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  27. def toString(): String

    Convert the current tableau and basis to a string suitable for display.

    Convert the current tableau and basis to a string suitable for display.

    Definition Classes
    DualSimplex → AnyRef → Any
  28. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  29. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native()
  30. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Deprecated Value Members

  1. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] ) @Deprecated
    Deprecated

Inherited from MinimizerLP

Inherited from Error

Inherited from AnyRef

Inherited from Any

Ungrouped