Five UMD students (A, B, C, D, and E) have rented a house in College Park. The house has five rooms.

1

4

2

5

3

So, for instance, student A likes room 2 best (followed by rooms 5, 4, 1 and 3 in descending order of preference), while student B likes room 4 best (followed by 2, 5, 3 and then 1). The students determine that a rational approach would be to assign students to rooms in such a way that everyone gets their top ranked room. They quickly see that this is not going to be possible (both student A and C like room 2 best, while both students B and D like room 4 best). They figure that the next best thing would be to get everyone as close as possible to their top ranking. To this end, they attempt to find an assignment of rooms to individuals such that the added up ranks that people give to the rooms they are assigned is as small as possible. In this approach, if student A is assigned room 1, student B is assigned room 2, student C is assigned room 3, student D is assigned room 4, and student E is assigned room 5, the total of ranks people assign to the rooms they get is 4+2+5+1+3 = 15. But clearly, it is possible to do better. Can you help the students?

(a)   Formulate this as an integer/binary linear programming problem. Clearly specify the decision variables, the objective function and the constraints. You do not need to solve the model in Excel.

(b)  How would you add the following constraints to the model?

·        If E is assigned to room 1, then D must be assigned to room 2.

·        One of D or E must be assigned to room 5.

·        If one of D or E is assigned to room 5 then one of A or B must be assigned to room 4.