Category Archives: INFORMS Monthly Blog Challenge

Choosing Summer Camps for Your Kids

Today I’m going to write about a decision that’s made by many American families each year: how to pick summer camps for our kids. There are several issues to take into account, such as cost, benefit, hours, and kids’ preferences. I’ll introduce an optimization model for summer camp selection through a numerical example. The example portrays a large family, but the same ideas apply if a few smaller families want to get together and solve this problem. This way they can take advantage of the discounts and take turns driving the kids around.

The Joneses have six kids: Amy, Beth, Cathy, David, Earl and Fred (yes, their first names are alphabetically sorted, matching their increasing order of age; Mr. and Mrs. Jones always knew they’d have six kids and hence named their firstborn with an ‘F’ name). This year, they’ve narrowed down their list of potential summer camps to the following ten: Math, Chess, Nature, Crafts, Cooking, Gymnastics, Soccer, Tennis, Diving, and Fishing. The Nature camp takes kids on a hike through the woods with the guidance of a biologist; they make frequent stops upon encountering specific plants and animals, during which a mini science lecture is delivered (pretty cool!). The Cooking camp involves cooking chemistry instruction, à la Alton Brown (also pretty cool).

The following table contains some data related to each camp:

The Cost column indicates the cost per child. The Discount column indicates the percentage discount that each child enrolled after the first would receive on the cost of each camp. For instance, if three children are enrolled in Math camp, the first would cost $1100, and the second and third would cost $770 each (30% less). The Hours column is self-explanatory and the last two columns indicate whether or not that particular camp develops mental and physical abilities, respectively (a value of one = yes, zero=no).

The next table shows some of the child-specific requirements:

For example, the Joneses want Fred to attend at least 3 camps that develop mental abilities, and at least 1 camp that develops physical abilities. The last two columns in the above table indicate the minimum and maximum number of camp hours for each child over the 9-week summer break.

The next thing parents need to take into account are their children’s preferences. So here they are:

The smaller the number in the above table, the more desirable a particular camp is. For example, Amy is a bit of a math nerd, and if we were to flip David’s preference scores for Math and Tennis, he could be classified as a bit of a jock. Some conflicts exist, in the sense that not all camps are compatible with each other in terms of time schedules. In this particular case, let’s assume that no child can attend both the Soccer and Tennis camps, or both the Nature and Soccer camps. Here’s how we are going to use this preference table to create a sense of fairness among the children: whenever a child that prefers camp X to camp Y goes to camp Y and doesn’t go to camp X, nobody else gets to go to camp X either. For example, if Amy goes to Nature camp and isn’t sent to either Math or Chess camp, none of her siblings are allowed to go to Math or Chess either. Conversely, if the Joneses decide to send Earl to Chess camp and Fred to Tennis camp, they must also send Earl to Tennis camp (because Earl prefers Tennis to Chess, and “Fred is going! Why can’t I go too!”). Clearly, there are other ways to use/interpret this table, such as trying to send everyone to at least one of their top N choices, but we won’t consider those alternatives here.

After taking all of the above issues and conditions into account, here’s a solution that satisfies all the requirements while resulting in the minimum cost of $22,180.00 (You guessed it…the Joneses are probably *not* among the 99%):

Amy goes to Math, Crafts, Cooking, and Tennis; Beth goes to Math, Cooking, Tennis, and Fishing; Cathy goes to Math, Crafts, Tennis, and Fishing; David goes to Math, Cooking, and Fishing; Earl goes to Math, Tennis, and Fishing; and Fred goes to Math, Crafts, Cooking, and Tennis. Mmm…interestingly, everyone goes to Math camp. I think the Joneses are on to something…

Depending on your own requirements, preferences, and costs your solution may differ, of course. But this should give you an idea of how this simple problem can easily become very complicated to solve. No need to fear, though! Operations Research is here!

Food for Thought: Here’s an interesting question that helps illustrate how high-quality solutions can be counterintuitive: by looking at the preferences table, we see that everyone prefers Soccer to Tennis. In addition, Soccer camp is less expensive than Tennis camp. So how come we send almost everyone to Tennis camp? Isn’t that strange? Let me know what you think in the comments below! That’s one of the advantages of using an analytical approach to decision making: it helps us find solutions we wouldn’t even consider otherwise because they don’t seem to make sense (at least not at first).

