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.