Thanks to my former MBA student Max Marty, I came across this interactive scale of the universe (click on the word “Play” below the video game ad). It’s easy to lose track of how big 10^10 is, and this scale helps to put things in perspective. Next time you’re teaching a course in optimization or constraint satisfaction and you tell your students a certain problem has 10^100 possible solutions, bring this scale up on the screen! (Tip from the creators: it’s better to use the arrow keys rather than the mouse to scroll left and right.)

# Tag Archives: teaching

## Twilight Network Flow

CAUTION: Spoiler Alert!

Part of a professor’s job is to come up with new exam questions each year. That may be a time-consuming (and sometimes tedious) task. You want the question to be just right: not too easy, not too difficult, and capable of testing whether or not the students understood a given concept. This year, I figured I might as well have some fun while doing it. Inspired by Laura McLay’s insightful (and very popular) post on vampire populations, I decided to create a Twilight-themed network flow question:

Alice is in charge of planning Edward and Bella’s wedding and she ordered 2000 roses to be delivered to three locations as shown in the network below. The Cullen’s house (node 2) needs 1000 roses, Charlie’s house (node 4) needs 800 roses, and Billy’s house (node 7) is supposed to get 200 roses (just to tease Jacob). The numbers next to the arcs of the network represent shipping costs per rose (in cents); they’re proportional to the distance between each node. The roses are coming from two local growers in Forks (nodes 1 and 3). Each of them can supply 1000 roses. Arrows with two heads indicate that shipments can be made in both directions.

Write down the supply and/or demand values next to each node and write a linear programming model to determine the shipment plan that minimizes the total cost of delivering all the roses (include all the necessary constraints). (Note: Alice already knows whether you’re going to get the right answer.)

The second half of the fun is to see if any students react to it. In fact, I got a couple of interesting written comments: “How dare you incorporate Twilight into Management Science?”, and a Harry Potter enthusiast wrote “Team Harry!”, while at the same time substituting the names of Hermione, Harry, Ginny and Malfoy for Alice, Edward, Bella, and Jacob.

Filed under Exam Fun, Linear Programming, Modeling, Network Flows, Teaching

## Facebook’s Farmville: What’s the Fastest Way to Get Rich?

One can’t help but notice that a lot of people have been playing Farmville on Facebook lately. Some of my relatives, friends, students and co-workers have taken the plunge. I don’t have time to *play* Farmville, but I thought it would be interesting to *study* it. It’s a simple and fun game, easy to explain, and apparently addictive.

You begin the game with a 12 by 12 piece of land. That gives you 144 one by one squares in which to plant crops. To simplify the explanation, I’m going to (1) restrict my attention to the four crops initially available (strawberries, eggplant, wheat, and soybeans); (2) assume crops will be harvested as soon as they are ripe (that is, ignore wilting); (3) disregard the random bonuses and gifts that show up every now and then. Blogger Mark Newheiser has a nice post about Farmville in which he includes a useful table. The cost column includes the cost of plowing the land (15 coins) plus the cost of purchasing the seeds. Because the harvest times of all four crops are multiples of four hours, we can think in terms of 4-hour periods.

**Question****:** **What’s the largest amount of cash one can obtain in 6 days?** (need to rest on the 7th day).

You initially have 200 coins, one ripe and one half-grown square of strawberries, one ripe and one half-grown square of eggplant. By harvesting the two ripe squares, your fortune grows to 323 coins. I’ll also go ahead and clean (delete) the two half-grown squares so that we can begin with a clean slate. It turns out that the answer to the above question is to plant strawberries *only,* and as much as you can. Here’s the planting schedule:

Period | Strawberry Squares |

0 | 12 |

1 | 17 |

2 | 24 |

3 | 34 |

4 | 47 |

5 | 66 |

6 | 92 |

7 | 129 |

At period 8 (after 32 hours), you’ll have enough money to fill all your 144 squares with strawberries and you just continue to plow, plant and harvest them all every 4 hours. After 6 days (36 four-hour periods), you’ll have 44,913 coins (adjusted to take into account that 4 squares were already plowed at time zero). This solution is not very exciting and, moreover, easy to predict. Taking a second look at the cost table, we can see that the profit per hour of strawberries, eggplant, wheat, and soybeans are 2.5, 1, 0.903, and 1.375, respectively. This fact, *combined with the fact that strawberries are the fastest to grow*, yields the above result. As one progresses through the game, other crops become available and strawberries’ dominance goes away. However, we can show that things can get very complicated by changing the numbers a little bit. If we increase the cost of strawberries to 31 (including plowing), their profit per hour changes to 1 (worse than soybeans). Here’s the new *optimal* planting schedule for 6 days, which yields a profit of 15,725 coins:

