(Thanks to Jeff Linderoth and Jean-Pierre Goux for coming up with the "bar30" QAP that is the inspiration for this story.)
So this Guy walks into a bar.
Guy was working on his business degree, but he needed a part time job. He'd applied all over town, and was his last shot. At the back of the dimly lit bar, a silhouette. "Can, I help you, son?" An Irish brogue. Clearly a Master bartender.
"Looking for a job."
"Do you have experience tending bar?"
"Absolutely."
"Don't try and fool me, son."
"Well, maybe once at a wedding."
"I like your style, kid. C'mon back."
Guy slid around the back of the bar. On top of the bar were two cardboard boxes containing 30 bottles of various sorts, and a huge pile of receipts. On the counter behind him there was a wooden 6 x 5 lattice: 30 slots for 30 bottles. "You want a job? Your first job is to get these bottles into these here holes. But do it right! We're going to be busy tonight, and I don't want to be dancing all over the place. Get those bottles in the right place!" Without another word, the Master went in to a small office in the back, to do who knows what.
Guy, an earnest fellow, thought about his task for a moment. "What does he mean, 'do it right'? I guess he means place the bottles that he uses at the same time close to each other. That way he won't have to dance around to get his job done."
Guy started to ask himself how he'd ever figure out which bottles the Master uses together. Just then he noticed the huge pile of receipts. "I can look at these receipts to see what kinds of drinks people are ordering. Then I can look in my bartender's guide to see which spirits I mix to make each drink. If I keep a log of all this then I can figure out how often, say, vodka is mixed with Red Bull, or 7-Up and grenadine." Guy smiled to himself. "I can do this. If I put the bottles in the holes, then I can figure out how far on average the Master will have to move. For each pair of bottles, I multiply the frequency that the bottles are used together in a drink with the distance between the bottles. If I add that up for all the pairs, I will know how far the Master will have to move around on average."
He thought for a moment.
"Crap. How am I ever going to find the best arrangement? How many different ways can I stick the bottles into the holes, anyway? Well, if there were two slots and two bottles, it would be easy: 1 2 or 2 1. If there were three, then there would be 3 x 2 = 6 ways: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1. So if there are 30 then its 30 x 29 x … x 2." Musing to himself he realized that was 2.6525285981219105863630848e+32 combinations, fewer than the number of atoms in the universe, but still an exceptionally large number. Not even his iPhone 4 could carry out such a computation by brute force.
At this point, a reasonable person would simply do their best. They'd do something simple, like find the most frequently used bottle and stick it in the middle, and then put its frequently used friends as close as possible. But Guy was not a reasonable man. Nothing meant more to him than getting - and keeping - this job, and he already knew from experience that nothing gets past the Master. But Guy was stuck. At that very moment, a tall rakishly handsome man holding a black book entered the room. You guessed it, it was me.
Guy explained his problem to me. I looked him straight in the eyes. "Dude, you've got a QAP."
"A what?"
"A quadratic assignment problem. You want to put each bottle in each hole. That's an assignment. You say you want to do it the best way you can. It sounds like 'best' means move as little as possible, and the amount of movement depends on the frequency of use times the distance between the holes. When you are multiplying unknowns together, that's quadratic. And you've definitely got a problem."
"Okay, so what do I do?"
"Divide and conquer, baby. Take a bottle and stick it in a hole."
"How do I know which one? And where? What if I get it wrong?"
"Just stick a bottle in a hole."
"Now what do you have?"
"Well, I've got the Smirnoff in the upper-left-hand corner."
"Yes, and 29 empty holes and 29 more bottles to place. Think about it: that's another QAP, just a smaller one. Let's assume you can find the best solution for the smaller problem. Now imagine putting the Smirnoff in all of the other holes, and solving those size 29 QAPs. If you know how to solve size 29 QAPs, then you will have your answer."
"I know where you're going with this, and I appreciate the advice, but I don't see how that helps. I don't know how to solve size 29 QAPs, except by solving a bunch of size 28 QAPs. And I can't keep doing this Russian doll stuff because there are too many combinations."
"True. But suppose you knew how rule out arrangements before you placed all the bottles. For example, say you try your best and come up with an arrangement where the Master consumes 800 calories a night. You know you can do at least that good. So suppose you have stuck 10 bottles in holes, but you've done a really bad job. In fact, you tally up the known cost with the 10 bottles and you're already over 800 calories, even with 20 bottles left to go. Then you know that there is no way that any solution involving that exact placement of the first 10 bottles is going to be the best. Ruling out partial placements is called 'fathoming'."
"Cool. But it still seems like we're going to have to try out an awful lot of combinations. I mean, how often can we really rule things out?"
"Well, you probably won't rule out too many that way. What you need to do is figure out better rules for fathoming. You need to deduce, given a partial placement of bottles, the minimum number of calories that any complete placement will take. And you want that deduction - that lower bound - to be as good as possible. If it is a good lower bound, then you will be able to eliminate partial solutions much sooner - maybe even after placing 4 or 5 bottles. If you can do that, then you may end up with a reasonable number of possibilities to check."
"I have no idea how to come up with a good lower bound."
"Here, read Chapter 2."
I made myself an Arnold Palmer as Guy proceeded to read Chapter 2 from the black book.
"Okay, so I project the problem into a lower dimensional space, solve the resulting quadratic program, and then I get a lower bound. Is that it?"
"That's one way to do it. There are others. Some of them go way back, to like, the 60s. The key is that you've got to do it every time you place a bottle, so whatever you do, you'd better do it fast."
"Fast. I can handle fast."
"One more tip."
"What's that?"
"When you are picking bottles to place - branching - be careful."
"Why is that?"
"Because the bound depends on the partial placement of the bottles. If you take the two bottles that are mixed together the most frequently - say vodka and Red Bull - I notice we are near a university - and put them in opposite corners, you will probably get a pretty large lower bound. That's good if it helps you rule out partial solutions quickly. What you want to do when you pick a bottle is make a selection that is likely to increase the lower bounds in the next round. Then you can rule out lots of possibilities. Sometimes the bounding procedure itself will give you hints. Do you know about dual values? Shadow prices?"
"Hell, no."
"Never mind. Just read Section 3.5. And do what it says." I hand the book to Guy, and start to edge towards the door.
"One more thing. You realize you don't actually have to try putting the Smirnoff in all 30 holes, right?"
"Seriously?"
"If you're putting the Smirnoff in the upper left hand corner, you don't need to try putting it in the upper right hand corner. Whatever solution you come up with on the left side case you can flip and use for the right side case. Symmetry."
"Symmetry. OK…"
"Section 3.6. Although I hear folks are into orbital branching these days...anyway...I've got to go. You can keep the book, I've got plenty. Hey - one more thing. And seriously, this is the last thing."
"What's that?"
"This ain't shuffleboard on a Carnival Cruise. You're going to need some help, even with all of these tricks. But most of what I told you about can be done in parallel."
"How's that?"
"Remember when I told you to try taking a bottle and sticking it in each of the possible holes? If you had a friend, and he tried half, and you tried half.... It's more complicated than that, but that's the idea."
"Got it." Guy looked through a doorway, where he saw another small bar with a virtually identical setup. "Do you think….?"
"Absolutely. What are friends for."
"Thanks. Hey, now I've got a question for you. I’m glad it worked out for me, but QAP sounds a little bit, you know, contrived. I mean, how often do they come up in real life, anyway?"
"Well, they don’t bump into you on the street, but contrived is a matter of opinion…I mean, this whole scene reminds me of the movie 'Cocktail'. I mean, there's an Irish bartender and everything. Isn’t that contrived too? And speaking of Tom Cruise movies, have you heard the theory about Top Gun?
"The Quentin Tarantino thing?"
"No...haven't heard that one. [Editor note: look that one up yourself…] Top Gun is actually a thinly veiled Quadratic Assignment Problem tutorial. Inside the jets: instrument panels. How to lay out the instruments on the panel? QAP. How to do the wiring on the circuit boards for the fancy targeting systems? QAP. How to balance the turbines? QAP. How to allocate crews to flight decks? QAP. They could hardly make it more obvious. Days of Thunder? Same deal."
"Cocktail, Top Gun, Days of Thunder. I suppose you're going to tell me that Interview With the Vampire is all about QAP too."
"You don't even want to know."
Shakira Leslie Bibb Chelsea Handler Salma Hayek Jennifer Scholle
No comments:
Post a Comment