Classroom Optimization Games

When I first saw Professor Norman Pendegraft’s LEGO game published in OR/MS Today [1], I was fascinated. I loved the idea of experiencing an optimization problem while touching physical objects and wanted to use it in my own classroom. Many years later, I finally went for it: I modified Pendegraft’s game to have three resources instead of two, changed the data a bit and purchased enough off-brand LEGO-type bricks to create 10 sets of parts carefully packaged inside zip-close bags. Off to my MBA class I went, with a smile on my face (to be continued…).

A Greater Purpose

As a child, I naturally loved math. I never had anyone explain to me how applicable it is to the real world; I just liked it and saw it as rules, patterns and order. I do understand, however, that most children are not like this. I believe that most (if not all) of the bad reputation that math gets (and the bad memories people might have who grow up to say they “never liked” or “hate” math) has to do with how it was taught to them. In the book “What’s Math Got To Do with It?,” Boaler provides evidence that learning mathematical problem-solving through challenges or projects that involve group work and allow for freedom of thinking and creativity to express oneself yields much-improved results in terms of learning and one’s long-term relationship with mathematics [2]. Therefore, I decided to join the crusade to help change this sad reality.

Optimization is a great gateway into developing a passion for mathematics: There are tons of real-life applications (i.e., its usefulness is obvious), and it is easy to explain. There is a goal (objective function), and there are rules (constraints) and moves you can make (decision variables). Wait! It’s a game! Children love games, so I started creating a series of them based on well-known optimization problems. I wanted them to be easy to explain, easy to distribute to any teacher in the world and easy to play. Hence, my game creation rules are (i) the game can be fully explained in one page, and (ii) the game pieces can be made with paper. This allows me to create a two-page PDF file for each game: Page 1 explains the problem and illustrates it on a small example, and Page 2 provides a larger (unsolved) instance of the problem and includes drawings of the pieces that can be cut out with a pair of scissors. All that is needed now is a printer.

Games vs. Puzzles

One may argue that these games are actually puzzles. I argue that it depends on how you use them. The experience can be gamified in several cooperative or adversarial ways, such as the following:

• Divide the group into teams and give them a set amount of time to work on the problem. Whichever team produces the best solution is the winner.
• Form pairs and let them take turns picking the next move in the decision process. Compare that against the solution obtained when they solve the problem alone, and then ask them to explain their rationales to each other.
• Introduce some randomness by using dice to decide how some moves are going to be made. The next person to make a move will need to try and compensate for that potentially bad random move.
• Have one person on the team play the role of an adversary who, when their turn comes, picks a decision that will hurt the solution being built as much as possible.

The Games

Here, I will provide a brief explanation about each of the seven games I have created thus far (there are more on the way), starting with the introductory sentences of each game’s first page. Each game can be freely downloaded [3], and Portuguese versions are also available.

Games That Only Require Basic Counting

Elektra Bikes (set covering). Elektra Bikes Inc. wants to install electric bike stations around the city for their ad to claim, “Wherever you are, a bike is never too far!” This means you are never more than two street segments – that is, the length of two blocks – away from a bike station. Stations can be installed on any city corner. Your goal is to pick corners on which to install bike stations to cover all street segments of a given map.

Page 2 includes a large map and orange circles (bike stations) for the players to cut out and place around the map.

Stop the Fire (the firefighter problem). You are a member of a firefighting squad that fights large forest fires by dropping fire retardant onto affected areas from two helicopters. Areas that can catch fire are drawn as circles, aka nodes, on a map, and corridors along which fire can spread appear as lines connecting the circles. How to play (illustrations are provided to clarify what is happening): First, choose a node where the fire will start and make it red to indicate it is burned. Then, choose two nodes to defend with your two helicopters, making them green. After a defense round, all undefended nodes connected to a burned node by a line will burn. You can then move the two helicopters to two other nodes to defend them, and so on, until all nodes are either burned (red), defended (green) or safe (white). Your goal is to save as many nodes as possible or, equivalently, minimize the number of nodes that burn.

Page 2 includes a large map, plus red and green circles for the players to cut out and place on the map.

Games That Require Some Basic Calculations

LEGO Furniture (product mix). This is the same kind of product mix problem as proposed by Pendegraft [1], but with a third resource added in for a bit more complexity.

Patty-O FunnyTure (product mix). This is a simplified version of the LEGO Furniture problem above that is suitable for children in first grade.

