I have written a program that matches students to courses, with the following conditions.
- A student chooses 12 course-types (biology, art, math, sport, ...).
- A course of a type can exist more than once (e.g. three 3 art-courses).
- A course has exactly one predefined time-slot (there are 12 slots). Example: art-1 in slot 1, art-2 in slot 3 and art-3 in slot 12.
- A student has to be assigned to as many as courses as possible. The restriction is, that the student may only be in one course per time-slot.
- courses of the same type should have approx. the same amount of students! (hard), or in other words there should be a limit of students per course.
First Algorithm
My first algorithm did the following. I processed the students in random order. Then I computed a bipartite matching from the set of course-types of the students (left) to the time-slots of the course-type. The Number 1 means "there is a course of that type in that slot".
slot1 slot2 slot3 .....
biology 0 1 0 .....
art 1 0 1 .....
math 1 1 0 .....
sport 1 0 0 .....
....
A maximum bipartite matching guarantees, that each students participates in as many course-types as possible. But if you compare art-1 and art-2 and art-3, it may happen, that the amount of students differ extremely (Example: art-1:33, art-2:17, art-3:28).
Second Algorithm
My second algorithm did the same as the first, but this time I used a minimum weight bipartite matching. If a course-type is not in a time-slot I assigned a very high number (infinity). If a course-type is in a time-slot I assigned to courses with less students a lower number. This algorithm worked quite well, the distribution of the students to the courses is much better. But this is still a greedy algorithm, because the students are processed one after the other.
Question
Is there a polynomial time (matching, maximum-flow, ...) algorithm where each students maximizes its courses AND the courses have limits of students they can take?
The following post was very interesting: Maximum "$2$-to-$1$" matching in a bipartite graph ... but to get it work with course-capacities I would need a 3-to-1-matching (which I think ist NP-hard), because there are 3 implications. If a students is assigned to a course (1) the time-slot is "used", (2) the course-type is "used" and (3) a seat of the course is "used".
Thank you for your help,
Benjamin