Prev Next Top

Integer Programming

Take Home Rules
You can use books, and computers, but you cannot ask anyone (inside or outside of class) for help with these problems. The solution is due at the beginning of class next Tuesday, 06-08-08.

Theorem
We use  R+^n ( Z+^n) to denote the set of vectors with  n components each of which is a positive real (integer) value. Suppose that  y in  Z+^n solves the problem
     maximize     c^T * x       w.r.t  x in R+^n
     subject to     A * x <= b                     (L)
It follows that  y solves the problem
     maximize     c^T * x       w.r.t  x in Z+^n
     subject to     A * x <= b                     (I)

Branching
For  a in  R we use  [a] to denote the largest integer that is less than  a. Suppose that  y in  R+^n solves problem  (L) above and  yj (its j-th component) is not an integer. Branching attempts to solve problem  (I) by solving the following two problems:
     maximize     c^T * x       w.r.t  x in R+^n
     subject to     A * x <= b                      (1)
                       xj <= [yj]

     maximize     c^T * x       w.r.t  x in R+^n
     subject to     A * x <= b                      (2)
                       xj >= [yj] + 1
If the solutions of  (1) and  (2) are in  Z_+^n , then the optimal solution to  (I) is the solution corresponding to the larger objective value. If the solutions of either  (1) or  (2) is not in  Z_+^n , further branching can be used to solve the problem.

Examples
Quiz0727 Math 407 Quiz 06-07-27
TakeHome Take Home Integer Programming Problem
Input File: IntegerProgram.omh