IntegerProg

This 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. TODO: 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 maxmize 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

Linear Supertypes

AnyRef, Any

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[java.lang]
Definition Classes
AnyRef
Annotations
@throws( ... )
final def eq(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def equals(arg0: Any): Boolean

Definition Classes
AnyRef → Any
def finalize(): Unit

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( classOf[java.lang.Throwable] )
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[_]

Definition Classes
AnyRef → Any
def hashCode(): Int

Definition Classes
AnyRef → Any
final def isInstanceOf[T0]: Boolean

Definition Classes
Any
final def ne(arg0: AnyRef): Boolean

Definition Classes
AnyRef
final def notify(): Unit

Definition Classes
AnyRef
final def notifyAll(): Unit

Definition Classes
AnyRef
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(): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long, arg1: Int): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
val x_ge: VectorD
val x_le: VectorD

Related Doc: package maxima

class IntegerProg extends AnyRef

Instance Constructors

new IntegerProg(a: MatrixD, b: VectorD, c: VectorD, excl: Set[Int] = Set ())

Type Members

type Constraints = (MatrixD, VectorD)

Value Members

final def !=(arg0: Any): Boolean

final def ##(): Int

final def ==(arg0: Any): Boolean

def addConstraint(j: Int, le: Boolean, bound: Double): Boolean

final def asInstanceOf[T0]: T0

def clone(): AnyRef

final def eq(arg0: AnyRef): Boolean

def equals(arg0: Any): Boolean

def finalize(): Unit

def formConstraints: Constraints

def fractionalVar(x: VectorD): Int

final def getClass(): Class[_]

def hashCode(): Int

final def isInstanceOf[T0]: Boolean

final def ne(arg0: AnyRef): Boolean

final def notify(): Unit

final def notifyAll(): Unit

def solution: (VectorD, Double)

def solve(dp: Int, cons: Constraints): Unit

final def synchronized[T0](arg0: ⇒ T0): T0

def toString(): String

final def wait(): Unit

final def wait(arg0: Long, arg1: Int): Unit

final def wait(arg0: Long): Unit

val x_ge: VectorD

val x_le: VectorD

Inherited from AnyRef

Inherited from Any

Ungrouped