'The Muffin Problem' is a recreational maths puzzle that is simple to state but hard to solve in general. For example:

You have 11 muffins and 6 students. You want to divide the muffins equally between the students, but no student wants a small piece. How should you slice the muffins to maximize the size of the smallest piece?

We're one muffin short of giving each student two whole muffins. An obvious solution is to give each student one whole muffin. Then slice 1/6 from each of the five remaining muffins, giving 5/6 muffin to five students and 5 x 1/6 muffin to the sixth student. Therefore, each student gets 1 + 5/6 muffins. In this solution, the smallest slice is 1/6 muffin. But is that the maximum size we can make the smallest slice?

Spoiler alert: it isn't. Have a go at working out a way to slice the muffins that maximizes the size of the smallest slice while giving each student an equal share of the total. Note that we assume each muffin is circular and they are sliced from the edge to the centre. In this small example, finding a good solution is straightforward. Finding an optimal solution is more difficult. In many cases, proving that a solution is optimal is very difficult.

In this article, we solve The Muffin Problem using a Mixed Integer Linear Program (MILP) for a range of combinations for the number of muffins and the number of students. A MILP is not the most efficient method for solving this problem, but it illustrates a way to approach many types of recreational maths puzzles. Along the way, we explore using fractions in a Python program, speed up the process by solving optimization model instances in parallel, include symmetry-breaking constraints and objective function bounds, and we eat a few muffins – purely for research purposes, of course.

To continue reading the article, download the model and understand the formulation of this problem continue reading on the Solver Max website. You will find there many other fantastic optimization materials, optimization models and a great collection of similar websites.