Wednesday, October 17, 2018

The Muffin Problem



We are asked to split \(m=5\) muffins between \(s=3\) students, such that each student gets in total \[\frac{m}{s} = \frac{5}{3}\] worth of muffins [1]. From [2] we see two possible ways of doing this:

Allocation 1 (from [2])

Allocation 2 (from [2])

(I believe Proc means Protocol). The problem is to find a way to divide the muffins such that the smallest piece is maximized.

There is a nice and simple MIP formulation for this. Let's define \(x_{i,j} \in [0,1]\) as the fraction of muffin \(i\) assigned to student \(j\). Also we need: \[\delta_{i,j} = \begin{cases} 1 & \text{if $x_{i,j} \gt 0$} \\ 0 & \text{if $x_{i,j}=0$}\end{cases}\] Then we can write:


Muffin Problem
\[\begin{align}\max\> & \color{DarkRed} z \\ & \sum_i \color{DarkRed} x_{i,j} = \color{DarkBlue} {\frac{m}{s}} && \forall j\\ & \sum_j \color{DarkRed} x_{i,j} = 1  && \forall i\\ & \color{DarkRed} \delta_{i,j} = 0 \Rightarrow \color{DarkRed} x_{i,j} = 0 \\ & \color{DarkRed} \delta_{i,j} = 1 \Rightarrow \color{DarkRed} z \le \color{DarkRed} x_{i,j} \\ & 0 \le \color{DarkRed} x_{i,j} \le 1\\ & \color{DarkRed} \delta_{i,j} \in \{0,1\}\end{align}\]

The objective takes care of \(x_{i,j}=0 \Rightarrow \delta_{i,j}=0\). Some MIP solvers allow us to use the implications directly (as so-called indicator constraints). For others we need to reformulate. It is not difficult to rewrite them as inequalities:

ImplicationInequality
\[\color{DarkRed} \delta_{i,j} = 0 \Rightarrow \color{DarkRed} x_{i,j} = 0 \]\[\color{DarkRed} x_{i,j} \le \color{DarkRed} \delta_{i,j}\]
\[\color{DarkRed} \delta_{i,j} = 1 \Rightarrow \color{DarkRed} z \le \color{DarkRed} x_{i,j} \]\[\color{DarkRed} z \le \color{DarkRed} x_{i,j}+ (1-\color{DarkRed} \delta_{i,j})\]


This is similar to what is proposed in [1] (they use \(y_{i,j} = 1-\delta_{i,j}\)) and somewhat simpler than the approach used in [3].

The results are:

----     26 VARIABLE x.L  fraction of muffin assigned to student

           student1    student2    student3

muffin1       0.500                   0.500
muffin2       0.583       0.417
muffin3                   0.417       0.583
muffin4       0.583       0.417
muffin5                   0.417       0.583


----     26 VARIABLE d.L  indicator for nonzero x

           student1    student2    student3

muffin1       1.000                   1.000
muffin2       1.000       1.000
muffin3                   1.000       1.000
muffin4       1.000       1.000
muffin5                   1.000       1.000


----     26 VARIABLE z.L                   =        0.417  smallest nonzero x


If student1 arrives early and confiscates muffin1, we can fix \(x_{\text{muffin1},\text{student1}}=1\). With this we can reproduce the first solution:


----     28 VARIABLE x.L  fraction of muffin assigned to student

           student1    student2    student3

muffin1       1.000
muffin2                   1.000
muffin3       0.333       0.667
muffin4                               1.000
muffin5       0.333                   0.667


----     28 VARIABLE z.L                   =        0.333  smallest nonzero x

A solution for 7 muffins and 5 students can look like:


----     26 VARIABLE x.L  fraction of muffin assigned to student

           student1    student2    student3    student4    student5

muffin1       0.667       0.333
muffin2       0.333                   0.667
muffin3       0.400       0.600
muffin4                               0.333       0.333       0.333
muffin5                   0.467                               0.533
muffin6                                           0.467       0.533
muffin7                               0.400       0.600


----     26 VARIABLE z.L                   =        0.333  smallest nonzero x

Not all problems are super easy to solve to proven optimality. E.g. with 11 muffins and 9 students, I had to spend several minutes. As usual the solver quickly found the optimal solution, but proving optimality was not so quick. There is lots of symmetry in the model. That may be something to exploit.

References