If you’re curious about how I managed to find the optimal solution, read on!

Details of the Analysis:

To find the minimum-cost solution, we can create a mathematical representation of the problem, a.k.a. a model, and then solve this model with the help of a computer. Let’s see how.

The first obvious decision to make is who goes where. So let the binary variable x_{ij} equal 1 when child i goes to camp j, and equal to 0 otherwise. We’ll also need another binary variable y_j that is equal to 1 when at least one child goes to camp j and equal to 0 when none of the children go to camp j. We are now ready to write our objective function and constraints. I’ll refer to the problem data using the column headings of the tables above. The subscript i will always refer to a child, and the subscript j will always refer to a camp.

To minimize the total cost, we write the following objective function:

\displaystyle \min \sum_i \sum_j (1-\mathrm{Discount}_j)\mathrm{Cost}_j x_{ij} + \sum_j \mathrm{Discount}_j \mathrm{Cost}_j y_j

Note how we are using the y_j variable to handle the discount for sending more than one child to camp j: we charge every child the discounted price in the double summation and add the discount back in only once if y_j=1.

Now we have to deal with the four requirements: minimum and maximum hours, mental activity, and physical activity. For every child i, we have to write the following four constraints:

\displaystyle \sum_j \mathrm{Hours}_j x_{ij} \geq \mathrm{MinTimeReq}_i

\displaystyle \sum_j \mathrm{Hours}_j x_{ij} \leq \mathrm{MaxTimeReq}_i

\displaystyle \sum_j \mathrm{IsMental}_j x_{ij} \geq \mathrm{MentalReq}_i

\displaystyle \sum_j \mathrm{IsPhysical}_j x_{ij} \geq \mathrm{PhysicalReq}_i

Next, we enforce the preference rules. Let’s recall the example involving Earl and Fred: if Earl goes to Chess camp and someone else (it doesn’t matter who) goes to Tennis camp, then Earl has to go to Tennis camp as well. Here’s what this constraint would look like:

x_{\mathrm{Earl},\mathrm{Chess}} + y_{\mathrm{Tennis}} - x_{\mathrm{Earl},\mathrm{Tennis}} \leq 1

Of course, we have to repeat this constraint for every child i and every pair of camps j_1 and j_2 such that child i prefers j_1 to j_2 in the following way:

x_{ij_2} + y_{j_1} - x_{ij_1} \leq 1

The camp compatibility constraints say that no child i can attend both Soccer and Tennis, or both Nature and Soccer, therefore:

x_{i,\mathrm{Soccer}} + x_{i,\mathrm{Tennis}} \leq 1

x_{i,\mathrm{Nature}} + x_{i,\mathrm{Soccer}} \leq 1

Finally, we need to relate the x_{ij} and y_j variables by stating that unless y_j=1 , no x_{ij} can be equal to 1 . So we write the following constraint for all values of i and j :

x_{ij} \leq y_j

And that’s the end of our model. Here’s a representation of this mathematical model in AMPL in case you want to play with it yourself. This is the model I used to obtain the numerical results reported above. Enjoy!

5 Comments

Filed under Modeling, Integer Programming, Applications, Mathematical Programming, Motivation, Promoting OR, INFORMS Monthly Blog Challenge, Summer camp

Can We Use Social Networks to Identify Poor Decision Making?

While suffering through the usual air travel woes recently, I felt compelled to tweet my feelings:

I was pleasantly surprised to see that Paul Rubin and Matthew Saltzman followed up with an interesting exchange:

Although I tend to agree with Paul that an outsider probably does not have enough information to decide whether or not the actions he/she sees are reasonably good given the situation (especially when it comes to the incredibly complex world or airline operations), I like Matthew’s general idea of an experiment to identify whether or not the outcome of a black-box decision making process is “good”.

Can that be done? Can we observe a black-box situation (or process) long enough to be able to tell whether the analytic machine inside the box could do better?

