Videos and Operations Research

Dick Larson has a very nice editorial in the April 2007 OR/MS Today on the use of videos in disseminating information about our field. One big point he makes is that the Edelman videos, a tremendous resource for our field, are not easily and freely available. This frustrates the heck out of me too! I do not understand why videos of the contestants are not up on YouTube right after the competition. There are some issues of ownership of the various INFORMS entities, but some INFORMS President will eventually be able to work them out and suddenly the world will be able to see how amazing we are.

Until then, Larson has another article on MIT World, where MIT professors give lectures on various topics. Arnie Barnett and Yossi Sheffi, along with Larson, are among those giving OR-oriented talks.

Incidentally, there are some “Operations Research” videos at YouTube but only 8 at the moment. Let’s see if things improve in the next year.

Operations Research and Turing Machines

From slashdot.com:

An anonymous reader writes “Stephen Wolfram, creator of Mathematica and author of A New Kind of Science, is offering a prize of $25K to anyone who can prove or disprove his conjecture that a particular 2-state, 3-color Turing machine is universal. If true, it would be the simplest universal TM, and possibly the simplest universal computational system. The announcement comes on the 5-year anniversary of the publication of NKS, where among other things Wolfram introduced the current reigning TM champion — ‘rule 110,’ with 2 states and 5 colors.”

Operations research (particularly integer programming) seems relevant to this work (through things like the undecidability of integer quadratic programming). $25,000 anyone?

Operations Research and Wikipedia

As part of my overview talk, I took a look at Operations Research in Wikipedia. Seeing a lack of pointer to this blog (which I think is a pretty good OR blog!), I went to fix it, but decided I had a Conflict of Interest, so reverted. I’ll leave it to others to decide if it should be added.

Anyway, I have mixed feelings about the OR section in Wikipedia. The long section on World War II applications simply reinforces the absolutely incorrect belief that OR may have been useful historically but has been superseded by newer, flashier methods. They are great stories, but they don’t really reflect the reality of OR today. I would much rather have summaries of recent Edelman finalists.

Some of this may be more general problems of describing science on Wikipedia, as this Wired blog entry by Thomas Goetz discusses:

Wikipedia is, by all measures, one of the great accomplishments of the Internet Age. I’m willing to say it stands alongside Google, eBay, GoogleMaps, IMDB and Wired.com as among the greatest resources on the Web (ok, that last one is self-serving).

But boy, does it suck when it comes to science topics.

Of course, there is nothing to stop me from doing some editing of the OR entry(short of COI), but I am trying to cut down on things I am doing. Perhaps someone will take it on as a weekend project. And I think an OR-oriented Wiki would be a great project.

Interaction of Computers and People

In a few days, I give a “public lecture” as part of the requirements for my Hood Fellowship that the University of Auckland gave me (I would have visited here anyway – New Zealand is wonderful – but the Fellowship was a very nice addition). Rather than trot out a version of my “sports scheduling” talk, I am giving an overview of OR talk. It is really quite a challenge. These overview talks can be quite a snooze for those in the audience who know OR, so I am thinking hard about the role OR has in the world, and the challenges the field faces. The “Science of Better” initiative of INFORMS has been very helpful in this regard.

One aspect I am exploring is the appropriate role of OR in decision making. While optimizers like me tend to be a bit impatient with this (“The best answer is this! Stop arguing with me and do it!!), the real-world is full of stuff that doesn’t appear in our models. In many (most?) applications, OR is an adjunct to decision making, not a replacement. Slate has an interesting article about this in the context of chess-playing programs that I may try to work into my talk.

Apologies in advance: the next few posts may be me trying to work through my thoughts in preparation for the talk.

Mathematical Puzzles, Martin Gardner, and Peter Winkler

I am certainly not alone when I say that interest in mathematics was sparked by Martin Gardner’s Mathematical Games column in Scientific American. I have a strong memory of many boring physics classes in high school which I whiled away reading through the stack of Scientific Americans in the corner. Those columns led to mathematics in university (where I probably not coincidently received a “D” in physics) and onward through my interest in discrete optimization.

While Gardner has long since stopped writing the column, his influence remains strong. Every year, a group of mathemeticians, magicians, jugglers, puzzle makers and so on meet at a “Gathering for Gardner“, a get-together that looks to be a blast!

Last year, Peter Winkler, formerly of Lucent and now at Darmouth, put together a set of puzzles, cleverly and correctly entitled “7 Puzzles You Think You Must Not Have Heard Correctly”. Here is one I particularly like:

The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.

The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed. Find a strategy for them which which has probability of success exceeding 30%. Comment: If each prisoner examines a random set of 50 boxes, their probability of survival is an unenviable 1/2^100 = 000000000000000000000000000008. They could do worse if they all look in the same 50 boxes, their chances drop to zero. 30% seems ridiculously out of reach but yes, you heard the problem correctly.

Is this really possible? Check out Peter’s writeup for the solution (and seven other problems). Also check out his book for more.

Major League Baseball Scheduling

