308-567B                       Integer Programming
Due: Tuesday, January 28,  2003   (in class)


1(a) Write down the dual of the LP relaxation of the  set covering problem (p. 7).
(b) Give an example where the integer LP solution is strictly more than the LP relaxation.
(c) Give an interpretation of the dual problem, considered both as an LP and an integer program.

Problems from Integer Programming, Wolsey

2. P. 19 Ex. 5

3. P. 21 Ex. 12 . Solve using CPLEX or lpsolve (see course software on home page).
          First try to solve without any subtour elimination constraints. Then add them if they become necessary, continuing until you get a travelling salesman tour.