class SimplexBG extends MinimizerLP

The SimplexBG class solves Linear Programming (LP) problems using the Bartels-Golub (BG) Simplex Algorithm. Given a constraint matrix 'a', constant 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

The BG Simplex Algorithm performs LU Factorization/Decomposition of the basis-matrix ('ba' = 'B') rather than computing inverses ('b_inv'). It has benefits over the (Revised) Simplex Algorithm (less run-time, less memory, and much reduced chance of round off errors).

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

Instance Constructors

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

    a

    the constraint matrix

    b

    the constant/limit vector

    c

    the cost/revenue vector

    x_B

    the initial basis (set of indices where x_i is in the basis)

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
    SimplexBGMinimizerLP
  8. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @native() @HotSpotIntrinsicCandidate()
  9. def dual: VectoD

    Return the dual solution vector (y).

  10. def entering(): Int

    Find the best variable x_l to enter the basis.

    Find the best variable x_l to enter the basis. Use Dantiz's Rule: index of max positive (cycling possible) z value. Return -1 to indicate no such column.

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

    Determine whether the current solution (x = primal) is still primal feasible.

  17. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  18. def leaving(l: Int): Int

    Find the best variable x_k to leave the basis given that x_l is entering.

    Find the best variable x_k to leave the basis given that x_l is entering. Determine the index of the leaving variable corresponding to ROW k using the Min-Ratio Rule. Return -1 to indicate no such row.

    l

    the variable chosen to enter the basis

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

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

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

    x

    the primal solution vector

    Definition Classes
    SimplexBGMinimizerLP
  23. def pivot(k: Int, l: Int): Unit

    Pivot by replacing x_k with x_l in the basis.

    Pivot by replacing x_k with x_l in the basis. Update b_inv (actually lu), b_ and c_.

    k

    the leaving variable

    l

    the entering variable

  24. def primal: VectoD

    Return the primal (basis only) solution vector (x).

  25. def primalFull(x: VectoD): VectorD

    Return the full primal solution vector (xx).

  26. def setBasis(j: Int = N-M, l: Int = M): Array[Int]

    There are M+N variables, N decision and M slack variables, of which, for each iteration, M are chosen for a Basic Feasible Solution (BFS).

    There are M+N variables, N decision and M slack variables, of which, for each iteration, M are chosen for a Basic Feasible Solution (BFS). The the variables not in the basis are set to zero. Setting j to N will start with the slack variables in the basis (only works if b >= 0).

    j

    the offset to start the basis

    l

    the size of the basis

  27. def showTableau(iter: Int): Unit

    Show the current BG tableau.

    Show the current BG tableau.

    iter

    the number of iterations do far

  28. def solve(): VectoD

    Solve a Linear Programming (LP) problem using the BG Simplex Algorithm.

    Solve a Linear Programming (LP) problem using the BG Simplex Algorithm. Iteratively pivot until there an optimal solution is found or it is determined that the solution is unbounded. Return the optimal vector x.

    Definition Classes
    SimplexBGMinimizerLP
  29. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  30. def toString(): String

    Convert the current BG tableau (basis, b_inv, b_, and c_) to a string.

    Convert the current BG tableau (basis, b_inv, b_, and c_) to a string.

    Definition Classes
    SimplexBG → AnyRef → Any
  31. def unbounded(u: VectoD): Boolean

    Check if u <= 0., the solution is unbounded.

    Check if u <= 0., the solution is unbounded.

    u

    the vector for leaving

  32. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  33. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()
  34. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  35. var x_B: Array[Int]

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