\ Opgave 9 

maximize 
   z = 5x1 + x2
subject to
   -x1 + 2x2 <=  4   
    x1 -  x2 <=  1
   4x1 +  x2 <= 12
    x1, x2 >= 0, integer

a) IP optimum (2,3) z = 13
 
b) LP optimum (13/5, 8/5) z = 73/5 = 14.6

   nearest IP-point is (3,2)  -> infeasible
   other IP-points are (2,1)  -> not optimal
                       (3,1)  -> infeasible
                       (2,2)  -> not optimal

c) Branch-and-bound, branching on most fractional variable
   in LP-solution


   initialize z = - infinity

   node 0: LP optimum (13/5, 8/5) z = 73/5 = 14.6

   node 1: add constraint x1 <= 2
           LP optimum (2, 3) , integer solution, update z = 13
           upper bound = z, hence backtrack
           
   node 2: add constraint x1 >= 3
           infeasible, hence backtrack