The student project allocation problem I am trying to solve goes as follows.
- There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$.
- Each student makes a top $3$ of their preferred projects.
- Each student should be allocated to exactly one project.
- Each project has a maximum number of students which can choose it, $c$.
We want to find some combination of students being allocated to projects so that a maximum of students are allocated their preferred project. Of the students who didn't get their preferred choice, a maximum of them should be allocated their second choice.
This is a optimization problem with constraints. If we assign a priority weight $w_{ij}$ for the $i^{th}$ student choosing the $j^{th}$ project, where $w_{ij} \in \{0, 1, 2, 3\}$, and $w_{ij}$ is $0$ when the student $i$ did not include project $j$ in his top $3$, $1$ if it is his third choice, $2$ second choice, $3$ preferred choice.
We can also introduce a variable $x_{ij} \in \{0, 1\}$, which is equal to $1$ when student $i$ has been allocated to project $j$ and $0$ otherwise.
Now we can formulate an objective function, $o$, to maximize in order to reach an optimal allocation.
$$o = \sum_{\forall (i, j) \in S \times P}{x_{ij} \cdot w_{ij}}$$
We must maximize $o$ according to the problems constraints.
$$\forall i \in S : \sum_{\forall j \in P}{x_{ij}} = 1 \quad \textrm{every student is allocated to exactly one project}$$
$$\forall j \in P : \sum_{\forall i \in S}{x_{ij}} \leq c_j \quad \textrm{no project is allocated more than its maximum number of students}$$
I think there are no other constraints.
Now, I am stuck. How do I go about actually solving this on a computer given all of the above. Is there a relationship between the optimal allocation for $i$ students and $i + 1$ students? Can I use dynamic programming, and if so how? Or do I have to use some other method, and if so what method?