1
$\begingroup$

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?

$\endgroup$

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.