| |
| 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 considerations. This problem arises frequently in academic institutions, where administrators 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 assignments. 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 handling 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 solutions 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 |
| |
