| |
| author |
Ryan Kulyassa
| | title |
The Student-Course Assignment Problem: Simulated Annealing for Bipartite Graph Optimization and Comparative Analysis
| | abstract |
The Student-Course Assignment Problem (SCAP) models the challenge
of assigning students to courses based on ranked preferences while satisfying
real-world constraints such as course capacities and enrollment considera-
tions. This problem arises frequently in academic institutions, where admin-
istrators must balance student demand with limited resources and ensure
equitable access to course offerings. A traditional optimization approach
like the Hungarian Algorithm (HA) guarantees optimal matchings under
rigid conditions and assumes a square cost matrix with one-to-one assign-
ments. While mathematically elegant, HA struggles to accommodate real-
world considerations such as variable course capacities, enrollment distribu-
tion, and other complex constraints. It also suffers from poor scalability in
large datasets due to its cubic time complexity. In this thesis, we formalize
SCAP as a bipartite graph optimization problem and propose a heuristic
solution using Simulated Annealing (SA). SA offers greater flexibility in han-
dling complex, real-world constraints and provides fine-grained control over
the optimization process. We implement and test SA against an HA-based
implementation on real-world student preference datasets, comparing their
accuracy, runtime, and ability to manage enrollment variance—our chosen
real-world constraint. Our results show that SA achieves near-optimal solu-
tions with better scalability and adaptability, making it a strong candidate
for practical deployment in academic scheduling systems.
| | school |
The College of Liberal Arts, Drew University
| | degree |
B.A. (2025)
|
| advisor |
Steven Kass
|
| full text | RKulyassa.pdf |
| |
