Now, please understand that I am not a geologist and have no expertise about drilling for oil. But I do understand that when the price of something goes up, one of two amazing things happen (or a mixture of the two): demand goes down, or people find a way to supply more.
It hurts to fill up the car with gas these days, but here are two independent stories that are different from the usual gloom and doom we read everyday: oil field development in North Dakota and the Falkland Islands.
Now for non-geeks, what does the cartoon in part one mean? When thinking about finding the optimal solution to a problem, one question is how “hard” is the problem. If there are only two solutions, then you could probably spend the time to evaluate both and pick the better one. Most problems have many solutions, and so any algorithm to find the best is going to have to evaluate some number of potential solutions in order to find the best.
This leads to the “order” notation, O(n). What this says is the problem is “order n” and that while we might not know the exact time to evaluate each possible solution, we know we are going to have to check about “n” of them.
Now the traveling salesman problem (TSP) is one where we have to visit some number of locations, one after the other. Suppose I sell golf balls and want to visit five different golf courses today. I start at my house, and I go to one of the golf courses. From there I can choose one of the remaining four. From there, I choose one of the three, and so on, until I return home at the end of the day. How many different ways are there to do this? Turns out that this is the number of permutations of the five (and if you count your home, actually six) locations, and the number of permutations is given by n! = n(n-1)(n-2)…(2)(1). One way to solve the problem is to check every solution, all n! of them.
Suppose there are 10 locations to visit, and that your laptop computer can figure out the length of a trip with a certain visiting sequence in one thousandth of a second. You can come back to your computer in about an hour for the solution. What happens if you add two locations to visit. The awful truth about factorials is they grow like crazy, and now your computer needs five days to find the solution. What to solve 15 locations? It will take your computer 40 years. Ouch.
So geeks try to find sneaky ways to evaluate all the “good” solutions, and implicitly check the others without doing any work. Dynamic programming is one of the sneaky methods for evaluating only some of the possible solutions, but still knowing that the best of the ones you find is better than all of the possible n! solutions. The algorithm in the cartoon is O(n^2 x 2^n). So for 10 locations, we can solve the problem in about one second (instead of an hour). Twelve locations takes four seconds, and 15 takes about a minute. Much better than 40 years!
So geeks win? Not so fast. Try thirty locations — 12 days. Thirty-five locations? A year. Forty locations? 35 years. Don’t even think about 100 locations…
What does O(1) mean? The third panel guy can sell to 100 golf courses by doing just one thing. Okay, you need to have a particularly warped sense of humor to find that funny. But such senses of humor do exist (me, unfortunately).
If you’ve read this far, thanks. But is this problem really important? Do salesmen really do this? Well think about oil delivery trucks or a beer distributor who restocks convenience stores. Lots of locations, lots of choices about who to visit today, and who to visit tomorrow, and the price of gas for your truck keeps going up.
Or think about making printed circuit boards. A robot arm (usually) picks the chips from a storage position (sometimes attached to a tape) and puts them on the board in a particular location. The optimal sequence (the shortest trip to visit the n chip sites on the board) may take a lot less time than a non-optimal one, increasing costs and reducing capacity. Could there be 100 chips on a board? Sure.
We all see barcodes in action at most retail stores, and the increased accuracy that technology allows in collecting sales information opened up all kinds of analysis. A newer technology, radio frequency identification (RFID) takes this one step further by putting a chip on the merchandise that can talk to computers. IBM has a commercial where a truck is lost and it stops at an IBM help desk in the middle of the desert. The drivers ask how the help desk person knew they were lost. She says “the inventory told us.” If the RFID tags know they are supposed to be heading east and they start going north, they could send out a “help us” message. Or a supermarket could tag everything, and when you go to the checkout, a computer could read all of the tags in your cart all at once. Cool, huh?
But one interesting part of technology is that the intended use and the actual uses often diverge. Here’s a company with an interesting application of RFID. Watch where you walk.
The traveling salesman problem is one of a class of “hard” problems, where even if you have insanely fast computers, the solution cannot be verified for thousands of years.
Of course, if you shift the problem setting slightly, the problem can become much easier.
note: this is a geek comic, and I will post what the notation means, and why it is funny (to a certain set of people) in a later post…
Science depends on statistics to allow us to “know” something. We experiment and show differences and try to show that those differences are not just random, but show some underlying effect.
Sometimes, even statistics are not enough, when enough people in a field are convinced of the current theories — which are theories because they can never be “proved.” An example is the struggle of two scientists who saw the data tell them that ulcers were not caused by what “everyone” knew they were caused by, but rather by a bacteria. Publishing their results was frustrated because the reviewers knew they must be wrong.
Lucky for us they persevered, and eventually on the Nobel Prize.
Most business schools that are ranked among the best in the country have been named after a significant donor. Tuck, Sloan, Wharton, Stern, Fuqua, Simon (my alma mater) among others. Of course there are the exceptions who have enough money to not need someone’s name — Harvard and Stanford, for example. Then there are schools with no name that could find wonderful uses for such a gift. UConn, for example.
Wisconsin has found a way to have it both ways, when a group of alumni got together to give the school $85 million to not allow the name to be changed. So it will be the Wisconsin School of Business, at least for the next twenty years.
Here is a small album that I’ve used for the study abroad fair. Most of the pictures are Italy, but there are a few from Ireland, the Netherlands, Switzerland, Barcelona, Denmark and Guatemala. I will put up a more complete set of pictures from the 2007 Florence business program a little later.
Ok, you have to be warned that there’s a bit of less-than-polite language, but this is an interesting explanation of the subprime mortgage mess. I’m sure there was also some sophisticated modeling involved that, unfortunately, depended on an assumption that gets mentioned in the link. That assumption is not holding, and so the modeling has not played out as expected.
The same queueing effects we see in operations happens on the road every day — you can come across a lengthy backup on the Merritt Parkway and find that there was no accident or other “cause” for the delay. This article links to some work in this area. Small amounts of variability have more power to affect things than people realize.
Hal Varian is a very smart guy who was at UC Berkely and is now at Google. Here’s an interview in the NY Times, and an earlier one in the Wall Street Journal. Good reading and some good advice.