Initial Approach

Greedy Algorithm

We modeled the status quo of course selection using a greedy algorithm. When students sign up for classes, there is a priority ordering assigned to them, based upon their year and academic status. When each has their chance to sign up, they choose the current best classes available to them. This is guaranteed to make a stable allocation - two students could be made better off by swapping a class. However, it is not necessarily equitable or fair, and it certainly does not optimize for the total sum utility of the students.

If a program began at the current state, it would find the local maximum, and not have any way to move from there to the global max.

Hill Climbing

In an attempt to better the results of the greedy solution, we supplemented it using hill climbing. Hill climbing algorithms begin with an arbitrary valid solution, and explore neighboring solutions to see if any are more optimal. Then one of these is selected, and the algorithm repeats itself. This can either be run for a fixed number of iterations, or until there is no better neighboring solution. Hill climbing is guaranteed to find a solution that is no less optimal than the initial solution, but it does not guarantee that a global optimum is found.

Our Implementation

We implemented a hill climbing solution to this problem in C++. It may be found at this Github repo. It takes as parameters the number of students that will be simulated, the number of courses, the number of students allowed per section, the number of time slots at which courses are offered, the number of sections of each class, the number of courses each student tries to enroll in and the maximum number of iterations that our hill climbing will run. From these parameters, we randomize when the sections are offered and the preference lists of the courses for each student.

We begin by executing the greedy algorithm on the simulated data to determine what would happen without our algorithm.

We then define the neighboring allocations as those which can be achieved by swapping one student's class with another and possibly getting a class in return. One of these is selected as random and becomes the new current solution, from which we continue to optimize.

On the right is the output from a trial with 10 sections offered of 1 student each, and 10 students. Each student tried to sign up for 3 courses. As can be seen in the top image, after the greedy algorithm completed, only 4 students were allocated courses. We then hill climbed as long as we could, and after 11 iterations, the classes were distributed much more evenly and we climbed 13 utils. However, 2 students still were not allocated any courses, and we may only be at a local max. To account for this, we implemented a simulated annealing approach as well.

Report abuse