What do the following—planning an airline hub, political gerrymandering, and a museum renovation—have in common? They’re all problems that can be tackled by mathematicians using a process called optimization—and there are many more, says professor Adam Levy.
What Is Optimization?
Levy began a recent faculty seminar on the subject by posing the following problem: Imagine you are hiking Mount Katahdin (Maine’s highest peak), and you get stranded at the top as darkness falls (which once happened to him on a different mountain, he admitted.) You have no flashlight and you have to figure out a way down. You could listen for the sound of water, then follow the water to the bottom. Or, you could feel for painted trail-marks on rocks and trees (which is what he did). “Different methods of descent have different pros and cons,” he explained. “For example, following water may be fast, but could be dangerous, but they all should get you to the bottom; and they illustrate the mathematical principle of optimization in practice.
Optimization, in general terms, means finding the best outcome in some situation, said Levy, and in the case of being stranded on the summit of a mountain, the best outcome is getting safely to the bottom. “For other problems of interest, we can use so-called math mountains to represent a quantity we’d like to maximize or minimize, given our choices, and then use optimization methods to scale or descend that math mountain.”
Renovating a Museum: How might the theory of optimization be put to work to maximize the efficiency of a museum renovation? This was a question that occurred to Levy as he watched the two-year renovation of the Bowdoin College Museum of Art from his study, completed twelve years ago. He generated a list of nineteen essential tasks, their anticipated durations, and what, if any, preceding tasks had to be done before each of them.
The quantity to minimize in this case is the time to complete the renovation, so the corresponding math mountain has elevations determined by the completion times associated with different choices of start-times for the essential tasks. “Instead of the two choices of latitude and longitude to locate us on a topographic map of a real mountain, this problem has nineteen choices (one for each essential task). This means that the math mountain the general contractor needs to descend to renovate efficiently lives in a twenty-dimensional space.”
Planning an Airline Hub: An airline is going to want minimal switching of planes by passengers connecting through its hubs while using the same aircraft for arrivals and departures. And this is where optimization theory fits in, observed Levy. “We can reframe this as finding the summit of a math mountain representing the total number of passengers who remain on their original aircraft, for different choices of itineraries for the aircraft. An airline with thirty-five aircraft connecting through a hub needs to scale a math mountain in 352+1 = 1226 dimensions!”
Gerrymandering: The frowned-upon practice of manipulating district boundaries in order to favor one particular political party was once described as politicians picking their voters instead of voters picking their politicians.
The problem Levy sets out is how to partition a handful of central Maine towns into groups of three voting districts to ensure the ruling party is not a minority, a practice known as “dilution” gerrymandering. “There are fifteen towns and fifty-five valid voting districts. The challenge is to arrange them into groups of three, non-overlapping districts, or ‘trios,’ where the ruling party is not a minority. So, to continue the math mountain analogy, an elevation of zero would mean that the ruling party is a minority in all districts of that trio. The maximum elevation is three and corresponds to a trio of districts that is ‘dilution gerrymandered,’ meaning the opposition party’s influence has been curbed due to the location of the boundaries.”
“A Small Sample”: These examples are just the tip of iceberg, said Levy. “They’re a small sample of the kinds of things we can frame as optimization problems.” Pick pretty much any field of “real world” interest, he explained, and the questions and problems that arise in that area can often be framed as optimization problems. “Nature optimizes all the time, and people frequently try to.”
