Figure 8.1 The shortest traveling salesman route (top) and minimum spanning tree (bottom) for Lincoln’s 1855 judicial circuit.
Even better, in the traveling salesman problem it turns out that the minimum spanning tree is actually one of the best starting points from which to begin a search for the real solution. Approaches like these have allowed even one of the largest traveling salesman problems imaginable—finding the shortest route that visits every single town on Earth—to be solved to within less than 0.05% of the (unknown) optimal solution.
Though most of us haven’t encountered the formal algorithmic version of Constraint Relaxation, its basic message is familiar to almost anyone who’s dreamed big about life questions. What would you do if you weren’t afraid? reads a mantra you might have seen in a guidance counselor’s office or heard at a motivational seminar. What would you do if you could not fail? Similarly, when considering questions of profession or career, we ask questions like What would you do if you won the lottery? or, taking a different tack, What would you do if all jobs paid the same? The idea behind such thought exercises is exactly that of Constraint Relaxation: to make the intractable tractable, to make progress in an idealized world that can be ported back to the real one. If you can’t solve the problem in front of you, solve an easier version of it—and then see if that solution offers you a starting point, or a beacon, in the full-blown problem. Maybe it does.
What relaxation cannot do is offer you a guaranteed shortcut to the perfect answer. But computer science can also quantify the tradeoff that relaxation offers between time and solution quality. In many cases, the ratio is dramatic, a no-brainer—for instance, an answer at least half as good as the perfect solution in a quadrillionth of the time. The message is simple but profound: if we’re willing to accept solutions that are close enough, then even some of the hairiest problems around can be tamed with the right techniques.
Temporarily removing constraints, as in the minimum spanning tree and the “what if you won the lottery?” examples, is the most straightforward form of algorithmic relaxation. But there are also two other, subtler types of relaxation that repeatedly show up in optimization research. They have proven instrumental in solving some of the field’s most important intractable problems, with direct real-world implications for everything from city planning and disease control to the cultivation of athletic rivalries.
Uncountably Many Shades of Gray: Continuous Relaxation
The traveling salesman problem, like Meghan Bellows’s search for the best seating arrangement, is a particular kind of optimization problem known as “discrete optimization”—that is, there’s no smooth continuum among its solutions. The salesman goes either to this town or to that one; you’re either at table five or at table six. There are no shades of gray in between.
Such discrete optimization problems are all around us. In cities, for example, planners try to place fire trucks so that every house can be reached within a fixed amount of time—say, five minutes. Mathematically, each fire truck “covers” whatever houses can be reached within five minutes from its location. The challenge is finding the minimal set of locations such that all houses are covered. “The whole [fire and emergency] profession has just adopted this coverage model, and it’s great,” says University of Wisconsin–Madison’s Laura Albert McLay. “It’s a nice, clear thing we can model.” But since a fire truck either exists at a location or it doesn’t, calculating that minimal set involves discrete optimization. And as McLay notes, “that’s where a lot of problems become computationally hard, when you can’t do half of this and half of that.”
The challenge of discrete optimization shows up in social settings, too. Imagine you wanted to throw a party for all your friends and acquaintances, but didn’t want to pay for all the envelopes and stamps that so many invitations would entail. You could instead decide to mail invitations to a few well-connected friends, and tell them to “bring everyone we know.” What you’d ideally want to find, then, is the smallest subgroup of your friends that knows all the rest of your social circle—which would let you lick the fewest envelopes and still get everyone to attend. Granted, this might sound like a lot of work just to save a few bucks on stamps, but it’s exactly the kind of problem that political campaign managers and corporate marketers want to solve to spread their message most effectively. And it’s also the problem that epidemiologists study in thinking about, say, the minimum number of people in a population—and which people—to vaccinate to protect a society from communicable diseases.
As we noted, discrete optimization’s commitment to whole numbers—a fire department can have one engine in the garage, or two, or three, but not two and a half fire trucks, or π of them—is what makes discrete optimization problems so hard to solve. In fact, both the fire truck problem and the party invitation problem are intractable: no general efficient solution for them exists. But, as it turns out, there do exist a number of efficient strategies for solving the continuous versions of these problems, where any fraction or decimal is a possible solution. Researchers confronted with a discrete optimization problem might gaze at those strategies enviously—but they also can do more than that. They can try to relax their discrete problem into a continuous one and see what happens.
In the case of the invitation problem, relaxing it from discrete to continuous optimization means that a solution may tell us to send someone a quarter of an invitation, and someone else two-thirds of one. What does that even mean? It obviously can’t be the answer to the original question, but, like the minimum spanning tree, it does give us a place to start. With the relaxed solution in hand, we can decide how to translate those fractions back into reality. We could, for example, choose to simply round them as necessary, sending invitations to everyone who got “half an invitation” or more in the relaxed scenario. We could also interpret these fractions as probabilities—for instance, flipping a coin for every location where the relaxed solution tells us to put half a fire truck, and actually placing a truck there only if it lands heads. In either case, with these fractions turned back to whole numbers, we’ll have a solution that makes sense in the context of our original, discrete problem.
The final step, as with any relaxation, is to ask how good this solution is compared to the actual best solution we might have come up with by exhaustively checking every single possible answer to the original problem. It turns out that for the invitations problem, Continuous Relaxation with rounding will give us an easily computed solution that’s not half bad: it’s mathematically guaranteed to get everyone you want to the party while sending out at most twice as many invitations as the best solution obtainable by brute force. Similarly, in the fire truck problem, Continuous Relaxation with probabilities can quickly get us within a comfortable bound of the optimal answer.
Continuous Relaxation is not a magic bullet: it still doesn’t give us an efficient way to get to the truly optimal answers, only to their approximations. But delivering twice as many mailings or inoculations as optimal is still far better than the unoptimized alternatives.
Just a Speeding Ticket: Lagrangian Relaxation
Vizzini: Inconceivable!
Inigo Montoya: You keep using that word. I do not think it means what you think it means.
—THE PRINCESS BRIDE
One day as a child, Brian was complaining to his mother about all the things he had to do: his homework, his chores.… “Technically, you don’t have to do anything,” his mother replied. “You don’t have to do what your teachers tell you. You don’t have to do what I tell you. You don’t even have to obey the law. There are consequences to everything, and you get to decide whether you want to face those consequences.”
Brian’s kid-mind was blown. It was a powerful message, an awakening of a sense of agency, responsibility, moral judgment. It was something else, too: a powerful computational technique called Lagrangian Relaxation. The idea behind Lagrangian Relaxation is simple. An optimization problem has two parts: the rules and the scor
ekeeping. In Lagrangian Relaxation, we take some of the problem’s constraints and bake them into the scoring system instead. That is, we take the impossible and downgrade it to costly. (In a wedding seating optimization, for instance, we might relax the constraint that tables each hold ten people max, allowing overfull tables but with some kind of elbow-room penalty.) When an optimization problem’s constraints say “Do it, or else!,” Lagrangian Relaxation replies, “Or else what?” Once we can color outside the lines—even just a little bit, and even at a steep cost—problems become tractable that weren’t tractable before.
Lagrangian Relaxations are a huge part of the theoretical literature on the traveling salesman problem and other hard problems in computer science. They’re also a critical tool for a number of practical applications. For instance, recall Carnegie Mellon’s Michael Trick, who, as we mentioned in chapter 3, is in charge of scheduling for Major League Baseball and a number of NCAA conferences. What we hadn’t mentioned is how he does it. The composition of each year’s schedule is a giant discrete optimization problem, much too complex for any computer to solve by brute force. So each year Trick and his colleagues at the Sports Scheduling Group turn to Lagrangian Relaxation to get the job done. Every time you turn on the television or take a seat in a stadium, know that the meeting of those teams on that court on that particular night … well, it’s not necessarily the optimum matchup. But it’s close. And for that we have not only Michael Trick but eighteenth-century French mathematician Joseph-Louis Lagrange to thank.
In scheduling a sports season, Trick finds that the Continuous Relaxation we described above doesn’t necessarily make his life any easier. “If you end up with fractional games, you just don’t get anything useful.” It’s one thing to end up with fractional allocations of party invitations or fire trucks, where the numbers can always be rounded up if necessary. But in sports, the integer constraints—on how many teams play a game, how many games are played in sum, and how many times each team plays every other team—are just too strong. “And so we cannot relax in that direction. We really have got to keep the fundamental [discrete] part of the model.”
Nonetheless, something has to be done to reckon with the sheer complexity of the problem. So “we have to work with the leagues to relax some of the constraints they might like to have,” Trick explains. The number of such constraints that go into scheduling a sports season is immense, and it includes not only the requirements arising from the league’s basic structure but also all sorts of idiosyncratic requests and qualms. Some leagues are fine with the second half of the season mirroring the first, just with home and away games reversed; other leagues don’t want that structure, but nonetheless demand that no teams meet for a second time until they’ve already met every other team once. Some leagues insist on making the most famous rivalries happen in the final game of the season. Some teams cannot play home games on certain dates due to conflicting events at their arenas. In the case of NCAA basketball, Trick also has to consider further constraints coming from the television networks that broadcast the games. Television channels define a year in advance what they anticipate “A games” and “B games” to be—the games that will attract the biggest audience. (Duke vs. UNC is a perennial A game, for instance.) The channels then expect one A game and one B game each week—but never two A games at the same time, lest it split the viewership.
Unsurprisingly, given all these demands, Trick has found that computing a sports schedule often becomes possible only by softening some of these hard constraints.
Generally, when people first come to us with a sports schedule, they will claim … “We never do x and we never do y.” Then we look at their schedules and we say, “Well, twice you did x and three times you did y last year.” Then “Oh, yeah, well, okay. Then other than that we never do it.” And then we go back the year before.… We generally realize that there are some things they think they never do that people do do. People in baseball believe that the Yankees and the Mets are never at home at the same time. And it’s not true. It’s never been true. They are at home perhaps three games, perhaps six games in a year at the same day. But in the broad season, eighty-one games at home for each of the teams, it’s relatively rare, people forget about them.
Occasionally it takes a bit of diplomatic finesse, but a Lagrangian Relaxation—where some impossibilities are downgraded to penalties, the inconceivable to the undesirable—enables progress to be made. As Trick says, rather than spending eons searching for an unattainable perfect answer, using Lagrangian Relaxation allows him to ask questions like, “How close can you get?” Close enough, it turns out, to make everyone happy—the league, the schools, the networks—and to stoke the flames of March Madness, year after year.
Learning to Relax
Of the various ways that computational questions present themselves to us, optimization problems—one part goals, one part rules—are arguably the most common. And discrete optimization problems, where our options are stark either/or choices, with no middle ground, are the most typical of those. Here, computer science hands down a disheartening verdict. Many discrete optimization problems are truly hard. The field’s brightest minds have come up empty in every attempt to find an easy path to perfect answers, and in fact are increasingly more devoted to proving that such paths don’t exist than to searching for them.
If nothing else, this should offer us some consolation. If we’re up against a problem that seems gnarly, thorny, impassable—well, we might be right. And having a computer won’t necessarily help.
At least, not unless we can learn to relax.
There are many ways to relax a problem, and we’ve seen three of the most important. The first, Constraint Relaxation, simply removes some constraints altogether and makes progress on a looser form of the problem before coming back to reality. The second, Continuous Relaxation, turns discrete or binary choices into continua: when deciding between iced tea and lemonade, first imagine a 50–50 “Arnold Palmer” blend and then round it up or down. The third, Lagrangian Relaxation, turns impossibilities into mere penalties, teaching the art of bending the rules (or breaking them and accepting the consequences). A rock band deciding which songs to cram into a limited set, for instance, is up against what computer scientists call the “knapsack problem”—a puzzle that asks one to decide which of a set of items of different bulk and importance to pack into a confined volume. In its strict formulation the knapsack problem is famously intractable, but that needn’t discourage our relaxed rock stars. As demonstrated in several celebrated examples, sometimes it’s better to simply play a bit past the city curfew and incur the related fines than to limit the show to the available slot. In fact, even when you don’t commit the infraction, simply imagining it can be illuminating.
The conservative British columnist Christopher Booker says that “when we embark on a course of action which is unconsciously driven by wishful thinking, all may seem to go well for a time”—but that because “this make-believe can never be reconciled with reality,” it will inevitably lead to what he describes as a multi-stage breakdown: “dream,” “frustration,” “nightmare,” “explosion.” Computer science paints a dramatically rosier view. Then again, as an optimization technique, relaxation is all about being consciously driven by wishful thinking. Perhaps that’s partly what makes the difference.
Relaxations offer us a number of advantages. For one, they offer a bound on the quality of the true solution. If we’re trying to pack our calendar, imagining that we can magically teleport across town will instantaneously make it clear that eight one-hour meetings is the most we could possibly expect to fit into a day; such a bound might be useful in setting expectations before we face the full problem. Second, relaxations are designed so that they can indeed be reconciled with reality—and this gives us bounds on the solution from the other direction. When Continuous Relaxation tells us to give out fractional vaccines, we can just immunize everyone assigned to receive half a vaccine or more, and end up with an ea
sily calculated solution that requires at worst twice as many inoculations as in a perfect world. Maybe we can live with that.
Unless we’re willing to spend eons striving for perfection every time we encounter a hitch, hard problems demand that instead of spinning our tires we imagine easier versions and tackle those first. When applied correctly, this is not just wishful thinking, not fantasy or idle daydreaming. It’s one of our best ways of making progress.
*It may look strange, given that O(n2) seemed so odious in the sorting context, to call it “efficient” here. But the truth is that even exponential time with an unassumingly small base number, like O(2n), quickly gets hellish even when compared to a polynomial with a large base, like n10. The exponent will always overtake the polynomial at some problem size—in this case, if you’re sorting more than several dozen items, n10 starts to look like a walk in the park compared to 2n. Ever since Cobham and Edmonds’s work, this chasm between “polynomials” (n-to-the-something) and “exponentials” (something-to-the-n) has served as the field’s de facto out-of-bounds marker.
Algorithms to Live By Page 22