Pack That Bag! (knapsack problem). You are participating in a TV game show in which each contestant is given an empty duffel bag that can carry up to 26 pounds. In front of you, there are 12 household items, each labeled with their corresponding weight and dollar value (a table with data is provided). It is not possible to carry all items in the bag because of the 26-pound limit (assume space is not a problem). Your goal is to choose which items to pack in the bag so that the total dollar value of the items inside the bag is maximized – that is, as large as possible.

This explanation is followed by a picture of a strip of length 26 cm, with 1-cm markings, and colored rectangles, one for each item, whose length in centimeters equals how many pounds they weigh. If your choice of items has total length less than or equal to 26 cm, it means they fit in the bag. On each item’s rectangle, its dollar value is also indicated. A sample solution is provided to illustrate a feasible packing of the bag and its total value.

Sort at the Port (cumulative scheduling). Cargo ships arrive at the port of Miami and need to be unloaded. The ships differ in size (length) and how long (hours) it takes the cranes to offload their cargo (this depends on both the amount of cargo and how fragile it is). The place at the port where the ships dock for unloading is called the berth and has a limited size. This means only a few ships can dock near the cranes to be unloaded at the same time. The question facing the port manager is: In what sequence should today’s ships be unloaded to finish as early as possible?

This explanation is followed by an illustrated example with three ships showing how different unloading orders yield different completion times (i.e., makespans). Page 2 includes drawings of a large berth and several ships of different sizes and unloading times for the players to cut out and move in and out of the berth as they try to produce a solution.

The Baker’s Conundrum (cumulative scheduling). Every year, families get together for large feasts during the holidays. This means preparing and baking several different items, such as poultry, fish, bread, cakes, cookies, etc. With a single oven available in the kitchen and each item requiring a certain amount of space and time in the oven, choosing the order in which to bake these items (and arranging them in the oven) can make a difference in terms of total baking time. (The sooner we are done, the sooner we can eat, right? Yum!)

This explanation is followed by an illustrated example with three items showing how different baking orders can save you time. Page 2 includes a drawing of a large oven plus myriad foods in different sizes and shapes that require distinct baking times. We are assuming that all of them bake at the same temperature, but what if they do not? Aha! Ask your audience!

Following Up After Gameplay

In addition to asking each individual or team to explain their approach to solving the problem, which can be an interesting activity itself, at the end of each game’s description, I provide additional questions for a follow-up discussion. They are a great way for people to think about concepts such as modeling and abstraction:

• How do you know for sure that your solution is the best possible?
• What assumptions or simplifications from the real-life situation were made while solving this problem?
• Variations: If we changed <feature A> to <feature B>, how would you modify your approach to solving this problem? Does that make the problem easier or harder? Can you think of another modification that makes it easier/harder?
• Abstractions and associations: At a high level, this game is about locating things that cover other things. Can you think of another example or application that fits this same pattern?
• Creativity: Create your own instance of this problem and try to solve it. See how well your friends can do on your instance.

Classroom Experience

So, I entered the first lecture of my MBA class, distributed the bags of LEGOs around the room (accompanied by instructions), and told the students to get to work. I left out key definitions and details: For example, the instructions tell them to find the best collection of products to make. But what does best mean? Someone eventually brought that up and we went on a tangent about potential definitions, minimization/maximization, etc. We then focused on one objective: maximize profit. At which point someone inevitably shouted, “But we don’t have enough data!” to which I replied “True! What do you need?” I kept going like this, omitting some things, waiting for them to realize there’s an issue or to question an assumption, until all groups converged on a solution.

I also had a chance to use the Pack That Bag! game with groups of prospective MBA students several times during mock class sessions offered through some recruiting events run by the business school. The way I run those is similar to what I described earlier. In both cases, the feedback I received over the years has always been very positive, with students particularly emphasizing that they enjoyed the hands-on aspect of the exercise.

If you happen to use any of my games in the classroom, or with your family and friends, I would greatly appreciate if you could share your experience with me via email at [email protected].

References

1. Pendegraft, N., 1997, “Lego of my simplex,” OR/MS Today, Vol. 24, No. 1, p. 8.
2. Boaler, J., 2015, “What’s Math Got To Do With It?” Revised edition, New York: Penguin Books.
3. Yunes, T., 2023, “Optimization Games for the Young,” https://thyunes.github.io/games.html.