Home

Welcome to the IoS-Algorithm wiki!

We're designing and implementing a matching algorithm for assigning students to project groups based on various constraints and optimization criteria, e.g. stable pairs, equal distribution of skills and/or students, group diversity or homogeneity, 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 a target 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.

References

1. E. Ronn, NP-Complete Stable Matching Problems, Computer Science Department, Technion-Israel Institute of Technology, Haifa 3X00, Israel
2. 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