How to assign classroom seating to minimize number of unique neighbors across classes

Question

This question was inspired by a local school district assigning seats to try to minimize the number of students who would have to quarantine in the event of a positive COVID case.

Assume that each classroom is arranged in a rectangular grid. If a student tests positive for COVID, the neighboring students in each class have to quarantine. For a COVID-positive student with neighbors in every direction, this means up to 8 other students per class may be affected.

Generally speaking, the objective would be to assign students next to the same neighbors across classes, but each class may have a different grid shape (e.g., 6x5 and 7x4) or class roster. What type of algorithm would be able to find the most optimal arrangement(s) that minimize the "worst case" - that is, minimizing the largest number of students that would need to quarantine for a single COVID case. Note that a few seats will usually remain unoccupied, as well.

My initial thoughts were to build graphs representing the classroom layout, with seats as nodes and neighboring relationships as edges. I wasn't sure how to proceed beyond that.

Answer 1

You can use mixed integer linear programming to minimize the maximum (across all students) number of neighbors. Let binary decision variable $x_{s,i,j,c}$ indicate whether student $s$ is assigned to seat $(i,j)$ in class $c$. Let $N_{i,j,c}$ be the set of seats that neighbor seat $(i,j)$ in class $c$. For $s<t$, let binary decision variable $y_{s,t}$ indicate whether students $s$ and $t$ are neighbors in some class. Let $z$ represent the maximum number of neighbors. The problem is to minimize $z$ subject to linear constraints: \begin{align} \sum_{i,j} x_{s,i,j,c} &= 1 &&\text{for all $s$ and $c$} \tag1\\ \sum_s x_{s,i,j,c} &\le 1 &&\text{for all $(i,j)$ and $c$} \tag2\\ x_{s,i,j,c} + x_{t,i',j',c} - 1 &\le y_{s,t} &&\text{for all $s<t,c,i,j,(i',j')\in N_{i,j,c}$} \tag3\\ \sum_{t>s} y_{s,t} + \sum_{t<s} y_{t,s} &\le z &&\text{for all $s$} \tag4\\ \end{align} Constraint $(1)$ assigns each student to exactly one seat per class. Constraint $(2)$ assigns at most one student to each seat per class. Constraint $(3)$ forces students $s$ and $t$ to be neighbors if they are assigned to neighboring seats in class $c$. Constraint $(4)$ enforces the minimax objective.

---

For your example data, here's an optimal seating assignment with objective value $4$:

Class 1:
 8  4  6 10 
14  3  . 12 
 2  5 15  1 
13  9 11  7 

Class 2:
18 16 17  . 23 
24  .  . 20 19 
 . 25  . 22 21 

Class 3:
 1 15  3  5 
21 11  .  9 
19  7  . 13 
23 17 25  . 

Class 4:
16  6  4 12 10 
14  8  .  . 24 
 2  . 18 20 22 

Because class $1$ has only one empty seat, some student in class $1$ must have four neighbors, so $4$ is clearly a lower bound, even without calling a solver. The seating assignment shown above achieves that lower bound.