The Burrito Optimization Game

The Burrito Optimization Game is an educational resource designed to introduce players to the power and capabilities of mathematical optimization. I collaborated with Gurobi Optimization to build the game, which is free and publicly available to anyone interested in discovering – or teaching others about – the benefits of optimization. (See www.burritooptimizationgame.com.)

The premise of the game is simple: Drag and drop burrito trucks onto a city map to serve customers. Each truck incurs a cost and each burrito sold earns a profit. The player’s goal is to maximize the total profit and get as close to optimal as possible while building a solution (see homescreen below).

If you are an optimizer, you’ll recognize this as a facility location problem. In particular, the underlying optimization problem is equivalent to the uncapacitated fixed-charge location problem (UFLP). The UFLP has been well studied for decades. It has a simple mixed-integer programming (MIP) formulation, and even large instances can be solved quickly with modern MIP solvers.

But players don’t need to know the MIP formulation or optimization algorithms to play the Burrito Optimization Game. Instead, the game is designed to introduce optimization to new learners and teach them why they might want to use optimization. Choosing burrito truck locations by trial and error, the player is essentially solving the underlying optimization problem manually. This usually goes fine in the first “day” (level) of the game; it is relatively straightforward to eyeball a near-optimal solution.

But as the game progresses, new wrinkles are added. The number of customer locations, as well as the number of allowable truck locations, increases over time. Cost parameters change. The weather influences customers’ willingness to walk to a burrito truck. Demands become random rather than deterministic. These factors make the game harder to solve manually, and by the final levels, even the most seasoned optimizers will feel the frustration of building manual solutions.

Meanwhile, each time the player finishes a level, the game calls Gurobi’s MIP solver to optimize the problem exactly. The player’s and Gurobi’s solutions are displayed side by side. Players can see how their solution fares in comparison to Gurobi’s (a humbling experience, even for expert optimizers or facility locators!).

These comparisons serve two purposes. First, they help players improve their solutions in subsequent levels by comparing their solution to the optimal one. Second, and more important for the underlying purpose of the game, they help convey the message that optimization by hand is difficult – often impossible – and that modern algorithms and solvers can nevertheless find optimal solutions in a fraction of a second.

The game also has a Championship Mode [1] in which players can compete against each other to see who develops the best solutions. An instructor or event leader can set up a new championship with a “match code” so that players are only competing with other members of the class or event. Unlike in normal gameplay, the optimal solutions are not revealed to the players in Championship Mode.

Learning from the Game

We built the Burrito Optimization Game with a few main audiences in mind. One is data scientists: After a data scientist completes a forecasting, classification or other data science task, they are often left with the question “what’s next?” That is, once you have data to describe or predict a system, how can you use that data to optimize the system?

A second audience is introductory operations research (O.R.) students. Students’ first exposure to optimization is often through algebraic models and graphical diagrams. We think it’s more fun, and more effective, to start off with a game to introduce some of the “why?” behind optimization.

A third audience is anyone who needs a demonstration that optimization is hard: If your boss, assistant or student thinks that it’s easy to optimize systems involving many possible combinations, have them try doing it by hand and they’ll quickly see why optimization algorithms are essential.

Finally, a bonus audience is younger students. The game is a great tool for introducing K-12 students to the idea that there’s more to math than quadratic equations and Pythagorean triples. Math forms the basis of a powerful set of computational tools that are critical for real-world decision-making.

The Burrito Optimization Game also works well as a standalone game played by an individual. An individual can learn about the “why” of optimization through the progression of the levels of the game – the increasing difficulty of optimizing by hand and the ease with which Gurobi solves the problem algorithmically.

The game helps individual learners by automating insights in the form of tips that are automatically generated when the player’s solution is compared to the optimal one (see screenshot below). These tips are indicated by lightbulb icons. Hover your mouse over a lightbulb and the game will comment on what you did well or poorly. For example, “You put trucks too close together” or “This part of the city is underserved. A truck placed here could have captured 127 more customers, for ₲131 additional profit.” (₲ stands for “Gurobucks.” See what we did there?)

Some tips comment on aspects of optimization problems that can be surprising to newcomers. For example: “Your solution was almost as good as Gurobi’s even though you opened three fewer trucks than Gurobi did. There is more than one way to earn a high profit; you found a different way than Gurobi.”

Others comment on directional changes as the daily situation changes: “Today’s higher ingredient costs mean there will tend to be fewer open trucks in the optimal solution than yesterday (since it’s harder to earn enough revenue to offset the cost of one truck).” And others reinforce the importance of optimization algorithms by commenting on the sheer scale: “There are 262,144 possible solutions to today’s problem. Gurobi found the optimal one in the blink of an eye.”

The online Game Guide [2] provides a lot more information about how to play the game, as well as the MIP formulation of the underlying optimization problem and a short overview of the branch-and-bound algorithm used by Gurobi to optimally solve the problem. It’s a useful first step for someone who plays the game and wants to learn more about optimization.

