-
Notifications
You must be signed in to change notification settings - Fork 0
Home
We're designing and implementing a matching algorithm for assigning students to project groups based on various constraints and optimization criteria, e.g. even distribution of skills, group diversity, student preferences, friends and foes, etc. In this wiki you can find more information about the internals of the algorithm, the theory behind it and how specific constraints are modeled in the solver.
Because this is in general an NP-hard [1] problem, finding on optimal solution would involve evaluating all possible assignments, which makes it unfeasible even for small problem sizes. We take a heuristic approach by trying to optimize an objective function. The resulting solution might not be globally optimal, but it should be statistically better than a random assignment.
The design of our algorithm follows closely the solution proposed by Hübscher [2] with some modifications and extensions. The following sections represent the gist of it.
The problem we are solving here is:
How can you distribute a set of N students over a set of G group assignments in an optimal way?
- E. Ronn, NP-Complete Stable Matching Problems, Computer Science Department, Technion-Israel Institute of Technology, Haifa 3X00, Israel
- R. Hübscher, Assigning Students to Groups Using General and Context-Specific Criteria, IEEE Transactions on Learning Technologies, vol. 3, no. 3, July-September 2010