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 Procedure). 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:
| Implication | Inequality |
|---|---|
| \[\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
- Guangiqi Cui, John Dickerson, Naveen Durvasula, William Gasarch, Erik Metz, Jacob Prinz, Naveen Raman, Daniel Smolyak, Sung Hyun Yoo, The Muffin Problem, 13 Mar 2018, https://arxiv.org/pdf/1709.02452.pdf
- https://www.cs.umd.edu/~gasarch/muffintalk.pdf
- https://math.stackexchange.com/questions/2958179/how-to-prove-that-1-3-is-the-optimal-solution-for-the-muffin-problem-with-5-stud
- NRC (Dutch newspaper), https://www.nrc.nl/nieuws/2018/09/14/hoe-vijf-muffins-tot-een-diep-wiskundig-vraagstuk-leidden-a1616534
No comments:
Post a Comment