Period | Strawberry Squares | Soybean Squares |

0 | 2 | 8 |

1 | 3 | |

6 | 1 | 15 |

7 | 7 | 1 |

8 | 6 | 2 |

9 | 7 | |

12 | 5 | 26 |

13 | 8 | |

14 | 13 | |

15 | 29 | |

16 | 25 | 8 |

17 | 2 | 27 |

18 | 57 | |

22 | 16 | |

23 | 75 | |

24 | 69 | |

29 | 16 | 59 |

30 | 85 | |

35 | 59 |

Note that the best course of action now is to mix strawberries and soybeans and, at least to me, the proper way of doing it isn’t so obvious (hence the value of using Operations Research). If you’re now wondering whether there would be a situation in which the best idea is to use three different crops, the answer is yes! If we decrease the cost of eggplant to 19 (including plowing), for instance, the optimal planting schedule results in a profit of 18,157 coins and looks like this:

Period | Strawberry Squares | Soybean Squares | Eggplant Squares |

0 | 17 | ||

12 | 1 | 37 | 18 |

13 | 1 | ||

14 | 1 | 1 | |

15 | 1 | ||

16 | 1 | ||

17 | 2 | ||

18 | 123 | ||

24 | 18 | ||

26 | 1 | ||

27 | 1 | ||

28 | 1 | ||

29 | 3 | ||

30 | 123 | ||

35 | 3 |

In conclusion, I believe that Farmville is a rich decision-making environment that can be used to illustrate some of the analytical techniques from the field of Operations Research. This simple example shows how complicated things can become, even with only four crops!

One possibility of extending this analysis would be to consider that one isn’t willing to log in every 4 hours or so in order to harvest crops, so here’s another question:

**Question: Given a schedule of off-line hours (i.e. not available for harvesting), how much money can you make in 6 days?**

Finally, I haven’t actually answered the question that appears in the title of this blog post: what’s the fastest way to obtain X coins? I’ll leave these last two questions as an exercise.

**Technical Details:**

This section of the post is dedicated to those who want to know more about how this analysis was conducted. I used an integer programming model written in AMPL (I think dynamic programming would work too). My variables are: = number of squares planted with crop in period , = number of squares of crop harvested in period , = area in use in period , = money available in period . Periods go from to (in our example, ). So we are interested in maximizing .

The constraints update the values of and based on what you do in period . Here they are (I’m omitting the details of boundary conditions):

where and are, respectively, the cost and revenue of crop . Because we don’t consider wilting, , where is the time it takes crop to grow and ripen. Therefore, the variables can be eliminated. Finally, we require and . Here’s the mixed-integer programming (MIP) model in AMPL in case anyone wants to play with it. When it is optimal to use more than one crop, the MIP can get pretty hard to solve, considering its size.

Filed under Applications, Exam Fun, Facebook, Farmville, Integer Programming, Modeling, Teaching

## YouTube Videos on Solving LPs with Excel

This had been in the back burner for a long while. Each time I taught my O.R. class (either undergrad or MBA), I kept thinking that the students would like to be able to see the Excel setup of an LP model over and over again. Many of them are not proficient in Excel, and my class is their first contact with things like absolute cell references and SUMPRODUCT. I watched a number of YouTube videos on the topic, but I wasn’t happy with any of them. Besides, I wanted the video to be about the same example that I use in the classroom. So I decided to bite the bullet and go for it. I think the outcome was decent: not great, but not terrible either. My wife said I sound a little stilted. I agree. I was only willing to do it once, no second takes, which means I was a little nervous :-)

Before I give you the link to the videos, I need to bring your attention to two disclaimers:

Disclaimer 1: I used the demo version of iShowU to record my screen action. That means you’ll see a green watermark on top of the video. I know it’s ugly, but I didn’t want to pay $29.95 for it. At least not until I get some feedback to convince me that I’ll be doing more of these videos.

Disclaimer 2: I shamelessly use the same example that they (used to?) use at the Tepper School in my classes: the “famous” farmer problem (sorry Javier :-). I was the head TA for that class a number of times and I literally sat through it at least 3 or 4 times.

Here they are:

