dividing up a large class into discussion sections using integer programming

I am team teaching a freshman course on engineering grand challenges with five other instructors. Each of the six instructors teaches a “theme” (mine is about systems, critical infrastructure, and logistics) to a subgroup of students. We must partition the students into six themes twice, since we repeat our themes in the second half of the semester with another group of students (we call these modules). To facilitate the assignments, students can submit a rank ordering of their top four choices. I was asked to use optimization to make the pairings. I thought about manually making the matches, but I could see that it would be a lot of work to redo the matchings if someone wanted to make some changes later on. So I put together a quick optimization model to do the work for me.

Here are the constraints:

• Theme class sizes must be between 21 and 24 students
• Each student should get one of their top two choices (this is not guaranteed)
• Every student needs to be assigned to a theme in each module
• Every student needs to be assigned to different themes across the two modules
• Two groups of students are in first year interest groups (FIGs) and should all be assigned to the same first theme, regardless of preferences. This is a hard-but-flexible constraint (is that a thing?). These students needed to be assigned to the same theme, but I could choose any theme for them.

I had about two days to make the assignments and possibly field some requests to change the assignments. Integer programming was appealing because it would allow me to quickly make changes to the assignments and do a “what if” analysis. I could quickly see that it was going to be impossible to fill some of the themes based on student preferences. Luckily, some students did not submit preferences, so I could use these students to “pad” the assignments while maintaining a good solution. The objective function captures the quality of the assignments based on student preferences, so I would always have a feasible solution. I assigned weights for each student-theme pair as the objective function coefficients. I assigned the first choice theme a weight of 8, the second choice theme a weight of 4, a third choice theme a weight of 2, and a fourth choice theme a weight of 1. I assigned all other student-theme pairs a weight of zero. The goal was to mostly assign students to first and second preferred choices, so I chose weights that would “encourage” this. After solving the model I could easily check to see how many students were assigned to one of their top two matches (we promise to do this, if its possible).

The FIGs was a bit tricky. This constraint made it hard to eyeball a good solution and motivated the use of integer programming. I wanted to be able to manually test out different theme assignments for the FIGs and possibly have the flexibility to change the assignments really quickly if one of the instructors did or did not want a FIG. I manually selected themes for the FIG students by fixing variables and then optimized the assignment of everyone else. I could have treated the FIG assignments as a decision instead of an input.

Here are the parameters:

• N = 138 students
• T = 6 themes
• M = 2 modules
• : preference weight for student n and theme t (either 0, 1, 2, 4, or 8).

Here are the binary decision variables:

• : 1 if student n is assigned to theme t in module m.

The integer programming model is as follows.

maximize

subject to

The objective function maximizes the value of the assignments. The first constraint sets class sizes between 21 and 24. The second constraint ensures that a student is not assigned to the same theme across both modules. The third constraint ensures that each student is assigned to one of the themes in both modules. I do not require the model to assign students to one of their top two choices, and therefore, a feasible solution is always easy to find. However, I checked afterward to see if students got what they wanted (according to my results, they did!). What isn’t in this model is fixed variables associated with FIG student assignments, but that is straightforward to change.

The model was easy to set up except for setting the weights  based on student preferences. This information came from a survey we conducted on the course management system. Downloading the data in a spreadsheet did not give us a flat file, so it took some extra parsing to get the right data. We would have needed to parse the survey data even if we made the assignments manually, so this was unavoidable. I would have liked to ensure diversity in teams somehow, but I did not have the data for this. Next time.

All in all, this was fun, and I would recommend the use of integer programming. It took me longer to write this post than to set up and solve the integer program to assign students to themes 🙂