Helping School Reopening Using Operation Research
Arnaud Sahuguet & Amélie Marian | Illustrations by Gary Zamchick | NYC Response Lab
School re-opening is on everyone’s mind. Students want their education back. Teachers want their students back. Parents want their life back. And everyone wants to be safe.
But the school experience in the time of Corona will be very different. Social distancing guidelines require fewer students per classroom and within school buildings each day. Students should always interact with the same set of other students to limit exposure and to facilitate contact tracing.
The "Plan"
All across the country, school districts that are ready to reopen are adopting variations of a straightforward approach to address safety: reduce the number of students at school at a given time by creating cohorts.
As a concrete example for New York City, one option is for students to be split into 4 groups (A to D) with the following schedule for each group.
As you can see from the diagram, this means 1.66 days at school instead of 5 every week for 3 groups of students, the fourth group being all-remote. You can read more about the NYC plan here.
Grades, Homerooms, Groups Divided into Cohorts
Here is a simple model for schools:
- A student belongs to a grade level: K, 1st, 2nd, 3rd, etc.
- A grade level is split into homerooms. A homeroom is where instruction happens (in-person or remote). It is usually associated with a teacher and a classroom.
- With the new plan, a student now also belongs to a group (A, B, C, etc.).
As a school principal, your mission is to assign students to cohorts, where a cohort represents a set of students for a given grade, homeroom, and group.
The assignment must follow the following constraints:
- a student belongs to one and only one cohort
- the cohort must match the grade the student is part of
- homerooms must have a proper size
- cohorts must have a proper size (based on current social distancing guidelines)
The assignment must also anticipate the fact that the situation will evolve: some students will opt-in or out of in-person instructions (NYC is allowing quarterly moves), social distancing guidelines may be tightened or relaxed, all of which will require splitting, merging, or reassigning cohorts.
On top of that, the principal must handle special cases such as:
- students who cannot be in the same homeroom, e.g. because of bullying
- students who must be in a specific homeroom, e.g. because of special needs
- twins who must be in the same cohort to limit exposure
- and more
The assignment should also make life manageable for families:
- A family should have all its children in the same group.
- Families doing car-pooling or sharing childcare should be in the same group.
- Families should be able to express preferences about groups.
- and more
Creating such an assignment is not a trivial problem. Doing it by hand is going to be time-consuming and frustrating. Small adjustments are bound to be needed for various reasons. And because of constant changes in the unfolding of the pandemics, this work will have to be done more than once (at least quarterly for the NYC plan).
Operation Research to The Rescue
It turns out that the problem stated above has a natural mathematical formulation as a Mixed Integer Linear Programming (MILP), a branch of Operation Research. Operation Research originated during World War I to solve military planning issues. It seems adequate that it finds itself useful again as part of the war against COVID-19.
Formulating the Problem
Let's consider a school with 600 students, split across 6 grade levels, with 4 homerooms per grade and 3 groups. That's 6*4*3 = 72 cohorts to assign. We will use the following notation for cohorts: 401B corresponds to 4th grade (the first digit), homeroom 401 (the first 3 digits), and group B (the last letter).
One way to think about the assignment problem is as follows. We have a large spreadsheet with 600 rows (1 per student) and 72 columns (1 per cohort). We need to populate the spreadsheet with 0s and 1s: a student is part of the cohort (1) or not (0).
All the constraints we mentioned before can be expressed as simple mathematical relationships inside the spreadsheet. For instance, "a student belongs to one and only one cohort" translates into "for each row, the sum of all its columns is exactly 1".
The Proof is in the Pudding
To convince ourselves – and you too, dear reader –, we have built a simple proof of concept.
(1) We have simulated a school with 600 students across 6 grade levels. Names, sizes of families, grades, etc. have been generated randomly. You can see the result below. We are using a unique "Family ID" per family to track family members and distinguish between families with the same last name.
This is the input.
(2) We have encoded the assignment problem using or-tools, an open-source MILP library from Google.
(3) We have set general constraints that model real-life socially-distanced school scenarios: (a) homerooms must have between 25 and 32 students, (b) groups must be balanced so that approximately a third of the students are in school each day, (c) each cohort must contain between 8 and 12 students, (d) siblings must be in the same group.
We have also added a few ad-hoc constraints to represent real-life scenarios:
- Family #41 and family #42 MUST be in the same group because they do car-pool together.
- Student #476 and Student #477 MUST NOT be in the same homeroom because of past bullying incidents.
- Student #499 MUST be in homeroom 203 because of special needs.
(4) We have run the algorithm. The algorithm takes around 6.5 seconds on a 5-year-old MacBook Pro laptop. The algorithm has been implemented using less than 200 lines of Python code.
The result is presented below. You can check that all the constraints are valid if you want :-)
Et voilà! The school principal now has a valid assignment for all their school students. They can choose to re-run the algorithm, add new constraints, change class sizes, etc. as they see fit.
Icing on the Pudding
Another benefit of using Mixed Integer Linear Programming is that it is an optimization framework that finds "the best" solution that validates all the constraints. This means that we can add family preferences (e.g. I want Group A or B, but not C) as input to the problem, and the tool will try to find the best solution that maximizes "family happiness".
What's Next?
After reading about the various plans to re-open schools and discussing with education professionals, we realized that some of the challenges they are facing could be solved using techniques borrowed from Operation Research.
The purpose of the tool we have built is to augment rather than to replace. We leave the tedious part of the task to the tool and let education professionals focus on stating the problem in a clear, fair, equitable, and safe way for all the parties involved.
We think this tool can be useful.
We would appreciate your feedback.
We would love to help.
Feel free to contact us.
Amelie Marian is an Associate Professor in the Computer Science Department at Rutgers University and is an NYC public school parent of three children.
Arnaud Sahuguet is the project lead for the Urban Tech hub at Cornell Tech and the parent of twin toddlers too young to go to school for now.