Linear Programming: The Farmer Problem, Part I (9:07 min)

Linear Programming: The Farmer Problem, Part II (8:57 min)

I hope these videos turn out to be useful to my students and to anyone who wants to learn about linear programming and Excel Solver. I’m thinking about doing more videos on the diet problem, transportation, sensitivity analysis, etc. Let’s see how things go.

Filed under Linear Programming, Modeling, Teaching, Videos, YouTube

## Modeling Logical Conditions

Binary variables are extensively used in integer programming (IP) models to represent yes/no decisions (“Should we open a new restaurant in Coconut Grove?”), and logical conditions (“If it rains tomorrow, I will not go to the beach.”). Most people are familiar with the project selection problem in which each variable Xi is equal to 1 if project “i” is selected, and it’s equal to zero otherwise. To model the condition “if project 1 is selected, then project 2 must also be selected” one can write “X1 ≤ X2″, and “if project 2 is selected, project 3 must not be selected” becomes “X2 + X3 ≤ 1″. Even students who are learning about integer programming for the first time are usually capable of coming up with those two constraints after a few minutes (or hours). A little bit of trial-and-error typically gets you there.

What if the logical condition is a tad more complicated? For instance:

If it rains tomorrow or the Heat defeat the Spurs and grandma doesn’t come to visit on the weekend, then I’ll either go to South Beach and not drink a mojito or I’ll fly to Vegas.

I’m sure it only took you about 7 seconds to figure out that the corresponding IP model is

w + q – x ≥ 0

z + w + q ≥ y

1 + q ≥ x + p

y + p – q – z ≤ 1

This assumes that the binary variables x, y, z, w, p, q are assigned the following meanings: x = whether it rains; y = whether Heat defeat Spurs; z = whether grandma comes to visit, etc.

My students always ask me if there’s a more systematic way to come up with the linear constraints other than trial-and-error or memorization of a few simple cases. This led me to write a 4-page handout on the topic. More recently, I searched around for a while (OK, I confess that my search wasn’t very extensive) and found two references: an article on INFORMS Transactions on Education and H. P. Williams’s book. It turns out that Williams (section 9.2) does an excellent job explaining the process (if only I had known that two years ago…).

I hope this handout can still be helpful to someone out there (instead of just sitting in my hard drive). As always, your comments and feedback are welcome.

Filed under Integer Programming, Modeling, Teaching

## No more excuses. Math can be fun!

Everyone who teaches a math-related subject has probably struggled with attracting (and keeping) the students’ attention. At parties, it gets even worse:

- “Hey, nice to meet you. What do you do?”

– “I’m a professor.”

– “Really? What do you teach?”

– “How to use mathematical models to help business managers make better decisions.”

– “Hmm, interesting stuff…I never really liked math…<awkward silence>…see you later.”

Times have changed. With books like The Goal, The Numerati, and Innumeracy (among others) and publications like Interfaces and the Analytics magazine, there are no more excuses. Fun and realistic examples describing how math, stats and OR are being used in real life abound. Why not use them in class? I propose, however, that we go one step further. Why not make one of these books the assigned course reading? Go over the book in class and, every now and then, stop, teach the technique in question, do a few exercises, and then proceed with the reading. I haven’t finished reading the Numerati yet, but it certainly would lend itself to something of the sort. Here’s the approach: start by showing a realistic problem, with a real story and facts provided by a third party that corroborate its relevance. Then, and only then, show the math that tackles it. Repeat until final exam.

While I haven’t had time to transform my own classes in such a drastic way, I’ve decided to increase the appeal of my MBA course on *Management Science Models for Decision Making* (a.k.a. OR) by spending the first 5 minutes of each lecture going over a real-life application of OR. The source of these applications? My fellow OR bloggers! Here’s the list of applications I used this past Spring:

Open Pit Mining, Fewer Brown Left Turns, Optimizing Airline Routes, Revenue Management at Thomson Holidays, Swapping Kidneys, Renewable Energy Portfolios, Domino Artwork, Aisle Design for Warehouses, Dutch Railway Scheduling, OR at the Lego Factory.

After explaining the application and the role OR plays in it, I connect the problem with the topic we are currently studying. The students’ reaction is always very positive. And, if you’re feeling audacious, you can even close it all with MC Hammer’s YouTube video on Analytics! I’m curious to know what other instructors in quantitative disciplines do to motivate their students. Let me know in the comments!

Filed under Teaching