‘Tis the season of baking all kinds of things: cookies, cakes, breads, brownies, pies, and my favorite Brazilian dessert “*pudim de leite moça*“, which is depicted below. Click here for the step-by-step recipe.

Many OR bloggers, such as Laura McLay and Anna Nagurney, actually enjoy baking, and they both have written posts on the subject (e.g. here and here). I happen to include myself in this group and, yes, I made the *pudim* shown above (using my mom’s recipe).

My goal today is to approach the art of baking from an optimization point of view. Let’s say you have a long list of items to bake. Perhaps you’re hosting a mega party at your house, or you’re helping your local church or favorite charity with their holiday cooking. You have an oven that can only fit so much at a time (think of area, or volume). Each item to be baked occupies some space in the oven and needs to bake for a specific amount of time. In what order should you bake your items so that you finish as soon as possible? (Side note: it may not be obvious at first sight, but this is the same problem faced by a container port that needs to decide the order in which to unload cargo ships.)

In the OR world, this is a *job scheduling* problem with a *cumulative* machine. The jobs are the tasks to be performed (items to bake), the machine (or resource) is the oven. We say the oven is cumulative, as opposed to disjunctive, because it can deal with (bake) multiple items at a time. The unknowns in this optimization problem are the start times of each job (when to begin baking each item). The objective is to minimize the *makespan*, which is defined as the finish time of the last job (the time at which it’s OK to turn off the oven). Finally, this is a *non-preemptive* problem because, typically, once you start baking something, it stays in the oven until it’s done.

This problem occurs so often in practice that the Constraint Programming (CP) community created a global constraint to represent it. It’s called the *cumulative* constraint (what a surprise!). Here’s a reference. For example, let’s say that we have a -cubic-foot (cf) oven and we need to bake five items. The baking times (in minutes) are , , , , and . The space requirements in cf are, respectively, , , , , . If the time at which we begin baking item is denoted by the variable , we can write the following in a CP model:

The above constraint makes sure that the start times are such that the capacity of the oven is never exceeded. To minimize the makespan, we have to minimize the maximum among , , , , and .

It’s easy to incorporate some real-life details into this model. For example:

- Not every item will be ready to go into the oven at time zero. After all, you’re making them as you go. To take care of this, add a ready-time (i.e. a lower bound) to the appropriate variable: .
- If a given item does not occupy the entire oven, but you still prefer to bake it alone, just artificially increase its space requirement to be equal to the oven’s capacity .
- If you’re baking both savory and sweet things, you probably don’t want to mix them up in the oven. In that case, simply solve the problem twice.
- If, for some reason, item must be finished before item starts baking (e.g. they need different temperatures), just include the constraint , where is the baking time of item .

We could, of course, have approached this problem from an Integer Programming point of view. In that case, we’d have binary variables that are equal to 1 if you start baking item at time , and equal to zero otherwise. For more details on this formulation, including model files and some pretty tough instances, take a look at the CuSPLIB web page.

In the spirit of holiday baking, I will close with some pictures of past baking jobs ran on my house’s machine (a.k.a. oven). Enjoy! :-)

**Key Lime Pie**

**Carrot Oatmeal Cookies (recipe here)**

**Sparkling Ginger Chip Cookies (recipe here)**

**Irish Soda Bread**

**Six-Seed Soda Bread (recipe here)**

Someone the Drools mailing list was using Drools Planner to optimize

beer brewing.In reality though, I ‘ve been told the cooks will never let a mathematical formula generate food for production use. But toothpaste however, made by chemists instead of cooks, is a whole different story: they already use optimization software to invent new toothpaste variants in production!

Pingback: Tweets that mention The Joy of Baking (Optimally) | O.R. by the Beach -- Topsy.com

Great post! I like to bake many things in tandem (hey, it’s efficient), so I thoroughly enjoyed your constraint programming approach. I can’t help but think of OR every time I cook multiple batches of cookies at once. Unfortunately, your beautiful pictures have made me insanely hungry.

Laura: they make me hungry too. I had an extra large serving of cereal this morning because I revised the post before breakfast.

Hello Laura

I once set an examination question for CPA which was concerned with scheduling cooking two desserts. Both were real recipes. One had layer A on top of layer B, the other had layer B on top of layer A, with different fillings. It was a simple problem to solve under exam conditions, but just complex enough to sort out those who understood CPA and those who didn’t. No real cookery knowledge was assumed; it was just a change from industrial problems.

Nice photos, Tallys. If you’re done with the props, I’ll be happy to take them off your hands.

Thanks, Paul! Unfortunately, they all had to pass a very stringent quality control step and ended up being devoured in the process.

I can’t bake at all, but as I looked at your wonderful pictures, I realized that my specialty is consumption. Very nice holiday greetings you sent with the photos.

For items that need different temperatures, you could use a state function if you were using ILOG CP Optimizer. Not sure if that is a standard feature of CP as I have only used ILOG tools for CP. The state function reflects the fact that your resource (the oven) can change state (temperature) over time, and you can have constraints that say certain items require a certain temperature.

Cara: thank you for the tip. I wasn’t aware of this feature. If I had to guess, I’d say this is not standard in most CP solvers.

Pingback: INFORMS Optimization Society Conference 2nd Call for Abstracts, Posters, and Participation | O.R. by the Beach