2
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ You just formulated your problem as an integer linear programming problem. There are specialized solvers for this kind of problem (CBC, ...). $\endgroup$
    – Gabriel Gouvine
    Jun 5 '20 at 10:18
  • $\begingroup$ I want to write a program myself to solve this problem though. @GabrielGouvine $\endgroup$
    – Tom Finet
    Jun 5 '20 at 10:23
  • $\begingroup$ Otherwise your problem is close to a multiple knapsack problem, which is well studied. If you want to solve it by dynamic programming, you should get some inspiration from the single-knapsack case. However, such an algorithm is unlikely to scale to even moderate-size instances $\endgroup$
    – Gabriel Gouvine
    Jun 5 '20 at 10:27
  • $\begingroup$ I encourage you to use a heuristic, such as a greedy algorithm or local search, rather than dynamic programming. $\endgroup$
    – Gabriel Gouvine
    Jun 5 '20 at 10:29
  • $\begingroup$ Ohh, so I shouldn't use dp. Would these lead to perfect solutions or approximate? $\endgroup$
    – Tom Finet
    Jun 5 '20 at 10:29
1
$\begingroup$

This sounds like it could be solved using a flow network.

Define the graph $G=(V,E)$ such that:

  1. Add a starting node $s$. It will be the "source" node in the flow-graph.
  2. Add a node $v_{s_i}$ for every student $s_i$.
  3. Add a node $v_{p_j}$ for every project $p_j$.
  4. Add the final node $t$. It will be the "sink" node for the flow-graph.

Now, start adding the edges and their weights as following:

  1. For every $s_i\in S$, add an edge $(s,v_{s_i})$ of weight 1.
  2. For every $s_i\in S$ and every preferred project of his, $p_j$, add an edge $(v_{s_i},v_{p_j})$ with weight 1.
  3. Finally, for every project $p_j$ add an edge $(v_{p_j},t)$ of weight $c$.

Run the Ford Fulkerson algorithm on this graph $G$ we defined, and it will spit out an integer flow $f$. Assign a student $s_i$ to project $p_j$ if there is flow between $v_{s_i}$ and $v_{p_j}$ in $f$. Notice there might be students that wont be assigned anything in that way. They cannot be assigned to anything they prefer - so just assign them in any free project.

This algorithm runs in time $\mathcal O(|S||P|)$ since $|V|=\mathcal O(|S|+|P|)=\mathcal O(|P|)$, and each student has up to 3 preferred project so $|E|=\mathcal O(|V|)=\mathcal O(|P|)$ as well and the value of $f$, $|f|\le|S|=O(|S|)$.

It also provides the best possible solution, since it always maximizes the flow's value which is the number you want to maximize (think why).

Improve this answer
$\endgroup$
17
  • $\begingroup$ Do you have a good resource for learning about flow networks? I don't understand what it means for there to be a flow from $v_{s_{i}}$ to $v_{p_{j}}$ in $f$. @nirshahar $\endgroup$
    – Tom Finet
    Jun 5 '20 at 13:57
  • $\begingroup$ Did you take an algorithms course? it is learned there. Anyways, are you familiar with putting "weights" on nodes (for example as in pathfinding algorithms)? This idea is (somewhat) similar. Instead of "weights", we call it "capacity" (and we try to do something else with it). $\endgroup$
    – nir shahar
    Jun 5 '20 at 14:01
  • 1
    $\begingroup$ While this approach does assign as many students as possible to some project on their list, it seems their order of preferences is ignored. In other words, this solution does not assign as many students to their most preferred project. The latter is what makes this problem difficult, and leads to the use integer programming in practice. $\endgroup$
    – Discrete lizard ♦
    Jun 5 '20 at 14:03
  • 1
    $\begingroup$ @TomFinet As Gabriel Gouvine noted in the comments, you basically have already described an integer (linear) programming formulation. We have no polynomial time algorithms for solving integer programs, but it turns out many important problems can be expressed as an integer program, and there are several heuristics that allows us to solve many integer programs in practice using specialized solvers. Of course, writing a solver for general integer programs by yourself is probably not the most effective way to approach this problem. $\endgroup$
    – Discrete lizard ♦
    Jun 5 '20 at 14:10
  • 1
    $\begingroup$ Indeed it can be expressed as a flow problem. It can be solved as an assignment problem, for example. You will find several algorithms on the Wikipedia page. $\endgroup$
    – Gabriel Gouvine
    Jun 5 '20 at 14:19
1
$\begingroup$

This is a variation of the assignment problem. You will find several algorithms on the Wikipedia page linked, although none makes use of dynamic programming.

You can transform your formulation into an assignment problem by subdividing each project in $c$ projects of one student each, and creating phantom students with no preferences to fill the remaining places.

Alternatively, you can formulate it as a linear programming or minimum cost flow problem, and solve it with a solver or a dedicated algorithm for those.

Improve this answer
$\endgroup$
6
  • $\begingroup$ For the answer that @nirsahar gave, how can I use it to get the best possible allocation? I checked the link for wikipedia and I did not understand it? $\endgroup$
    – Tom Finet
    Jun 5 '20 at 15:33
  • $\begingroup$ I don't think you can, as their solution only handles capacities, not costs. For the best possible allocation, you can modify it with $w_{ij}$ costs on the edges, which gives you the minimum cost flow problem I mentioned above $\endgroup$
    – Gabriel Gouvine
    Jun 5 '20 at 15:43
  • $\begingroup$ If you want to implement it yourself, the approach using the assignment problem should be a lot easier $\endgroup$
    – Gabriel Gouvine
    Jun 5 '20 at 15:45
  • $\begingroup$ Yes, but couldn't you just add a cost for every node on top of the capacity $\endgroup$
    – Tom Finet
    Jun 5 '20 at 16:07
  • $\begingroup$ I thought the assignment problem approach uses the network flow approach $\endgroup$
    – Tom Finet
    Jun 5 '20 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.