scalation.maxima

IntegerProg

class IntegerProg extends AnyRef

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
Ordering
  1. Alphabetic
  2. By inheritance
Inherited
  1. IntegerProg
  2. AnyRef
  3. Any
  1. Hide All
  2. Show all
Learn more about member selection
Visibility
  1. Public
  2. All

Instance Constructors

  1. new IntegerProg(a: MatrixD, b: VectorD, c: VectorD, excl: Set[Int] = scala.this.Predef.Set.apply[Int]())

    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

  1. type Constraints = (MatrixD, VectorD)

Value Members

  1. final def !=(arg0: AnyRef): Boolean

    Definition Classes
    AnyRef
  2. final def !=(arg0: Any): Boolean

    Definition Classes
    Any
  3. final def ##(): Int

    Definition Classes
    AnyRef → Any
  4. final def ==(arg0: AnyRef): Boolean

    Definition Classes
    AnyRef
  5. final def ==(arg0: Any): Boolean

    Definition Classes
    Any
  6. 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.

    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

  7. final def asInstanceOf[T0]: T0

    Definition Classes
    Any
  8. def clone(): AnyRef

    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  9. final def eq(arg0: AnyRef): Boolean

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

    Definition Classes
    AnyRef → Any
  11. def finalize(): Unit

    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  12. def formConstraints: (MatrixD, VectorD)

    Starting with the original constraints (a, b) add the current set of bounding constraints.

  13. 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

  14. final def getClass(): Class[_]

    Definition Classes
    AnyRef → Any
  15. def hashCode(): Int

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

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

    Definition Classes
    AnyRef
  18. final def notify(): Unit

    Definition Classes
    AnyRef
  19. final def notifyAll(): Unit

    Definition Classes
    AnyRef
  20. def solution: (VectorD, Double)

    Return the optimal (maximal) integer solution.

  21. def solve(dp: Int, cons: (MatrixD, VectorD)): 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)

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

    Definition Classes
    AnyRef
  23. def toString(): String

    Definition Classes
    AnyRef → Any
  24. final def wait(): Unit

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

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

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

  28. val x_le: VectorD

Inherited from AnyRef

Inherited from Any

Ungrouped