A large number of people carry smart phones these days, with constant connectivity to the internet. Twitter, Facebook, and FourSquare (to name a few) can determine our location, and there are other Apps that tell us which of our friends (and even non-friends) are close by. With all of this connectivity and location awareness, we can think of human beings as sophisticated sensors that collect and share information. We see a fire, a car accident, a traffic jam, an arrest, a fight, and immediately share that information with our network. In addition, human sensors are much better than electronic sensors because they can detect and interpret many other things, such as: the mood in a room (after the airline changes your gate for the third time), the meaning of an image, and so on.

Consider a hypothetical situation in which a crowded venue has to be evacuated for whatever reason. Perhaps some exits will be blocked and people will be directed to go certain places, or act a certain way. Human observers may notice a problem with the way security is handling the situation from multiple locations inside the venue, and from multiple points of view. The collection of such impressions (be they tweets, Facebook status updates, or something else) may contain clues to what’s wrong with the black-box evacuation procedure devised for that venue. For example, “avoid using the south exit because people exiting through there bump into those coming down the stairs from the second floor and everyone has to slow down quite a bit.”

In a world where Analytics and OR specialists struggle to convince companies to try new ideas, could this kind of evidence/data be used to foster collaboration? “I noticed that you did X when Y happened. It turns out that if you had done Z, you’d have achieved a better outcome, and here’s why…”

Is the airline example really too complicated to be amenable to this kind of analysis? I’m not sure. But even if it is, there may be other situations in which a social network of human sensors can collect enough information to motivate someone to open that black box and tinker with its inner workings a little bit. Those of you working in the area of social networks might be aware of something along the lines of what I (with inspiration from Matthew) have proposed above. If that’s the case, I’d love to read more about it. Please let me know in the comments.

1 Comment

Filed under Applications, INFORMS Monthly Blog Challenge, People, Social Networks, Travel

Rescue Mission, Part 3 of 3

Make sure to read part 1 and part 2 first!






Notes:

The Edelman Award presentations are available here.

The INFORMS Public Information Committee (PIC) web page is here.

A long list of real-life applications of Analytics and O.R. is available here.

The topographic maps above are actual maps of Mars.

2 Comments

Filed under Applications, Heuristics, INFORMS Monthly Blog Challenge, Promoting OR

Rescue Mission, Part 2 of 3

Make sure to read part 1 first!





TO BE CONTINUED… Read part 3 here!

Notes:

The paper by Trick et al. is available here.

The Science of Better podcasts are available here.


Leave a comment

Filed under Applications, Heuristics, INFORMS Monthly Blog Challenge, Promoting OR

Rescue Mission, Part 1 of 3







TO BE CONTINUED…  Read part 2 here!

Note: The topographic map above is an actual map of Mars.


1 Comment

Filed under Applications, Heuristics, INFORMS Monthly Blog Challenge, Promoting OR

Should You Hire Security When Tenting Your House?

Last week I had my house tented because of termites. For those of you who don’t know what “tenting” is (I didn’t until about a year ago), it amounts to wrapping an entire house inside a huge tent and filling the tent with a poisonous gas that kills everything inside (and by everything I really do mean everything). Those who have been through this experience know what a hassle it is. We received a to-do list of pre-tenting tasks, which included:

  • Remove or discard all food that isn’t canned or packaged in tightly-sealed, never-opened containers
  • Turn off all A/C units and open one window in each room of the house
  • Open all closet and cabinet doors
  • Turn off all internal and external lights (including those operating on a timer)
  • Prune/move all outdoor plants away from the house to have a clearance of at least 18 inches
  • Soak the soil around the house (up to a foot away from the structure) on the day of the tenting
  • Warn your neighbors about the tenting (so that they can keep their pets away from the house)
  • etc.

We had to sleep two nights in a hotel, with two dogs, one of which had just had knee surgery. What an adventure!

The main point of concern was that the house would stay vulnerable (open windows) and unattended during the process. On top of that, one of our neighbors told us that he knew of a house that had been robbed during tenting a couple of months ago. So we started to consider hiring a security guard to sit outside the house for 48 hours. Would that be a good idea? Let’s think about this.

