# Assign $m$ tasks to $n$ workers, with $m \geq n$

There are $n$ students that share the same apartment. At each evening, one of them must prepare dinner for everyone. There are $m$ evenings to schedule, with $m \geq n$, and you have to assign any singular evening to one student at a time.

In particular, student $i$ is disposed to accept cooking for $c_i$ evenings, with $1 \leq c_i \leq m$. Let $S$ be the global set of evenings (eg. $S=\{1,2,3,4,5\}$), for every student we define also $S_i \subseteq S$: you may assign evening $j$ to student $i$ only if $j \in S_i$.

So, given $m, n, c_i, S_i$, you have to define an algorithm that assigns each single evening to an available student.

I think a solution can be found using linear programming, although seems a little tricky. Let $x_{ij}$ be defined as follows:

$$x_{ij} = \begin{cases} 1 & \hbox{if evening } j \hbox{ is assigned to student } i \\ 0 & \hbox{otherwise} \end{cases}$$

Then you have such constraints. Student $i$ can accept a max. of $c_i$ evenings, so: $$\begin{array}{cr} \sum_j x_{ij} \leq c_i & \hbox{ for every student } i \cr \end{array}$$ You have to ensure that every evening is assigned to a student only, then: $$\begin{array}{cr} \sum_i x_{ij} = 1 & \hbox{ for every evening } j \cr \end{array}$$ Now a way to include $S_i$ in the constraints is required. Before doing it we define: $$p_{ij} = \begin{cases} 1 & \hbox{if evening } j \notin S_i \\ 0 & \hbox{otherwise} \end{cases}$$ So last constraints are: $$\begin{array}{cr} \sum_j x_{ij} \cdot p_{ij} = 0 & \hbox{ for every student } i \cr \end{array}$$ Suppose you have $5$ evenings, with $S_i=\{2,4,5\}$. You'll have the constraint $x_{11} + x_{13} = 0$. Since it's a linear program, we have $x_{ij} \geq 0$ so the equivalence is satisfied only if terms are all zeros, i.e. those evenings ($1$ and $3$) are not assignable to that student.

I have some doubt with the objective function, that it should be the sum of every $x_{ij}$. Should we maximize or minimize, or are they the same for this model? We could also put a constraint to say that such sum must be equal to $m$ (the total amount of evenings to assign), but i think it's not mandatory since it's guaranteed by previous constraints. What do you think about?

Is there a better way to solve such problems?

• I think a max-flow algorithm should work. – AndyG Jan 12 '16 at 22:06
• – D.W. Jan 13 '16 at 0:40
• @AndyG That's like saying "I think an LP should work". – Raphael Jan 13 '16 at 7:02
• @D.W. Any duplicate among those? – Raphael Jan 13 '16 at 7:02
• @Raphael: Yes, solving max-flow can be accomplished with an LP, but OP did not formulate is as such. Approach from a simplex algorithm perspective may make less sense than Hungarian, for example. – AndyG Jan 13 '16 at 13:51