This section will cover a demonstration of the proposed system. We will be using the Hungarian method for assignment. The process will be described below.
- Create a square with the assignment option along the top of the matrix and student along the left side with the elements of each coordinate being the cost of making said assignment. This means that each column represents one possible dorm assignment option and each row represents one group that can possible be assigned to that room. The values associated with each column and row represents the cost of assigning row x group to column y dorm room.
- If the matrix is not square, create dummy rows (assignments) for students who will not be assigned.
- Find the smallest value in each row and subtract that value from every element in that row.
- Find the smallest value in each column and subtract that value from every element in that column.
- Draw the least amount of vertical and horizontal lines through the matrix so that each zero is crossed out. If the number of lines equals the number of rows, skip to step 9.
- Find the smallest element that is not crossed out and add that value to every value that is crossed out and add it twice if the value is crossed out twice.
- Find the smallest value in the matrix and subtract it from every value in the matrix.
- Go to step 5.
- Choose zeros so that each row and column only have one zero selected. These are the student assignments.
- Find the values for each element in the original matrix and add them together to find the assignment cost. Do not add the values for the dummy assignments
First, we must assign cost to each associated assignment. A student being assigned to their top preference will cost the least and their last preference will cost the most. The goal is to minimize the cost and thus maximize the top preferences assigned.
|1st Choice||+ 1|
|2nd Choice||+ 2|
|3rd Choice||+ 3|
|4th Choice||+ 4|
|5th Choice||+ 5|
|6th Choice||+ 6|
|7th Choice||+ 7|
|8th choice||+ 8|
|9th choice||+ 9|
For this implementation, we will focus on students who have a group of four. While there will be one housing round and deadline, each group size will go through the assignment process individually which allows us to focus on individual groups sizes. For the purposes of evaluation, we will simulate group four assignments with the following housing availability:
This demonstrates 7 different options with 35 total slots available.
We now need to get sample housing preferences from groups. We chose to do 35 groups to make the numbers easy. Normally we would use the google survey to get group preferences but for the demonstration we generated random preferences using the RANDBETWEEN(1,7) function in excel.
|Group||Modern Double||Modern Single||Trad. Singles||Village Singles||Village East||U. Drive||Millbrook|
In order to use the MATLAB function munkres (Hungarian method code), we created a table in MATLAB similar to the one seen in the previous section. As stated in the Proposed Method section, the assignment options must be listed across the top of the matrix and the student groups along the left side, with each element being the associated cost; however, we stated before that there were five slots for each room type and the table in the previous section would only allow for one possible slot, as each column represents a possible assignment. In order to correct this, we copied each groups preference for each assignment five times. An example is shown below:
|Group||U. Drive||U. Drive||U. Drive||U. Drive||U. Drive||Village East||Village East||Village East||Village East||Village East|
In this example, we see that there are ten possible assignments with five being from U. Drive and five from Village East. One problem with this was that each cell returned a random value between one and seven. In order to maintain the same values for each group preference, we first created a column next to the first preference column and assigned the values from the first column to the second. We then copied this second column three more times. We did this by placing the code provided in the deliverables section into a new excel module.
After formatting the data correctly in a variable called “housing”, and applying the code for munkres found in the deliverables section, we used the following line of code to get our optimal solution:[assignment,cost] = munkres(housing)
This code returned an associated assignment matrix and cost. The assignment matrix and cost are listed here:
As seen above, the total cost is 55 and we have a table with the chosen assignment. For example, there were five options for modern doubles, and they were listed first. This means that the groups assigned to values 1-5 are in modern doubles. This would be group 1, 9, 17, 23, and 33.
In order to simulate a random selection, which is how the current housing method works, we decided to go in order by group number. This would assume that the random selection has already occurred and group one was selected to choose first and group thirty-five was selected to choose last. Each group will choose their top preference available until all assignments are made. We also did this random assignment in reverse order, meaning that group thirty-five would go first and group one would go last. After completing both of these methods, we obtained a cost of seventy and sixty-eight, respectively.
As we can see, the Hungarian method produces the most effective method for assignment.