Our insurance’s deductible is $2500. I assume that if thieves are willing to risk their lives (wearing gas masks; oh yeah! they do that!) to enter a tented house, they’d steal more than $2500 worth of stuff. Therefore, being robbed would cost us $2500. This doesn’t take into account that one might have irreplaceable items in the house. However, most of the time those can be taken with you (unless they are too big or inconvenient to carry). In my case, I took the external hard drive to which I back up my data, and the mechanical pencil I’ve owned and used since 1991 (yes, you guessed right, the eraser at the end doesn’t exist any more). The security company we called would charge $15 per hour for an unarmed guard to be outside our house. Multiplying that by 48 hours brings the cost of hiring security to $720.

Let’s say that the likelihood (a.k.a. probability) of being robbed while your house is tented without a security guard is p_1 (in percentage terms; for example, p_1 for the White House is pretty close to 0%), and when a security guard is on duty that likelihood is p_2. Unless p_1 > p_2, there’s no point in having this entire discussion, so I’ll assume that is true. Here’s a pretty neat rule of thumb that you can use: divide the cost of hiring security by your deductible to get a number n between zero and one (of course, if hiring a guard costs more than your deductible, don’t do it!). Unless the presence of the guard reduces your chance of being robbed (p_1) by more than n, you should not hire security! (Later on, I’ll explain where this rule comes from.) For example, in my case 720/2500 is approximately equal to 29%. If the chance of being robbed without security is 30%, unless hiring a guard brings that chance down to 1% or less, it’s better not to do it. If the value of p_1 is less than or equal to 29% to begin with (I live in a reasonably safe neighborhood), the answer is also not to hire security (probabilities cannot be negative). This rule works regardless of the value of p_1; what matters is how great the improvement to p_1 is.

In addition to looking at the numbers, we also took into account the following clause from the security company’s contract:

…the Agency makes no warranty or guarantee, including any implied warranty of merchantability or fitness, that the service supplied will avert or prevent occurrences or the losses there from which the service is designed to detect or avert.

In other words, if you hire us (the security company) and still get robbed, we have nothing to lose!

So what did we do? We chose not to hire security and, fortunately, our house was not robbed. However, even though the tenting instructions  say that you don’t have to wash your glasses and plates after returning home, we decided to do so anyway (as they say in Brazil: “seguro morreu de velho”).

Disclaimer: The advice contained herein does not guarantee that your house will not be robbed. Use it at your own risk!

Details of the Analysis

So where does that rule of thumb come from? We can look at this problem from the point of view of a decision tree, as pictured below.

In node 0, we make one of two decisions: hire a security guard (payoff = -$720, i.e. a cost), or not (payoff = -$0). For each of those decisions (branches), we create event nodes (1 and 2) to take into account the possibility of being robbed. At the top branch of the tree (node 2), the house will be robbed with probability p_2, in which case we incur an additional cost of $2500, and the house will be safe with probability (1-p_2), in which case we incur no additional expense. Therefore, the expected monetary value of hiring security, which we call EMV_2, is to spend $720+$2500 with probability p_2, and to spend $720 with probability (1-p_2). Hence

EMV_2 = - 3220p_2 - 720(1-p_2) = - 2500p_2 - 720

Through a similar analysis of the bottom branch (node 1), we conclude that the expected monetary value of not hiring security, which we call EMV_1, is to spend $2500 with probability p_1 and to spend $0 with probability (1-p_1). Therefore

EMV_1 = -2500p_1 - 0(1-p_1) = - 2500p_1

Hiring security will be the best choice when it has greater expected monetary value than not hiring security, that is when EMV_2 > EMV_1, which yields

-2500p_2 - 720 > -2500p_1

\Downarrow

2500(p_1 - p_2) > 720

\Downarrow

p_1 - p_2 > \frac{720}{2500}

which is the result we talked about earlier (recall that p_1 > p_2).

How Does Analytics Fit In?

