Which algorithm can calculate an optimal allocation of students to projects?

Question

I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects are predetermined and of fixed number and each student needs to be allocated to exactly one project. Each project needs at least one student, but can hold up to a maximum of $y$ students.

For my purposes, there will be on average between 8 to 15 projects available and 80 to 250 students to assign to these projects, resulting in average group sizes of 8 to 15 students per project. A reasonable value for $y$ is usually $\frac{n}{m}+2$.

The definition of optimal and stable as put by @Gassa:

(1) There is no student $S$ assigned to project $P$ such that $S$ likes $Q$ more and $Q$ has an empty slot; (2) there is no pair of students $(S,T)$ such that the current assignments are $S→P$ and $T→Q$, but $S→Q$ and $T→P$ would both be more preferred.

All sort relevant sources I could find so far (listed below) either require an equal number of students and projects (stable marriage) or allocate only one student to each project (exchange-stable matching [1] / the matching problem) and I find it non-trivial to adapt these algorithms for the described purpose.

Sources

• [1] Pages 41ff of Algorithmics of Two-Sided Matching Problems by David J. Abraham
• [2] A Systematic Approach to the Implementation of Final Year Project in an Electrical Engineering Undergraduate Course by C. Y. Teo and D. J. Ho
• [3] Student Project Allocation Using Integer Programming by A. A. Anwar and A. S. Bahaj
• [4] Similar (but not identical) question Assignment based on ranked preference on Stack Exchange

Answer 1

This sounds much like a problem for minimum-cost maximum flow.

Construct a network. The nodes will be the students, the projects, and the added source and sink.

Add an edge with capacity $1$ and cost $0$ from the source to each student.

Add an edge with capacity $y$ and cost $0$ from each project to the sink.

Add an edge with capacity $1$ and cost $r_{i,j}$ from each student $i$ to each project $j$, where $r_{i,j}$ is the rank given by student $i$ to project $j$, the most preferred being ranked $1$. (Alternatively, we can give negative scores, $-m$ up to $-1$, or even $-(2^m)$ up to $-(2^1)$, and more negative is more preferred. I believe the exact scheme is not significant.)

Now find the minimum-cost maximum flow. The maximum-ness of the flow means that each student is assigned to some project, because the maximum flow is obviously equal to the number of students.

The condition which can break is that each project gets at least one student. (Before proceeding to remedy this, first, check if the values $n$, $m$, and $y$ make failing this condition at all possible.) We can force it by splitting the edges from projects to the sink: instead of one edge of capacity $y$ and cost $0$, we can have an edge of capacity $1$ and cost $-L$, and another of capacity $y - 1$ and cost $0$. The value $L$ is a large constant, effectively infinite compared to all other costs: if we just use the ranks from $1$ to $n$, perhaps something like $m \cdot n$ will suffice. This way, a minimum-cost flow will have to add at least one student to every project in order to use all of the available edges of cost $-L$.

The thing left to prove is that the resulting arrangement is stable. Indeed, if the stable condition was not satisfied, we could just make a local change, like switching a student to their more preferred project, or swapping the projects for two students. These would result in strictly lower cost with the same flow, which would in turn contradict the fact that we found the minimum cost flow.

I'm not going into details here (we should start with a formal definition of stableness when only one side has preferences), but hope that they turn out trivially right. In the unfortunate case they don't, the first I'd do is revisit the cost assignments for $r_{x,y}$.