NL8 Solved!

Almost 10 years ago, Kelly Easton, George  Nemhauser and I created something called the Traveling Tournament Problem.  The name is George’s:  I wanted to call it the Problem where Teams Play a Round Robin and Travel and Stuff, but George’s name is catchier.  The problem came from work we had done with Major League Baseball in creating their schedule.  Rather than try to post 150 pages of requests and requirements (which MLB would never let us do anyway), we abstracted out the key aspects of the schedule.  Those were:

  1. Travel:  a wish to keep the total travel down, and
  2. Flow: a wish not to be home or away for more than 3 series consecutively.

I also added a “no repeat” constraint:  if A is at B, then B cannot be at A in the next time slot.

When we put this together, we also put together the website http://mat.tepper.cmu.edu/TOURN to keep track of results and that turned out to be a great idea.  By having one site with results and instances, it has been easy to keep track of “current records”.

When I first worked on this, my goal was to show how some of our methods that we use for MLB could handle problems of reasonable size for the Traveling Tournament Problem.  That turned out to be impossible to do.  The Traveling Tournament Problem is hard!  Even solving the eight team problem turned out to be nontrivial.  Six teams is doable with a bit of work.

Kelly Easton, in her dissertation, put a lot of effort into the TTP, and even solved the eight team problem.  She used a network of 20 computers over the course of a week to prove optimality.  Unfortunately, she did not include the “no repeat” constraint, so we didn’t have the result for exactly the right problem.  While we believed that adding the “no repeat” constraint wouldn’t affect things too much, Kelly graduated, began working (for my small sports scheduling business) and we never solved the real problem.

Despite lots and lots of people working on the TTP, proving the optimality of a known solution to NL8 with value 39721 has been elusive.  In fact, relatively little (but some, thanks to Melo, Ribeiro, and Urrutia) work has been done on improving lower bounds.

I was thrilled yesterday to get an email Stefan Irnich of Aachen who, together with his master student Ulrich Schrempp, claims to have proved the optimality of 39721.  But here is when it gets hard.  How do I know?  It is easy to check feasible solutions, but unless there is a simply calculated lower bound, it it hard to confirm optimality.   Fortunately Stefan sent the slides of his work, and it seems clear that the approach they are taking is one that would work, and would be stronger than what others have tried.  So I have no hesitation in proclaiming that NL8 is now solved!  I am sure there are easily dozens (OK, half-dozens … OK, a half-dozen) people who are excited about this, and I am one of them (and it is my blog).

On to NL10!

Data Visualization

