The Joy of Baking (Optimally)

‘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 10-cubic-foot (cf) oven and we need to bake five items. The baking times (in minutes) are 20, 25, 40, 30, and 30. The space requirements in cf are, respectively, 6, 4, 5, 6, 4. If the time at which we begin baking item i is denoted by the variable s_i, we can write the following in a CP model:

\mathrm{cumulative}([s_1,s_2,s_3,s_4,s_5],[20,25,40,30,30],[6,4,5,6,4],10)

The above constraint makes sure that the start times s_i are such that the capacity of the oven is never exceeded. To minimize the makespan, we have to minimize the maximum among s_1+6, s_2+4, s_3+5, s_4+6, and s_5+4.

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 r_i (i.e. a lower bound) to the appropriate variable: r_i \leq s_i.
  • If a given item does not occupy the entire oven, but you still prefer to bake it alone, just artificially increase its space requirement c_i to be equal to the oven’s capacity C.
  • 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 i must be finished before item j starts baking (e.g. they need different temperatures), just include the constraint s_i + p_i \leq s_j, where p_i is the baking time of item i.

We could, of course, have approached this problem from an Integer Programming point of view. In that case, we’d have binary variables x_{it} that are equal to 1 if you start baking item i at time t, 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)


11 Comments

Filed under Applications, Constraint Programming, CuSPLIB, Food, Holidays, INFORMS Monthly Blog Challenge, Integer Programming, Modeling, People

11 responses to “The Joy of Baking (Optimally)

  1. 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!

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

  3. Laura

    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.

  4. orbythebeach

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

  5. 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.

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

  7. orbythebeach

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

  8. 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.

  9. Cara

    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.

  10. orbythebeach

    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.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s