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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Solving the Student-Project Allocation Problem with Preferences over Projects Using a Multi-start Local Search

  • Le Quoc Anh,
  • Nguyen Nhu Son,
  • Son Thanh Cao,
  • Hoang Huu Viet

摘要

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.