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).
- Alphabetic
- By Inheritance
- SimplexBG
- MinimizerLP
- Error
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Instance Constructors
- 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
- final def !=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def ##: Int
- Definition Classes
- AnyRef → Any
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- val EPSILON: Double
- Attributes
- protected
- Definition Classes
- MinimizerLP
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- 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
- val checker: CheckLP
- Definition Classes
- SimplexBG → MinimizerLP
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @native() @HotSpotIntrinsicCandidate()
- def dual: VectoD
Return the dual solution vector (y).
- 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.
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- final def flaw(method: String, message: String): Unit
- Definition Classes
- Error
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- def hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- def infeasible: Boolean
Determine whether the current solution (x = primal) is still primal feasible.
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- 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
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- 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
- SimplexBG → MinimizerLP
- 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
- def primal: VectoD
Return the primal (basis only) solution vector (x).
- def primalFull(x: VectoD): VectorD
Return the full primal solution vector (xx).
- 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
- def showTableau(iter: Int): Unit
Show the current BG tableau.
Show the current BG tableau.
- iter
the number of iterations do far
- 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
- SimplexBG → MinimizerLP
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- 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
- 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
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- var x_B: Array[Int]
Deprecated Value Members
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable]) @Deprecated
- Deprecated