Neighborhood Landscapes

Figure 2.1: Neighborhood Landscape at a Random Point

The landscape of the neighborhood of a single random point is represented in Figure 2.1. The value of the objective function was 520 million, achieving only 37% satisfaction, leaving 803 out of 1267 students nowhere they wanted to be, and only 202 students receiving a perfect score. The histogram shows the nearly symmetric distribution of the cost changes of this neighborhood. The significantly better moves are below the cloud line (negative change in cost), while those above the cloud line are worse.

Figure 2.2: Neighborhood Landscape of the Most-senior and Least-senior Students at a Random Point

In Figure 2.2 we isolate the most senior student, who we'll call `$Al$' (at position 10), a resident for eleven consecutive semesters, and the least senior student, `$Zo\ddot{e}$' (at position 1267), a first time resident, at the single random data point to see how they would fare in any other available bed. As it happens, $Al$ objects to smoke and requested the apartment-style dorm for all three choices, with one roommate request, and a special request to be in the graduate area; $Zo\ddot{e}$ is a smoker with no hall preferences or roommate requests. They were both randomly placed in virtual beds.

The best place for $Al$ is the apartment-style dorm (near bed 700) which matches the special living option he requested and switches with someone who has no desire to be there. $Zo\ddot{e}$ improves her score pretty much anywhere we place her; the worst places for her are non-smoking apartment-style rooms with the non-smoking special living option (near bed 1000).

Figure 2.3: Neighborhood Landscape at a Single (local optimum) Point

Using the same constraint values and data as in the random point, after six rounds taking approximately two hours, the global score declined to 45 million, achieving 97% satisfaction with only 32 out of 1267 students nowhere they wanted to be, and 697 students receiving a perfect score. The result of this complete run, as we can see in Figure 2.3, is a local minimum -- there are no better single moves (below zero) for any student.

Figure 2.4: Neighborhood Landscape of the Most-senior and Least-senior Students at an Optimized Point

Two slices of the neighborhood landscape for our students, $Al$ and $Zo\ddot{e}$, at the optimized point can be seen in Figure 2.4. $Al$ got his first hall choice in the graduate area, but didn't get his roommate request because it was not a reciprocal request and the special grad area wasn't mutually specified. $Zo\ddot{e}$, who was so easy to please, got a perfect score. Her set of possible alternative moves exhibits the end of a phenomenon that looks like a `hole' in the cloud.

Figure 2.5 pinpoints the start of this obvious `hole' between the last second semester resident, $Mary$ (at position 718), and the first new student (at position 721) $Nick$. $Mary$ got her second hall choice, but not her requested roommate, a more senior resident who wanted and got into the apartment-style dorm. $Nick$, assigned to his first hall choice with the scholar's wing special option and no requested roommates, has a perfect score. Attempting to move him into any of the coveted apartment-style dorms (beds 673 through 1161) severely hurts his grade with increased costs -- this begins the vacant region.

Figure 2.5: Neighborhood Landscape of the Least-senior and First-new Students at an Optimized Point

The Objective Function has terms that include dependencies between students, not just students and beds independently. As we've seen with $Al$'s assignment, a student requests other students as roommates, and depending upon the locations of the requested roommates there may be a `mismatch' or `error'.

download thesis