Author:Â Dr. Ed Klotz, Senior Mathematical Optimization Specialist

Optimization problems are all around us, often in unexpected places. In my last blog article, I showed interesting examples ofÂ how optimization shows up in the art world.

Now letâ€™s talk about another interesting place where optimization pops up: puzzles. If youâ€™re into games or puzzles, then chances are youâ€™ve seen mathematical optimization in action without even realizing it.

I often find that puzzles are a great way to help explain optimization to those who arenâ€™t familiar with it. Here are a few of my favorite examples.

## Game #1: The Matrix: Revisited

First up, hereâ€™s a simple game we created at Gurobi. In honor of the most recent installment ofÂ The MatrixÂ movie franchise, we dubbed itÂ The Matrix: Revisited.

Letâ€™s unpack what weâ€™re looking at here. First, theÂ greenÂ Target Matrix is a square grid of non-negative integers. Thatâ€™s fixed data, and we have no control over that. Next, the 6Â redÂ grids are binary matrices filled with 0 and 1 values. Last up, theÂ blueÂ matrix is the one you can manipulate. It starts blank, filled with zeros.

Your goal is to make copies of the red matrices, add them to the blue matrix, and see how close you can get to the green target matrix. (InÂ this on-demand Tech Talk, you can see more about how this works and possible solutions.)

A simulated scenario with real-world applications

Just like inÂ The MatrixÂ the movie, this simulated scenario has a real-world counterpart. In fact, the logic behind this game is helping save lives. Itâ€™s a model used to guide radiation treatment therapy for cancer using a robotic tool called aÂ Cyberknife.

The green target matrix is a grid overlaid on the diseased tissue. The integers in it are the dosage levels for each area of tissue within that grid. Certain areas are more diseased (higher numbers like 8 and 7) and need higher dosage levels. Other areas are completely healthy (0), so you want to avoid dosing those areas with any radiation at all.

The red binary matrices correspond to different angles of the robotic arm that administers the dosage of radiation. There are some constraints to specify how the arm can move and how much dosage it can deliver continuously.

When we make a model like this into a game, itâ€™s an amazing way to visualize optimization in the real world. And, spoiler alert, Gurobi was able to solve this small puzzle with ease.

## Game #2: Three-Dimensional Sudoku

Letâ€™s look at another game that ties back to optimization. Most of us are familiar withÂ Sudoku, a 9Ă—9 grid that you need to fill with unique numbers.

Most Sudoku puzzles are easy enough for humans to solve on their own. In fact, thatâ€™s the whole point of them. But what if we looked at Sudoku in a whole new way?

Try this variant: Instead of filling numbersÂ in, try taking numbersÂ out. As designed, Sudoku puzzles have only one answer. What are the fewest numbers you can take out before you â€śjailbreakâ€ť the puzzle? Hint: Try removing a couple of numbers that donâ€™t appear as often.

Letâ€™s take it up another level. What if we make a Sudoku grid bigger? Hereâ€™s a real-world example weâ€™ve worked on where the grid increased to 17Ă—32. The numbers are swapped out for labels, and thereâ€™s also the added complexity of color-coding based on certain conditions.

The addition of coloring creates a third dimension to the puzzle.Â  Also, the rules for placement of the labels in the grid cells are more complex than the standard Sudoku puzzle. The larger grid size, additional dimensionality, and added complexity make this puzzle much harder to solve than even the most challenging standard Sudoku puzzle.

This puzzle would be quite difficult for most humans to solve quickly, if ever. And yet itâ€™s a puzzle that a team of human planners have worked out every year since 1920. If you recognize this as the date when the National Football League was founded, you get extra points.

It turns out, this is the real-world model the NFL uses to plan their game and broadcasting schedule. The horizontal columns identify the 32 teams in the league, from the Dallas Cowboys (DAL) to the Los Angeles Chargers (LAC). The vertical columns represent the 17 weeks in a season (theyâ€™ve since moved to 18 weeks). The black squares are bye weeks, where a team isnâ€™t scheduled to play. And the other colors represent the television network on which a particular game is broadcast, from ESPN to NBC.

Using this model, the NFL planners can come up with compelling schedules, with the biggest, most exciting games broadcast to the biggest audiences. Gurobi Optimizer helps them get there, in a fraction of the time that they can figure out a compelling schedule themselves. For more about this story, see ourÂ NFL case study.

Another interesting puzzle isÂ Slitherlink, also known as the Traveling Salesman problem. Your job is to connect the dots in a single loop, using the fewest number of lines. The numbers are constraints: how many lines can touch a particular square.

This sort of optimization model can be used in all sorts of real-world scenarios, from how Google Maps helps plan the most efficient route between two points or how delivery services figure out which routes their trucks take each day.

## Game #4: Rectangle Packing Game

With this game, the objective is to rearrange the rectangles, in order to minimize the amount of space being used, without letting the rectangles overlap. Using your mouse, you can try rearranging the rectangles into different configurations. As you do, youâ€™ll see your score (measured by the area of the smallest rectangular boundary containing the individual rectangles) in the lower-left corner. The lower the score, the better youâ€™re doing.

Once you think youâ€™ve achieved the most efficient layout, you can let the Gurobi Optimizer give it a try. In less than a second, Gurobi will show you the optimal way to arrange the rectangles.

As you may have guessed by now, this simple and fun game has real-life applications. For example, arranging hardware components on a chipâ€”where the components need to be as close as possible, in order to speed up communication.

It also applies to situations like bin-packing design, two-dimensional job scheduling, and positioning machines on a shop floor, among others. To see the game in action, and learn more about its real-life applications, check out our Tech Talk,Â Converting Weak to Strong MIP Formulations.

## Game #5: Burrito Optimization Game

This game is one we created in-house, for use as an educational tool. It introduces players to the idea of mathematical optimizationâ€”teaching them a little about what optimization can do, what sorts of problems it can solve, why someone might want to use it, and what advantages it has over manual trial-and-error approaches.

The goal of the game is to place burrito trucks to serve hungry customers throughout the city, while maximizing your profit. Truck placement has to be carefully planned, because every truck has a costâ€”but its ability to earn revenue depends on how close it is to potential customers. For example, on some days, special events increase the demand in some regions of the city; on other days, the weather affects customersâ€™ willingness to walk to a burrito truck.

You canÂ play the Burrito Optimization game for freeÂ (youâ€™ll just need to create an account). And be sure to check out theÂ Teaching Guide, for more info behind the methodology.

## Get Inspired

By turning optimization into games like these, we can consider problems from new angles, in thousands of real-world scenarios. This more visual approach to optimization models can help explain the importance of mathematical optimization and the meaning of individual models to those less familiar with the algebraic representations or underlying mathematical foundations.

For more about how optimization can help you solve puzzles of all sorts, watch our recent Tech Talks:Â Grab Bag of Interesting and Unusual Optimization Applications, as well asÂ Converting Weak to Strong MIP Formulations.

#### 30 Day Free Trial for Commercial Users

Start solving your most complex challenges, with the world's fastest, most feature-rich solver.

We make it easy for students, faculty, and researchers to work with mathematical optimization.

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Get a free, full-featured license of the Gurobi Optimizer to experience the performance, support, benchmarking and tuning services we provide as part of our product offering.
Gurobi supports the teaching and use of optimization within academic institutions. We offer free, full-featured copies of Gurobi for use in class, and for research.
##### Cloud Trial

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.