So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils assigned to the activity change. (So in block 1 pupil x takes part in activity a and in the second block in activity d).

Before this day starts, we give make lists in which each pupil can tell us his 3 (or 4) favorite activities (he only takes part in two of them, these again are ordered from most "favorite" to least) in which he wants to take part. Now our job is to assign these pupils in a way that we have the best overall satisfaction among the pupils (so everybody did more or less did get his/her chosen activities).

What would be a good algorithm to solve this? Is there any way to do this, apart from calculating such a "satisfaction" value for each possible solution?

An optional feature would be that if someone can't get in to his/her project, they would get into a similar one according to some predefined distance.

  • $\begingroup$ What have you tried? SAT or ILP are two natural approaches. Simulated annealing might work too. You should also look at the traditional marriage algorithm for matching; it might be applicable here. $\endgroup$ – D.W. Jul 18 '14 at 6:03
  • 1
    $\begingroup$ This is an assignment problem similar to the marriage problem. Try searching with these buzzwords! $\endgroup$ – Raphael Jul 18 '14 at 7:25

Here is partly a solution, partly an approximation:

Let $T$ denote set of time blocks. Let $C$ denote set of children. Let $A$ denote set of activities.

Let $T_i$, $C_i$, $A_i$ denote $i$-the time block, child, activity. Let $S_{ij}$ denote the satisfaction for child $i$ from activity $j$. Let $M_j$ denote maximum number of pupils that can participate in $j$-th activity.

  1. Create a bipartite graph where pupils are on the left side and activities are on the right.
  2. For each pupil $C_i$ and activity $A_j$ create an edge with capacity equal to 1 and cost equal to $-S_{ij}$.
  3. Create a source and connect it to all $C_i$, capacity equal to $|T|$.
  4. Create a sink and connect all $A_j$ to sink, with capacity equal to $M_j * |T|$.
  5. Find minimum cost maximum flow on this graph.
  6. Now for each pupil you have assigned number of activities equal to the number of time blocks. If there exists a valid assignment of activities to pupils, the algorithm above will surely find some (not necessarily valid) assignment.

Let $P_j$ denote number of pupils that were assigned to $j$-th activity after the algorithm above.

Now, for the approximation part:

  1. Let's create a grid of $|T|$ rows and $|A|$ columns, $i$-th row denoting all activities that will happen during $i$-th time interval.
  2. Let's fill in our table. We will loop through it's columns, and for a column, we will loop from top to the bottom of the row. In parallel let's loop through all activities in some order. For activity $j$ let's put into the next cell of the table $j$ activity and move to the next cell, total of $P_j$ times for $j$ activity.
  3. Since $P_j \le M_j * |T|$, in each row of the table there will be at most $M_j$ entries of $j$-th activity, satisfying the condition that during one time interval only $M_j$ persons can participate in $j-th$ activity.
  4. Each row should have some permutation of pupils. Let's for each for find maximum matching between pupils and and activities in some row. Two problematic situations might occur:

    • Pupil is assigned to the same activities in different time blocks. We can overcome this in two possible ways:

      a. Once pupil was assigned to some activity in one row, don't connect the appropriate pupil vertex to the appropriate activity vertex in the following rows.

      b. Who ever said that satisfaction decreases if you participate in your favorite activity again? ;)

    • For some rows, we may not find perfect matching. Well, this is why it is an approximation, not a solution. since it is maximum matching, we will still find for many pupils their preferred activities from first part. For others, we can match them with other activities in a row.

Possible heuristics:

Match pupils in a row not using bipartite matching, but using Hungarian algorithm (for perfect maximum weighted matching, with weights equal to $S_{ij}$, where $j$ is activity in the appropriate cell in a row.

Try different orderings when creating a grid. For example, we may try to use simulated annealing based on the permutation of order, in which we put activities to the grid, and transition between steps that results in a swap of neighboring / any two elements in this permutation.


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.