The Analytics process is composed of three main phases: descriptive (what does the data tell you about what has happened?), predictive (what does the data tell you about what’s likely to happen?), and prescriptive (what should you do given what you learned from the data?). In this problem we can identify a descriptive phase in which we try to obtain probabilities p_1 and p_2. This could be accomplished by looking at police or insurance company records of robberies in your area. It’s not always possible to get a hold of those records, of course, so one might need to get a little creative in estimating those numbers. Having knowledge of the probabilities, the calculation described above could be classified as a prescriptive phase: what’s the course of action? Hire security if (cost of security)/(insurance deductible) < p_1 - p_2. There is no predictive phase here because our analysis does not require the knowledge of any future event (only how likely it is to occur). Operations Research can be used in some or all of these phases. Most of what I do in my research and consulting projects lies in the prescriptive phase (optimization). Recently, however, I’ve decided to broaden my horizons and learn more about the other two phases as well, starting with some self-teaching of data mining.

13 Comments

Filed under Analytics, Applications, Decision Trees, INFORMS Monthly Blog Challenge, Security

Find Out What Happens to Mr. Lovr

I’ve had a number of people tell me that they like my Valentine’s Day post, but many of them did not solve the Excel Spreadsheet. That’s the most important part of the post! You have to see what happens to Mr. Lovr! There’s no set-up necessary; just open Excel Solver (it’s an add-in you have to enable in Windows and a separate program in the Mac), and click on the “Solve” button. You’ll be glad you did.

Leave a comment

Filed under INFORMS Monthly Blog Challenge, Love, Valentine's Day

Transporting Flowers with Love

Mr. Lovr, a lonely gentleman, does not want to spend Valentine’s day alone in 2011. As one of his New Year’s resolutions, he intends to send roses to nine of his lady friends. Being an avid procrastinator, however, he waits until the last minute and finds out that only eight flower shops in his city still have roses available. For lack of better names, let’s call those flower shops F1, F2, F3, …, F8. The number of bouquets of roses available at each shop are, respectively, 4, 4, 3, 2, 2, 2, 2, and 1. Based on how well he knows each of his potential valentines, whom we’re going to call V1, V2, V3, …, V9, he calculates how many bouquets he needs to send to each of them to increase his chances of going on at least one date. The numbers are, respectively, 3, 2, 2, 2, 2, 2, 2, 2, and 3. At this point, a light bulb goes off in Mr. Lovr’s head, and he remembers from his Operations Research class that this is a transportation problem. But there’s something missing…Ah! The costs! He calls each of the eight flower shops and asks how much it would cost to ship one bouquet of roses to the addresses of each of his nine lady friends. He then compiles the following table of costs (in dollars):

He also remembers that because the total supply is equal to the total demand, he can write all of the constraints in this problem as equalities. Essentially, he has to say that, for each flower shop, the number of bouquets that it ships has to be equal to the number of bouquets that it has. Similarly, he needs one constraint for each valentine saying that the number of bouquets that they receive has to be equal to the number that they want (according to his estimates above). To avoid suspicion, he also decides that it’s better for each flower shop to send no more than one bouquet to the same person. So far, so good, but he needs a specific shipment plan because he’s running out of time.

He opens up an Excel spreadsheet and creates the following layout of cells (he chose pink to make it more romantic):

Somewhere else in his spreadsheet he also typed the table of costs shown above. To his surprise, he even remembered to use the SUMPRODUCT function to calculate the total cost expression. He clicks “Solve” and finds out that the cheapest way to send all 20 bouquets will cost him $38. Not bad…but wait a second…something amazing happened! He cannot believe his eyes! The optimal solution exhibits a very curious pattern! Could it be a Valentine’s Day miracle? Could it be the power of love? If you want to see for yourself, download Mr. Lovr’s spreadsheet, open Excel Solver, and solve the model (no setup necessary, just click the “Solve” button). (NOTE: this spreadsheet has been tested with Excel 2007 under Windows XP, and with Excel 2008 under Mac OS X Snow Leopard. I’m not sure the “trick” will work in earlier Excel versions. For a free download of Excel Solver for Mac OS X, go here.)

Thanks to my love for giving me the idea for this blog post.

12 Comments

Filed under Exam Fun, INFORMS Monthly Blog Challenge, Love, Valentine's Day

Political Districting and OR

When I think about how Operations Research can contribute to the world of politics, one of the first things that come to mind is the redistricting process which, of course, has been receiving a lot of attention after the 2010 census. Here’s an excerpt from the census.gov web site:

Another major use for decennial census data is for geographically defining state legislative districts, a “redistricting” process that begins in 2011. The census data allow state officials to realign congressional and state legislative districts in their states, taking into account population shifts since the last census and assuring equal representation for their constituents in compliance with the “one-person, one-vote” principle of the 1965 Voting Rights Act.

One of my favorite articles on the topic is “An Optimzation-Based Heuristic for Political Districting” by Anuj Mehrotra, Ellis Johnson and George Nemhauser, which appeared in Management Science in 1998 (henceforth referred to as the MJN paper). For a districting plan to be acceptable, it has to be fair/unbiased (to avoid gerrymandering), where fairness can be defined in terms of criteria that districts have to satisfy, such as population equality, contiguity, and compactness. Contiguity means that the district cannot have holes in it. Compactness is a bit more difficult to define, but it essentially means that districts should look more like a circle or square than like a snake or a tree branch. For example, would you say that this state senate district in Florida is compact?

Another important issue is that the methodology used to create the districts be transparent. This is a strong point in favor of using mathematical techniques such as those of Operations Research. The algorithm and software code used to create the districts can be made publicly available for anyone to inspect. Specific questions about the methodology can be answered precisely and unambiguously. There’s no beating around the bush. I applaud efforts such as the Public Mapping Project, which attempts to make the districting process more transparent and increase public participation. Nevertheless, given how difficult the problem is (in both practical and mathematical terms), I believe that it would also be important to consider plans created with the help of OR. As no mathematical model is perfect, those plans will probably need to be fine-tuned by a human being using tools such as this district builder. Of crucial importance, however, is the need for clear rules to guide such modifications. When is it OK to move part of a district’s border? by how much? etc. Given that current OR software tools are capable of producing multiple high-quality solutions at the end of a run, perhaps an even better alternative is to present the decision makers with a myriad of OR-generated and man-made plans, and let them pick the most adequate one. This practice is common in sports scheduling, where the leagues typically ask schedulers to provide them with many alternative solutions to choose from.

At this point, I’d like to switch gears and explore the districting problem in more detail from an OR point of view (using some ideas from the MJN paper). Districts are made up of smaller geographical units, for example counties (or pieces of counties). For illustration purposes, if a state like Ohio, which has 88 counties, is creating 18 congressional districts and those districts are to be made up of counties only, the potential number of distinct districts is

{88 \choose 18} = 2,\!418,\!561,\!960,\!739,\!869,\!780

That number is greater than the number of miles I’d cover if I could travel at the speed of light for 400,000 years! (Without a bathroom break!) Obviously, many of those districts are not legitimate because they violate contiguity and/or compactness constraints. However, even if those invalid districts are eliminated, the remaining number of possible districts is still very large. Ideally, however, we’d like to use district building blocks that are much smaller than counties, such as zip codes, but that is still very challenging (and would increase the above number even more!). In the MJN paper, the authors create an initial plan using counties as building blocks and then fine tune the districts’ borders to equalize populations. Here are the “before” and “after” districting plans for South Carolina:

Pretty good improvement, huh? Their basic methodology is to associate one decision with each potential district indicating whether or not it is part of the final plan (a binary variable). The optimization model then selects a subset of the districts that covers each county exactly once (a set partitioning problem). Because the number of variables is huge (as we’ve seen above), they resort to a technique called branch-and-price. In short, branch-and-price solves an optimization problem by considering only a subset of its variables at a time and by adding in promising variables little-by-little as the search progresses. It’s possible to define mathematically what a missing “good” variable is, and to construct one (i.e. a new district) on-the-fly. During this process, many set partitioning problems have to be solved. Because these intermediate problems are not always solved to optimality, the final solution obtained in MJN, albeit very good, isn’t technically an optimal solution, and that’s why they use the word “heuristic” in the title of their paper.

Acknowledgment: I’d like to thank Brady Hunsaker for providing a nice collection of links in the comments section of this blog post by Michael Trick.

Update: Here is another post I came across this week that also talks about using OR for political districting.

9 Comments

Filed under Modeling, Integer Programming, Applications, Motivation, Promoting OR, INFORMS Monthly Blog Challenge, Politics

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