Schoolclass Optimization Algorithm for finding Stable Matching

Question

I have the task to write a program that puts students in classes and that in the best possible way.

We have given the name, the foreign language a student chooses(french or latin), a profile (Music,bilingual or normal) and 2 friends and enemys for every student in a table. A friend is someone a student should be in a class with(no must) An enemy is someone a student shouldn't be in a class with(no must)

As settings we have the minimum and maximum count of students in a class, the maximum count of classes general, maximum count of classes with latin, music and bilingual each.

In the end we want the students put in a class, with at best both their friends, without their enemys and least mixture between the different foreign languages and profiles.

Do you have any rough idea how I could solve this?

Thanks in advance

Answer 1

You can use the Gale-Shapley algorithm (or deferred acceptance algorithm) and opportunely modify it in order to model your case.

In the original algorithm, you have to pair elements from two sets. Here, you have to pair students and classes, but a class can be paired with more than one student. For doing so, it is sufficient to keep a counter for classes' capacity and decrease a counter by 1 each time a student is assigned to a class.

The one who do the choice is the student, while the class receives the proposal. A class would reject a student if it is full.

You have to define the priorities of a student (language, friends, enemies).

You can assign a student and then assign theyr friends to the same class and enemies to another class (if possible). The algorithm could remove a friend if it is necessary, or reassign an enemy to that class.

This algorithm will find a stable matching (but an optimal solution is not guaranteed).

For more details on the original algorithm: https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm