Optimization (With Applications to Battleship)

Objective: 

To learn high level concepts involving optimization and constraints.

Background:

Optimization is the process of choosing the “best” option out of a number of possible alternatives.

We might be trying to do this for a specific problem, or developing a method to use on a lot of problems of a particular type.  

As an example, imagine that we are trying to find the fastest point from A to B in the figure below. We might try a few different paths (colored in red, green, yellow, and blue):

We might get to the end and think that green and yellow seemed to take the least amount of time. We might not like the blue path, but we really had trouble when it came to the red path in terms of finding the fastest route from A to B. This might represent a real world problem of trying to find an efficient route on an uncharted hike or trying to find the best way through a crowded room. 

In this particular example, the fastest route would be the route that is closest to a straight line between A and B. When we can see the entire puzzle, we can find this route relatively efficiently. Now imagine that we had to find the fastest way from point A to point B and we can only see part of the problem space:

Now in this setup we have to find a way to navigate the area that is not visible to us while also attempting to find the fastest route from point A to B. This starts to approximate how most real world optimization problems start to look. Imagine that we found a way through the hidden area above. Would we be able to say for certain that we found the fastest possible of all routes or the fastest possible route over the area we discovered? This gives rise to two more terms:

• Global optimum – The best possible choice of all possible choices.
• Local optimum – The best choice of the options that we have explored.

The global optimum and a local optimum might be the same, but in most real world problems it is difficult to verify. Now imagine that we are considering the first problem where we could see the problem space. Imagine that we are not allowed to use any path that goes through the red square:

Now our fastest path that we identified, the green path, is no longer available to us. The red path (the slowest identified) is also not available. The next best path appears to be the yellow path (this is our path that represents the current local optimum). In this version of the problem, the red square represents a constraint. A constraint is a condition that limits the possible answers that we might choose when we try to optimize. Some constraints are obvious (ex. we can’t go through walls in the example above) and others might be subtler.

Target variables represent the variables that we are looking to optimize. This often means that we are looking to minimize or maximize the variable, subject to other things that we have control over and the ability to change. In general, we might find that there are common themes for target variables. We might say that we want to maximize good things and minimize bad things in terms of any specific problem. What a “good” thing or a “bad” thing is depend on the problem we are studying. For example, let’s consider a generic variable of “time.” If we are trying to optimize having fun after school, we would want to maximize the time spent having fun and minimize time doing other things (likely subject to constraints of completing school work, chores, and other obligations). For another example, imagine that we are taking a cross country road trip to see national parks in the United States. We might seek to minimize time in the car and maximize time at the parks (here, time in the car might be considered “bad”).

Now that we’ve talked about a few of the general ideas in optimization, let’s consider a few examples of optimization problems and constraints for each problem:

     1.      Delivery routing – how do we deliver packages all over the city?

a.      Target variables for optimization:

                                                    i.     Total distance traveled (minimize)

                                                   ii.     Gas used (minimize)

                                                  iii.     Trucks used (minimize)

                                                  iv.     Packages Delivered (maximize)

                                                   v.     Time used (minimize)

b.      Possible constraints:

                                                    i.     Trucks need to drive on the roads and obey all traffic laws

                                                   ii.     Shifts for truck drivers cannot exceed 12 hours including two 15 minute breaks and a 1-hour lunch.

                                          iii.     Trucks can carry a maximum of 2,000 pounds of packages and are limited to 1200 cubic feet of packages.

     2.      Bin packing – We have a lot of things that we need to put in boxes. Items have different sizes, weights, and volumes and boxes have different dimensions and capacities. How do we minimize the number of boxes that we might use?

a.      Target variables for optimization

                                                    i.     Items packed (maximize)

                                                   ii.     Boxes used (minimize)

                                                  iii.     Empty space in boxes (minimize)

b.      Possible constraints

                                                    i.     Items packed in a box cannot exceed a box’s weight or volume capacity

                                                   ii.     Certain items may not be able to be packed together

      3.      Grocery store or bank lines. How do we handle a changing number of customers efficiently while minimizing wait times for checkout clerks (or bank tellers)?

a.      Target variables for optimization

                                                    i.     Wait times for customers (minimize)

                                                   ii.     Customers served per hour (maximize)

                                                  iii.     Idle time for customer service agents (minimize)

                                                  iv.     Open checkout lines/tellers (minimize)

                                                   v.     Overtime for agents (minimize)

b.      Possible constraints

                                                    i.     Minimum open lanes for any part of the day is 1

                                                   ii.     Maximum open lanes for any part of the day is 15

                                                  iii.     Employees need to be scheduled according to their scheduling constraints

      4.      Battleship (game)

a.      Target variables for optimization

                                                    i.     Turns to find all 17 points that need to be hit (minimize)

                                                   ii.     Number of misses (minimize)

                                                  iii.     Opponent’s turns to find all 17 points on my board (maximize)

b.      Constraints

                                         i.     100 possible points to target that are laid out in a 10 by 10 grid. Each point is identified by a letter (A-I) and number (1-10). Letters identify columns and numbers identify rows.

                                               ii.     Each player takes a turn that involves targeting a single point, opponent respons with hit or miss. If a particular hit sinks a ship, player says “sink.”

                                               iii.     Ships may lie on one row or column and have the following lengths: 5, 4, 3, 3, 2

                                                  iv.     Ships may not overlap or be placed on the diagonal

                                                   v.     Ships cannot move during the game once set

There are many different optimization problems that have been discovered and most problems are still being actively researched. Methods have been developed to produce some solutions for problems such as the truck delivery problem, but these solutions are not the globally optimal solutions to these problems. In many cases, optimum solutions can be found to reduced/simplified versions of these problems, but the solutions do not scale to non-simplified versions of these problems. It’s also possible that a globally optimal solution could be found, but finding it would take hundreds of years of computation time to search all possible solutions. Students and researchers who specialize in computer science and mathematics often work on some form of an optimization problem. Perhaps one day you will help find a globally optimal solution to one or more problems.

Materials

• Lab notebook
• Optimization schemes
• Game Boards
• Dry Erase Markers

Procedure

1. From the optimization scheme grab bag, grab an optimization scheme (this will be what you use to play your game)
2. Have your opponent(s) grab their optimization scheme
3. Setup your game board
4. Play your game using the optimization scheme
5. The first person to identify each hidden boat or candy on your game board wins.
6. Record the number of moves required to get to that outcome for both yourself and your opponent
7. Pick another optimization scheme and play again.
8. Record number of moves to win for the next set of schemes

Analysis and Conclusions

After playing a few rounds of the game with different optimization schemes, could you find one that seems to work better than others? What you should be able to see is that working line by line across the board is one of the least optimized schemes that you can do. You may also find that a scheme that allows you to skip a few spots then on the next line shift that scheme over may get you to an optimum outcome. The number and size of the ships/candy will affect your optimization.

Extension Activities

Try playing this game at home against your parents but do not tell them that you have learned to optimize your strategy. You may find that mom and dad are a bit taken-a-back by your amazing battleship skills. Now look at other things that you might be able to optimize. Think about different things that you would like to see work better or go faster and work through your ideas to optimize each. By doing these optimizations can you make things easier and quicker?