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?


Your Answer

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

Browse other questions tagged or ask your own question.