Optimizing Dorm Assignments

The Dorm Assignment problem can readily be structured for simulated annealing:

• The dormitory system can be described concisely in terms of students and beds;
• The students can be rearranged in different beds randomly;
• An objective function based on student preferences can be devised;
• Through trial and error, and a bit of luck, an effective annealing schedule can be found.

The existing HMS system provides us a convenient description of the problem domain: The beds and the students (Figure 1.2). The student data is entered into the system from the application forms manually, and more recently through a trial scanning system.

Figure 1.2: System Overview

In the DAO, each rearrangement attempt, or move, is based on switching a randomly chosen student with the occupant of a randomly chosen bed (though it may be empty). Available beds are selected directly instead of first selecting a room and then a bed, eliminating any dependency upon room capacity. Virtual beds, though nonexistent in physical reality, are offered as possible temporary alternatives -- amounting to a kind of waiting list. Students who have already been assigned a room by the Housing Reservations staff or a previous run of the DAO, are considered unmoveable and are never selected, but their preferences continue to be considered in the placement process of their roommates.

The objective (cost) function is a sum of per-student error terms. Used to calculate the overall cost, Housing chooses the coefficients for these terms -- an art in itself. As the primary repository of preference and policy choices, this objective function will be the focus of Chapter 2.

To minimize the cost function, five annealing schedules: Algorithmic, table-driven, and three adaptive algorithms, each with its own criteria for reducing temperature and phase and determining completion, were devised and studied for this project. To use simulated annealing effectively to sample the search space efficiently, a good cooling schedule is crucial [EFC98] -- this is the focus of Chapter 3.

download thesis