Social classroom seating assignment problems

Abstract University students benefit academically, personally and professionally from an expansion of their in‐class social network. To facilitate this, we present a novel and broadly‐applicable optimization approach that exposes individuals to as many as possible peers that they do not know. This novel class of “social seating assignment problems” is parameterized by the social network, the physical seating structure and “tie potentials” representing the likelihood for two neighbors to connect. The resulting problem is NP ‐hard and belongs to assignment problems with an elaborate objective that depends on the relation of both seats and individuals assigned to them. We develop compact integer programming formulations and strengthen them with valid inequalities to improve performance. In parallel, we suggest fast heuristics that are guided by network centrality measures. Finally, we present the necessary modeling techniques to integrate practically relevant instructor preferences and special student needs. Combining the above, we experiment on a set of 320 realistic instances with up to 200 students forming both sparse and dense social networks and for both rectangular and circular classrooms. For sparse or small instances we present optimality gaps under 1.3% within a few minutes, whereas in larger or denser cases the algorithmic performance decreases. We also evaluate our approach from both a quantitative and a qualitative perspective on three actual classes with more than 70 students. A network‐analysis‐based comparison of a priori and a posteriori networks shows that 40% of opportunities led to new connections, while feedback from both instructor and student is particularly favorable for our method.