Scheduling Major League Baseball

ESPN has a new “30 for 30” short video on the scheduling of Major League Baseball.  In the video, they outline the story of Henry and Holly Stephenson who provided Major League Baseball with its schedule for twenty-five years.  They were eventually supplanted by some people with a computer program.  Those people are Doug Bureman, George Nemhauser, Kelly Easton, and me, doing business as “Sports Scheduling Group”.

It was fascinating to hear the story of the Stephensons, and a little heart-breaking to hear them finally losing a job they obviously loved.  I have never met Henry or Holly, and they have no reason to think good thoughts about me.  But I think an awful lot of them.

I began working on baseball scheduling in 1994, and it took ten years of hard work (first Doug and me, then the four of us) before MLB selected our schedule for play.

Why were we successful in 2004 and not in 1994? At the core, technology changed. The computers we used in 2004 were 1000 times faster than the 1994 computers. And the underlying optimization software was at least 1000 times faster. So technology made us at least one million times faster. And that made all the difference. Since then, computers and algorithms have made us 1000 times faster still.  And, in addition, we learned quite a bit about how to best do complicated sports scheduling problems.

Another way to see this is that in 1994, despite my doctorate and my experience and my techniques, I was 1 millionth of the scheduler that the Stephensons were. Henry and Holly Stephenson are truly scheduling savants, able to see patterns that no other human can see. But eventually technological advances overtook them.

More recently, those advances allowed us to provide the 2013 schedule with interleague play in every time slot (due to the odd number of teams in each league), something not attempted before. I am confident that we are now uniquely placed to provide such intricate schedules. But that does not take away from my admiration of the Stephensons: I am in awe of what they could do.



Watch the Edelmans!

I have said numerous times that the Edelman Prize presentations and papers are my favorite part of the operations research world.   It is fantastic to see and read about such great work in operations research.  The presentations often feature a Cxx of the firm.  Watching business leaders explain the importance of operations research never gets old to me.  And some of them actually read the script with feeling and (seeming) understanding (others look like they are reading under duress, with uzi’s pointed at them from just offscreen).

The Edelman’s have all been recorded through the years, and INFORMS (the professional organization that runs the Prize)  has experimented with how best to distribute the results.  We have gone from video tapes to DVDs to YouTube snippits.  There was always an issue of monetizing the presentations.  If this is our field’s best work, surely we can make money on it!  But making money limits distribution.

At least for now, INFORMS seems to have given up the money aspect, and even any membership aspect, and offers the most recent Edelman presentations for the low, low cost of a site registration.  Once you register, you can see all sorts of neat videos.  In addition to the Edelman finalists, there are Richard O’Neill’s talk on energy markets  (he is the chief economic adviser to the Federal Energy Regulatory Commission), Chris Tang’s talk on supply chain risk management, and the Wagner Prize finalists.  For all, there is a proprietary presentation which shows both the powerpoint slides and the speaker.

I do have one big complaint about this setup, however.  The system, as currently designed, appears to fall into a trap that operations research often sets for itself.  If you know you want what the system offers, it is easy to work with:  registration is fast and relatively non-intrusive.  But the listing of the videos is “behind the wall”, so someone interested in, say, energy markets, has no idea that this site would have a great talk on the subject.   Why aren’t all the talk titles and abstracts freely available?  Better yet, why bother with registration?  Based on the privacy agreement, it does not appear that INFORMS can even market to those who register.  Why hide anything?

For those of us in the know, this is a tremendous resource!  For those of you who have not yet discovered the beauty, fun, interest and (particularly) importance of operations research, I strongly urge you to go to the site and explore.  It might change your life.

Advertising Operational Research (but maybe a few updates are in order?)

The Operational Research Society (the U.K. equivalent of INFORMS) has a website about operational research (the U.K. equivalent of operations research) aimed at students and teachers called Learn about OR. This makes a great adjunct to the INFORMS site, the Science of Better, aimed at business. Lots of good examples and good advice about getting into the field.

For portions, however, the site shows the tone-deafness that we in OR often show. Some of the examples might be a little more relevant to a 50-year-old rather than a teenager. Consider the example aimed at 11-14 year olds “OR Inside Your Holiday Snaps”:

It’s highly unlikely that, while you were snapping your holiday photos on the beach, you stopped to think, ‘Is there O.R. inside the film in this camera’? But, in fact, there is!

Photographic film is manufactured in rolls about 6km long by 1m wide, which have to be cut up into complex patterns so as to produce a wide variety of products. The problem of deciding how to cut the rolls is very complicated

What a great example: cutting photographic film is a wonderful example leading to column generation approaches and other advanced math programming methods. Too bad the average twelve year old hasn’t ever seen photographic film. I look forward to examples of fitting music onto cassette tape cartridges and optimal horse rotation for mail delivery.

Despite this cavilling, it is a good site, and the sort of site the world needs more of. There is even a introductory video that covers the range of OR (with instructions for downloading to an ipod).

Thanks Dawen, of ThinkOR, for mentioning the site in a somewhat different context.

Arnoff Lecture by Keeney, Having Children, and Decision Analysis

Last year around this time, I was giving the 17th Arnoff Lecture at the University of Cincinnati, which was a great thrill. This year, the Arnoff Lecturer was Ralph Keeney who spoke on “Making Informed Business, Health, and Personal Decisions”. Keeney was the author of an OR Forum Paper on how personal decisions are a leading cause of death. The organizers have put a video of the lecture online.

The Lecture contained a review of Ralph’s work on personal health decisions and his earlier work on placing a nuclear waste site. The third topic was my favorite: when should a woman decide to start a family? Being an older parent (I am 49, with Alexander being 5 in a couple of weeks) it is interesting to see how such a decision analysis might be done. Near as I can recall, this was a non-issue until I was 44 when Ilona told me I was about to be a father (at which point I watched “Finding Nemo” to see a possibly fatherly role I might have to take on). Ilona might have a different view of the decision process, though I do not believe it involved explicit utility curves.

I’m ready for my close-up Mr. DeMille, the Operations Research Version

If all goes according to plan, the members of INFORMS will receive an email over the next two days.  The email outlines some reasons why you should attend the upcoming INFORMS Practice Meeting (note that you need to register by April 1 in order to get a discount on the registration fee).  Part of the email is a video featuring … me!  In my two minute schtick, I try to give you some reasons why I like the INFORMS Practice conference so much.

I found the video really hard to do.  I vacillated between spontaneous and rigid.  When spontaneous, I had enough verbal tics that it was unwatchable.  “I, um, really like the INFORMS Practice Conference, you know, um, because, um…”  Arghh!  The other extreme made me look as though madmen had captured my loved ones and were forcing me to to read their manifesto against my will.  So I tried to split the difference in the final video.  Perhaps now it looks like I am being forced to read the manifesto with a verbal tic.  As my wife said “It was fine, but you are no actor”.  Despite that, you really should think about attending the INFORMS Practice Conference:  it is inspiring to see what our field does in the real world.

If you can’t wait for the email, you can check it out here.

Pulleyblank Lecture at Georgia Tech

Bill Pulleyblank, Vice President, Center for Business Optimization, IBM (I have written about CBO before) gave a talk at Georgia Tech on April 17.   The title was “Computing, Business, and Operations Research: The Next Challenges”.  Here is the abstract:

 There have been two consistent drivers over the last sixty years of the evolution of computing: Computer power and price/performance improve by a factor of two every eighteen months; the problems that we wish to solve require this growth in capability and more. We seem to be reaching inflection points with both of these drivers. High performance systems are turning to massive parallelism to continue the required growth in performance. New challenges are arising in business and industry that require the solution of fundamentally different problems as well as the development of new approaches to old problems. Moreover, the rapid growth of a global economy has given an unprecedented urgency to dealing with these changes. I will review these subjects and some approaches that are being applied, with varying degrees of success. In particular, I will discuss five technical problems that must be solved to enable us to successfully meet the business challenges that we will face in the future.

Bill was a plenary speaker at INFORMS Pittsburgh 2006,  and I thought his talk was one of the highlights of the conference.  Georgia Tech has made a video and his slides available.

Ant Colonies in the Skies

“Discoveries and Breakthroughs in Science” is a producer of short TV clips on results in math and science. INFORMS is involved with them, and is seeking story ideas to pitch to them.