I have always loved Data Visualization (well, always since my adviser John Bartholdi pointed me to Tufte’s classic “Visual Display of Quantitative Information”). I teach data mining here to our MBAs, and have wanted to include the topic, but never knew what to include. Thanks to Stephen Baker of Business Week and his pointer to Many Eyes, I think I am getting an idea. Many Eyes is an IBM site with a goal of making data visualization algorithms and data sets widely available. It is a fantastic place to spend a few hours. As an example of what you can do on the site, here is a tag cloud of my vita (the source is at http://mat.tepper.cmu.edu/trick/vita.pdf):


I think you can find a fair amount about me just by looking at that tag cloud, though I am a bit biased (most ink blots end up looking like me in my eyes). Perhaps even more than by reading through a 12 page vita (by the way, vita (or curriculum vitae) is supposed to meana short account of one’s career and qualifications prepared typically by an applicant for a position”. What ever happened to short? What is the name for the document where you put down every blessed thing you ever did in your academic career?)

The structure of Many Eyes is unusual: you don’t download computer software. Instead, you upload your data (which immediately becomes public, so don’t try this with your financial records) and work with it there. This means that Many Eyes is quickly collecting a huge amount of data (23,256 data sets so far) that it (and you and others) can work with. This “social networking” aspect is unexpected, but I would bet that some interesting results come from it.

Another fascinating site is Wordle, which also creates tag clouds, but does so in a more artistic way. Here is my vita in that form (a couple of versions). I think I will use it during my next salary review!


I think I will need a few more days to recover from my surgery before I can get any useful work done.

IFORS 50th

IFORS 50th logo

The International Federation of Operational Research Societies (IFORS) is holding a conference in a few weeks in South Africa. Part of the festivities is a celebration of the 50th anniversary of the organization. I am putting together a presentation on the history of IFORS and would very much welcome anything anyone has that might be relevant (including pictures from conferences, pictures of Presidents (pre-1995 or so: I think I can find Tom Magnanti on the web!) and so on. Let me (trick@cmu.edu) know if you have something! Please, please, please!

There is a wonderful indexed photo of the first international conference (Oxford 1957) available. It is too bad that conferences have grown so big that such pictures are now hardly ever taken. It is fascinating to see some of the “big names” in our field as young men, and sometimes women. Can you pick out Dantzig without checking the index? Hint: he is in the front row.

One striking aspect of the history is the variety of backgrounds of the early Presidents of IFORS. Sir Charles Goodeve was the first president of IFORS (I have a family connection with Sir Charles). He had done tremendous work in OR during World War II. The next President, Philip Morse, also did significant work during the war and went on to found the Bookhaven National Laboratory, among other institutes. The third president, Marcel Boiteux, led French Electricity and was a leading proponent of nuclear energy for that country. After Charles Salzmann finished Boiteux’ term (I know little about Salzmann), Alec Lee, a manager at Rolls-Royce became President. That is two physicists, an economist, and an automobile executive as the first presidents! Many more recent presidents (Pierskalla, Bell, Weintraub, Toth, Magnanti) are mainstream academics, though the current president (Elise del Rosario) made her mark with the San Miguel corporation, a food, beverage, and packaging company in the Philippines and South East Asia.

It has been interesting to look into the history of IFORS. For a number of reasons (primarily because its members are societies, not individuals), it is less well known than groups like INFORMS, but I am glad to be part of it. More about IFORS in the coming weeks leading up to South Africa.

First computer, now me on the mend

Now that I have the “new” computer working, I have to spend a couple of days on the mend myself:  I had surgery for a hernia on Wednesday.  My plan was to to a “live blog” on the efficiency of hospital operating procedures.  I guess I can tell you that general anesthesia works pretty well, since I have absolutely no memory between “Just slide onto the table here” and “How are you feeling?  Ready to go?”.  So give me a couple of days then I will be ready to take on the OR world again, with upcoming conferences in South Africa and New York.

Arnoff Lecture

I am just back from Cincinnati, where I gave the 17th E. Leonard Arnoff Memorial Lecture on the Practice of Management Science. When I look at the list of presenters, with my name on it, I am reminded of the Sesame Street tune “One of These Things (Is Not Like the Others)“. I was honored to be asked, and very happy to give the talk. There were about 85 in the audience, despite armaggeddon-like lightning and thunder outside.

The lecture is named after Len Arnoff, best known for his 1957 book “Introduction to Operations Research” with Churchman and Ackoff, one of the first (or the first) operations research textbook. He had a varied career: faculty member at Case and others, partner at Ernst and Ernst, and Dean of the Business School at the University of Cincinnati, before retiring to Florida in 1988. He died in 1991. (David Rogers is preparing a short biography of Arnoff, and I am grateful for the early version he sent me).

I was very pleased that his wife Ann flew up to attend the lecture, and that his daughter Susan could also attend.

The title of my talk was “Sports Scheduling and the Practice of Operations Research”. In addition to telling some stories about working with various sports leagues (you will have to attend one of my talks to hear those!), I spend some time on some of the technical issues. The main theme was that if you only knew operations research from ten years ago, you probably don’t have the techniques needed to solve real-world sport scheduling problems. In particular, the following methods don’t work very well:

  1. “Routine” integer programming: let x[i,j,t] = 1 if i plays at j in time t, etc. etc. Weak formulation that does very poorly
  2. Greedy heuristics. Generally do not lead to anything close to feasible.
  3. Local search. Simple exchange generally leads to infeasible solutions, making it hard to use simulated annealing, tabu search or other metaheuristic approaches.

The following do make a big difference (and are much more recent ideas):

  1. Complicated variables (like in branch and price): Let a variable represent a road trip, a schedule section, or a whole schedule for a team.
  2. Large neighborhood search. Relax large pieces of a schedule and reoptimize keeping the rest fixed.
  3. Constraint programming, ideally combined with integer programming, in order to quickly find feasible solutions.

Closing of the Florida International University Industrial and Systems Engineering Department

Florida International University is planning to shut down 17 degree programs, including industrial and systems engineering. I have good feelings for FIU, since my first doctoral graduate took a position there (in the business school; he has long since moved on), but it is shocking that a popular and important degree such as IE would not be offered. Here is the situation according the Miami Herald:

Florida International University has proposed eliminating 17 undergraduate and graduate degree programs, including some related to teaching, nursing and engineering, and laying off scores of employees in an effort to cope with deep budget cutbacks from the state Legislature.

Staff and faculty in the industrial engineering department say the decision to cut their program came as a shock, and was made without consulting them. Industrial engineering is a popular area of study, with 300 students currently enrolled in undergraduate or graduate level programs. Currently enrolled students would be able to finish their degrees over the next three years, after which the faculty and staff would be laid off, said Martha Centeno, associate professor in industrial engineering.

The INFORMS student chapter of FIU has been very active and has sent a plea for help and support:

We are currently pursuing a degree in Industrial & Systems Engineering (ISE) at FIU. FIU with no reasonable justification has proposed to permanently close our department. This decision will impact the current students, alumni, South Florida community and industry.

As students, we will be working on a degree which will not have the same value as it has today, having a degree from a department which does not exist is not the same as having a degree from a department which is stable and strong as it currently is.

This is the situation of over 300 students. We would like to encourage you to sign the petition that we, as students, are preparing for the Governor. The petition can be signed at the following link
http://www.petitiononline.com/ISE52108/

We need your help more than ever to reach our goal to stop the closure of our department. It would be highly appreciated if you could send letter to the FIU’s president stating how important and valuable Industrial Engineering is, and foward this email to all Informs members. We are counting with your support to keep open a department that is strong, healthy and needed for the community. More information can be found at the following web site
http://web.mac.com/save_ise/ISE_PLAN_X/Welcome.html
Thank you so much for your valuable time, understanding and support.
Sincerely yours,
Industrial and Systems Engineering Student Body

INFORMS FIU Chapter