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.