Teaching with the Game

The Burrito Optimization Game is a great tool in the classroom for introducing learners to optimization. It has been used in this way in both academic and industry settings.

A typical lesson plan might work something like this:

• Introduce the game. Discuss goals, rules, gameplay, etc.
• Play two or three “days” of the game. Let students get a feel for the game.
• What seems easy or hard about locating burrito trucks? Did anyone find a solution that was close to optimal?
• Finish Round 1.Students will work through a few new wrinkles (changing costs, different demand behaviors, increasing number of nodes).
• What strategy did students use? Ask, if you were going to design an algorithm to solve the problem (that is, to automate the work that you did by hand, and maybe do it better), what strategies might your algorithm use? What are the pros and cons of the different algorithmic ideas?
• Choose one:Play Round 2 (which introduces demand uncertainty) or step away from the game for a few minutes for an “optimization 101” primer (for example, high-level discussions of why enumeration is impractical, how to formulate a simple MIP, how branch-and-bound works, etc.).
• What surprised students about playing the game or about the discussion afterward? Ask, can you think of other real-world problems that might benefit from optimization? What previously learned mathematical/computational concepts might be useful in designing optimization models or algorithms?

Afterward (perhaps for homework), have the students compete against each other in a championship that you set up for them in Championship Mode. (A gift card to your favorite burrito restaurant for the winner?)

We feel the game has three main takeaways that each player should have learned after playing:

1. Planning doesn’t end with forecasting. Finding the best site is one thing. Finding the best 10 is orders of magnitude harder.
2. Optimization by hand is hard. You might have done fine when there were, say, 15 possible spots to locate trucks. But what if there are 50, 500 or 5,000 (as in many real-life situations)?
3. Optimization can be done by algorithms. Mathematical optimization is a mature scientific field with a well-developed theory and robust commercial and open-source software.

The game also provides many opportunities for “aha!” moments and insights about optimization that you can highlight while playing the game. For example:

• Trade-offs. Maximizing profit in the game means trading off between (fixed) truck costs and (variable) revenues. There is more than one way to navigate this trade-off, and different solutions may use different numbers of trucks while still being nearly equally good.
• Diminishing returns. The first truck you place in a given part of the city will usually have a big impact on your profit, but subsequent trucks will bring less profit as the area becomes saturated.
• Directional changes. Although optimization is sometimes viewed as a black box by people new to the topic, optimal solutions still behave in predictable ways that students can anticipate. For example, if the ingredient cost per burrito increases, do you expect that the optimal number of trucks will increase or decrease?
• Greedy approaches may not be optimal. Most players take a greedy approach to locating trucks in the game. But this is not optimal, which the instructor can demonstrate. Students can brainstorm other possible algorithms and discuss their pros and cons.
• The problem is solvable, even though it’s NP-hard. Some audiences (especially computer scientists) might come to the game with the belief that NP-hard problems (like the UFLP) are “impossible.” By showing Gurobi’s solution time (usually less than one second), the game helps dispel this misconception.

The online Teaching Guide [3] provides more suggestions for how to use the game in a classroom setting.

Making Optimization Fun!

We hope (and believe) the Burrito Optimization Game is fun to play and provides a smooth on-ramp to more technical optimization concepts. The artwork by Hansel González (www.hanzmade.net) is colorful and whimsical, and it invites the player to enter the world of the game. We could have built the game around locating ambulances or mobile libraries, but who doesn’t love burritos?

And for the math geeks, each building on the city map has a punny, nerdy name, crowdsourced from the Gurobi team. Just a few highlights: LP Relaxation Spa! Farkas’ Lemma-nade! Interior Point Decorating! You’ll have to play the game to see them all. And in case that’s not enough, we’ve included a key to the building names [4], along with a brief explanation of the underlying math/data science/optimization concept, in the Game Guide.

Feedback

The Burrito Optimization Game has been one of the most fun projects I’ve worked on in my career. The Gurobi team and I hope you find it fun and useful, either for your own learning or in the classes you teach.

The game is available at www.burritooptimizationgame.com. It’s free to play, although you’ll need a (free) Gurobi account, which is quick to set up.

We’d love to hear your feedback about the game. What worked well for you? What would make the game better? What “aha!” moments did your students have while playing it? You can reach me at [email protected] or the Gurobi team at [email protected]. Happy playing!

References

1. https://www.gurobi.com/lp/academics/burrito-optimization-teaching-guide/#championship-mode  
2. https://www.gurobi.com/lp/academics/burrito-optimization-game-guide/
3. https://www.gurobi.com/lp/academics/burrito-optimization-teaching-guide/
4. https://www.gurobi.com/lp/academics/burrito-optimization-game-guide/#the-buildings