Due: Tuesday, May 10, 2011.
Penalty for late homeworks: 10% for each day or part of a day.
Define a greedy algorithm for the node packing problem. How does your algorithm do on the
instance given in Figure 9.1 on page 343 of the text?
Describe a tabu search algorithm for node packing. Be sure to define your valid solutions,
your neighbourhoods, and what you would do with violated constraints. Run your algorithm
on the instance given in Figure 9.1 on page 343 of the text, starting from the solution you
found in Question 1 until the algorithm finds two more local minima.
Reformulate the following binary polynomial problem as an equivalent binary linear program, and
solve it (using AMPL or otherwise):
