Return to the model of Exercise 15-21, and consider solving it approximately with Improving Search Algorithm 15B over each of the following move sets:

M1! 5reassignments of a single professor to any office6 M2! 5reassignments of a single professor to a vacant office6 M3! 5swaps of the assignments of two professors6 The search will begin with each professor randomly assigned to a different office.

(a) Show that all these move sets yield a polynomial-
size neighborhood in terms of numbers of professors and rooms.

(b) Compare the 3 move sets with regard to whether every neighbor of any current feasible solution must also be feasible.

(c) For those move sets that can produce infeasible neighbors, show how the objective function of your model can be modified with “big M” penalties to make such infeasible solutions unattractive.