Peter Theis and Jeremy Hastings, MBA students at my home base, the Tepper School of Business at Carnegie Mellon, have independently reminded me that I have been getting some press about the baseball schedule that I should be pointing to. Not all of it has been positive, but most of it talks about how difficult creating satisfying schedules is. For those who don’t know, some colleagues (Doug Bureman, George Nemhauser and Kelly Easton) and I, through our company the Sports Scheduling Group, created the 2005 and 2007 Major League Baseball Schedule. ESPN.com has an article on the 2007 schedule. They talk about some of the rough parts of the schedule:

For baseball players, grousing about the schedule is as routine as chewing sunflower seeds or making rookies wear cocktail dresses and high heels to the airport during the obligatory hazing trip. The average fan might regard it as just another case of millionaires whining, but fans don’t have to step in the box in front of 50,000 people and produce while bleary-eyed and jet-lagged.

Listen closely, and you’ll hear the Pittsburgh Pirates groaning en masse as they look at their schedule and contemplate that geographically challenged Houston-to-San Diego-to-Chicago trip in late September.

Or consider how thrilled the Texas Rangers must be looking forward to a nine-game Detroit-to-Oakland-to-Minnesota jaunt (with no day off) in the final month.

But ESPN.com also talks about the challenges:

Each team has its own unique circumstances. Cincinnati is always home on Opening Day, while Boston plays at Fenway Park each Patriots Day. The Mets have potential traffic and parking concerns when the U.S. Open tennis tournament is in town, and the Minnesota Twins share the Metrodome with the NFL’s Vikings.

And lest we forget, New York, Chicago, Los Angeles, the San Francisco Bay Area and Baltimore-Washington are all two-team markets. In a perfect world, one team will be at home while the other is on the road.

Throw in six pages of whys and wherefores governing scheduling in the collective bargaining agreement, and you have an extremely complicated jigsaw puzzle.

“You can take any short part of a team’s schedule and say, ‘That’s awful. Why would anybody schedule that?'” Feeney said. “But you can’t look at it that way. It’s not a two-week schedule. It’s a 26-week, 30-team schedule.'”

There have also been articles in the San Jose Mercury News and the Seattle Times. The News has the most depressing line (at least to me):

Starting next season, MLB will create the schedule within its offices. In other words, no more outside consultants.

Not happy news for the Sports Scheduling Group!

And another OR Blog

I realize have have neglected pointing to one of the oldest OR blogs, “FM Waves” by Francesco Marco-Serrano, which started in February 2005. With the subtitle of “The dark side of an operations researcher. Or how operations research can be a funny subject. Wanna join me?”, this is an eclectic, wide-ranging blog. Fracesco has taken up the Netflix challenge that I wrote about.

Laura McLay Blog

Looks like we are getting a few more operations research blogs. Laura McLay of Virginia Commonwealth has a “Punk Rock Operations Research” blog. I particularly like her post on “Humanitarian Logistics“, based on the work of Dave Goldsman of Georgia Tech. Here is an excerpt:

The talk summarized some of Dr. Goldman’s experiences in applying simulation to problems in health clinic management/flow and the spread of Guinea worms in Africa. Guinea worms are particularly interesting. Guinea worms are parasites that are contracted by drinking contaminated water. Once contracted, they eat their way out of the body and reproduce. Breaking the chain results in extermination. This can be easily accomplished by filtering water. However, because of the civil war in Sudan, many soldiers walk home, contracting Guinea worms along the way. Finding a strategy for targeting resources is important for completely eradicating the Guinea worm. The research was funded by the Carter Center, and apparently, Jimmy Carter’s work has nearly eradicated the Guinea worm already.

There was a series of articles in the New York Times a few months ago on the various parasites that plague the world: the pictures ruined a number of breakfasts at the Trick house. I am glad to see that OR may be helping with this problem.

Good to see the blog, and into the “blogroll” it goes!

American Idol Voting is Flawed

Just to prove that operations research is relevant everywhere, Ed Kaplan of Yale University has pointed out a fundamental flaw in the voting process for American Idol. It appears that lots of people get busy signals when trying to vote for “their” idol. This may appear to be simply a frustration but actually gets to the heart of the fairness of the voting system. As Ed argues in an op-ed at the Hartford Courant, if votes are limited due to phone capacity, and each candidate has a separate line (each with the same capacity), then the votes will by necessity be much more evenly spread than the electorate. So a runaway winner can turn into a coin-toss.

In the best OR tradition, Ed not only identifies the problem but solves it:

There is a simple solution to this problem that does not require “American Idol” to install additional phone capacity. Instead of assigning each contestant a personal phone number, use a single number for all voting, and have voters select their favorite by pushing a button after the call has gone through. This simple fix would equalize the chance of encountering a busy signal for all callers.

Many votes would still be lost. In fact, if the total phone capacity was left unchanged, more calls would be lost due to the increase in processing time per call necessitated by button-pushing. But, since all calls would have the same chance of getting through, the total votes received would be a representative sample of votes cast.

If only OR people ran the world, even American Idol would run better.