class IntegerProg extends AnyRef
The IntegerProg class solves Integer Linear Programming (ILP) and Mixed Integer
Linear Programming (MILP) problems recursively using the Simplex algorithm.
First, an LP problem is solved. If the optimal solution vector x is
entirely integer valued, the ILP is solved. If not, pick the first 'x_j'
that is not integer valued. Define two new LP problems which bound 'x_j'
to the integer below and above, respectively. Branch by solving each of
these LP problems in turn. Prune by not exploring branches less optimal
than the currently best integer solution. This technique is referred to
as Branch and Bound. An exclusion set may be optionally provided for
MILP problems.
FIX: Use the Dual Simplex Algorithm for better performance.
Given a constraint matrix 'a', limit/RHS vector 'b' and cost vector 'c', find values for the solution/decision vector 'x' that maximize the objective function 'f(x)', while satisfying all of the constraints, i.e.,
maximize f(x) = c x subject to a x <= b, x >= 0, x must be a vector of integers
Make b_i negative to indicate a ">=" constraint
- Alphabetic
- By Inheritance
- IntegerProg
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Instance Constructors
- new IntegerProg(a: MatrixD, b: VectorD, c: VectorD, excl: Set[Int] = Set ())
- a
the M-by-N constraint matrix
- b
the M-length limit/RHS vector
- c
the N-length cost vector
- excl
the set of variables to be excluded from the integer requirement
Type Members
- type Constraints = (MatrixD, VectorD)
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
- def addConstraint(j: Int, le: Boolean, bound: Double): Boolean
Add a new constraint to the current set of bounding constraints: x_j <= bound or x_j >= bound (e.g., x_1 <= 2.
Add a new constraint to the current set of bounding constraints: x_j <= bound or x_j >= bound (e.g., x_1 <= 2. or x_0 >= 4.).
- j
the index of variable x_j
- le
whether it is a "less than or equal to" 'le' constraint
- bound
the bounding value
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @native() @HotSpotIntrinsicCandidate()
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- def formConstraints: Constraints
Starting with the original constraints (a, b) add the current set of bounding constraints.
- def fractionalVar(x: VectorD): Int
Return j such that x_j has a fractional (non-integer) value, -1 otherwise.
Return j such that x_j has a fractional (non-integer) value, -1 otherwise. Make sure that j is not in the exclusion list.
- x
the vector to check
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- def hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- 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 solution: (VectorD, Double)
Return the optimal (maximal) integer solution.
- def solve(dp: Int, cons: Constraints): Unit
Solve the Integer Linear Programming (ILP) problem by using Branch and Bound and the Two-Phase Simplex Algorithm, recursively.
Solve the Integer Linear Programming (ILP) problem by using Branch and Bound and the Two-Phase Simplex Algorithm, recursively.
- dp
the current depth of recursion
- cons
the current set of original and new constraints (a x <= b)
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- def toString(): String
- Definition Classes
- AnyRef → Any
- 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])
- val x_ge: VectorD
- val x_le: VectorD
Deprecated Value Members
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable]) @Deprecated
- Deprecated