This month’s mathematics story is about using ant colony optimization to help run an airport, with an emphasis on the gate assignment problem.

“It’s sort of like a colony of individuals trying to move through a maze with all of the other individuals present, arriving and departing and trying to do it as fast as they can,” Douglas Lawson, Ph.D., a financial analysis manager at Southwest Airlines in Dallas, Texas, told Ivanhoe.

The software program uses swarm theory, or swarm intelligence — the idea that a colony of ants works better than one alone. Each pilot acts like an ant searching for the best airport gate. “The pilot learns from his experience what’s the best for him, and it turns out that that’s the best solution for the airline,” Dr. Lawson explains.

I’m not a huge fan of Ant Colony Optimization: it has always seemed overblown to me. But the proof is in the results, so if this does work better than alternative approaches, then that’s great. I have not found Lawson’s work on this on the web, but gate assignment has been tried with ACO (see here and here) and other forms of swarm intelligence, and Lawson is the “Manager of Process, Forecasting, and Simulations” at Southwest, an admirable airline, so it is interesting to see him using this in practice.

One thing bothered me and one thing I found humorous. First, Lawson and his team are described as “financial analysts”. Is the “Manager of Process, Forecasting and Simulations” a financial analyst? My guess is that the TV producers decided not to make the big step and call him “operations researcher” so they went with a word they thought the audience would know.

The humorous part comes in the background information where they describe swarm intelligence:

HOW DO SWARMS OPERATE? How do ants find a route to a food source? Each ant follows the strongest pheromone (chemical) trail left by other ants. If this process is repeated frequently enough, they will find the best route through trial and error. If ants become isolated from their group, they end up running around in circles, following their own pheromone trail until they die of exhaustion. This behavior, called “swarm intelligence,” …

I would hate to be on the plane that gets separated from the others!

Wonderful OR Video, which bills itself as “the go-to place for management” has a wonderful video on operations research, with Vijay Mehrotra from San Francisco State University. Vijay writes the ever-fascinating “Was it Something I Said” column in OR/MS Today, and his site has all his past columns.

In the video, Vijay gives three reasons why OR is more important:  faster computers, niche marketing and outsourcing.  I like these themes (though I generally go with faster computers, more and better data, and better algorithms):  they are appealing to the business-school audience and are, I think, important reasons why OR is being used more.

Vijay has lots of things going on: I highly recommend wandering through his site. My only disappointment is that the “occasional weblog” on his front page is broken: he is someone worth reading!

Al Roth on Market Design

Al Roth is a professor at Harvard (formerly the University of Pittsburgh: I still go to his house regularly, though he isn’t there anymore) who has done a lot of work in market design. His big success was work in stable matchings, and its application to the matching system between hospitals and medical residents. This work had a strong OR component: the heart of the system is the algorithm for finding stable matchings (matchings in which there is no resident, hospital pair, both of which would prefer to match with each other rather than the ones they had been assigned). You can get lots of pointers from his game theory, experimental economics, and market design page. Al recently gave a talk at Yahoo! Research as part of their Big Thinkers series. In the talk, he contrasted markets in kidneys (which I talked about a few weeks ago) with the market to match NY high school kids to schools:

Kidney transplants are necessary for end-stage renal disease, but there is a shortage of kidneys. Lack of compatibility and laws against kidney sales open up the possibility of a market designed kidney exchanged to increase the number of transplants. Roth explained the need for national exchanges as opposed to regional exchanges to increase the thickness in the market; 3-way exchanges that will add to a population of incompatible donor pairs; and opening up kidney exchanges to compatible patient-donor pairs as well.

In the example of matching students to high schools in New York City and Boston, where thickness isn’t a problem, there were too many transactions that led to congestion in the market. As many as 30,000 students in New York City were assigned to schools not on their choice list. The newly designed system incorporated a centralized clearinghouse to which students would submit their true preferences, instead of unreachable choices. The algorithm ensured that more students got accepted to their realistic first preferences and minimized the number of those rejected into their second choice pools.

As a side note, these Yahoo! (and Google) videos are a great resource: they attract the very best researchers who all obviously work very hard on their presentations.