Solving the Student-Project Allocation Problem with Preferences over Projects Using a Multi-start Local Search
摘要
The Student-Project Allocation problem with Preferences over Projects is a well-studied many-to-one stable matching problem with practical relevance in academic assignment systems. Finding a maximum stable matching that assigns the largest possible number of students to their acceptable projects is known to be NP-hard. In this paper, we introduce a multi-start local search algorithm to tackle this challenge, where each local search begins with a random matching and iteratively eliminates undominated blocking pairs to improve its stability. When a local search reaches a stable but incomplete matching, it applies a perturbation strategy to reassign unallocated students based on their preferences, thereby encouraging further improvements. The algorithm repeats this process across multiple local searches and returns the largest stable matching found. Experimental results demonstrate that our approach efficiently achieves large stable matchings within a reasonable computational time, even for large-scale instances.