“For S/He’s a Jolly Good [INFORMS] Fellow!”

Further to INFORMS recognitions, now is the time to nominate people for INFORMS Fellow.  I was on the board when plans for the Fellow’s program got underway and I, like many, was a little leery.  Way back in the early 1950s, the Operations Research Society of America (ORSA) started a Fellow’s program that led almost immediately to the creation of  The Institute for Management Science (TIMS) by those who were not selected as Fellows (this is an oversimplification, and I wasn’t there:  how old do you think I am!).  I know of many organizations ripped apart by arguments over who gets to be a Fellow and who isn’t.  It is really awful when a Fellows program gets to be a schoolyard argument over who gets to sit in the treehouse.

On the other hand, practically the first question asked for nomination to the National Academy of Science (or Engineering) is “Is the candidate a Fellow of their professional society”.  Without this designation, operations research people are at a disadvantage.  So the Fellows program came in to being (Jim Bean, my predecessor as President of INFORMS, played a big role in designing and implementing the program).

I was fortunate to be President of INFORMS for the inaugural class in 2002, so I got to shake hands with Dantzig, Arrow, and a host of others.  It was a great thrill (forever memorialized in an OR/MS Today article where it looks like all the famous people are shaking hands with a cardboard cutout of me!).   And, while I know there are those who are not Fellows who should be (fewer and fewer every year), the society has seemed to survive this program.

The process for Fellows is now in the hands of the existing Fellows.  They (well, “We” since I became a Fellow a few years back) have put out a call for nominations:

The Fellow Award recognizes members who have made significant contributions to the advancement of operations research and the management sciences. The contributions of a nominee will be evaluated in each of the following five categories and contributions must be outstanding in at least one category: research, practice, management, education, and service. INFORMS will name its tenth set of Fellows at the INFORMS Annual Meeting 2012 in Phoenix, AZ, in October 2012. The nomination deadline is June 30, 2012.

Remember – a maximum of four reference letters, including the letter from the nominator, may be submitted.

[The complete nomination guidelines are at]:http://www.informs.org/Connect-with-People/Fellows/INFORMS-Fellows-Nomination-Procedure

The complete list of current Fellows is at http://www.informs.org/Connect-with-People/Fellows/Fellows-Alphabetical-List

Kimball Medal Call for Nominations

I’m chairing this year’s Kimball Medal Committee.  Here is the call for nominations:

The George E. Kimball Medal is awarded by INFORMS for recognition of distinguished service to the Institute and to the profession of operations research and the management sciences.   The committee for this year’s award is Michael Trick (Chair), Robin Keller, and Steve Robinson.  If you would like to nominate someone (including yourself) please send an email with the name of your nominee along with a brief justification to Michael Trick (trick@cmu.edu) by July 31 for review in August.  The website for the award is http://www.informs.org/Recognize-Excellence/INFORMS-Prizes-Awards/George-E.-Kimball-Medal and past awardees are listed at that site.
The past winners are generally an impressive group with recent winners including Brenda Dietrich, Steve Robinson, Larry Wein, Jim Bean, Mark Daskin, and yours truly (which is how I got to chair this year’s committee).

Sports with a vague Operations Research connection

It is pretty clear that academic administration and blogging are perfect substitutes, at least in regard to time, if not satisfaction.  After having an easy period earlier in the year when I racked up a dozen blog posts, administrative needs sucked up all my time, leading to the buildup of dust-bunnies at Ye Olde Blog.  But it is the end of term, so perhaps I can get things cleaned out.

Let me point out two recent sports-oriented items.  First is a fascinating dynamic map from Slate showing the winning of sports championships in the four major US sports (football, baseball, hockey, and basketball).  The progression is fascinating, and the graphical display gives far more information than the static listing does.  It is a great example of the value of visualization, even if I can’t quite figure out what the value is.  The graphic to the left shows a particularly good year:  1979 when Pittsburgh really was “The City of Champions”.

Second, there were two good articles on sports scheduling.  The first was on NFL scheduling in the New York Times.  Lots of people sent me this, since I’m part of the group that does Major League Baseball Scheduling.  The article does a great job of talking about all difficulties there are in agreeing on a schedule. Ironically, some of these difficulties come from the ease at which it is possible to get NFL schedules.  When it is possible to ask “What if we had Pittsburgh play New England in week 3?” and get back appropriate schedules quickly, it is tempting to ask a near-endless set of questions.  Particularly when there are many interested parties and no particular rules for aggregating preferences.

Baseball scheduling doesn’t provide the same quick response.  Due partially to the size of the schedule (2430 games or 780 series rather than the NFL’s 256 games) but due mainly to the scheduling difficulty of “good trips” (an issue of minimal importance to the NFL since teams return home after almost every game), the turn-around time on MLB schedules is measured in days or weeks, not minutes or hours.  Which brings me to the second article:  an article in the LA Times on baseball scheduling.  It even quotes my partner Doug Bureman:

Bureman, whose company also does the scheduling for several major-college conferences, summed up the job this way:

“We’re kind of in the business of seeking perfection, knowing that you’re never going to get there.”

That is for sure:  we are a long way from perfection!  But this year has been fascinating due to realignment issues:

All of this gets even more jumbled in 2013 when MLB realigns, with the Houston Astros moving to the American League and both leagues having 15 teams. (Currently there are 16 in the NL, 14 in the AL.) Interleague games will then be spread through the season instead of being bunched together around midseason as they are now.

Feeney and her group are currently working on that 2013 schedule, and have found it to be quite a challenge. “We’re still struggling with the format,” she said.

For a sports scheduler, this “struggle” is a once-in-a-lifetime opportunity, and it has been tremendously fun and interesting to work out how that format might work.

In between bouts of academic administration!

 

NSF Program Directors

I see from the INFORMS eNews that NSF is looking for new Program Directors for both Operations Research and Manufacturing Enterprise Systems/Service Enterprise Systems.  Needless to say, these are critical positions for the operations research community.  And, reading Robert Sloan’s article about his stint in computing theory at NSF, it sounds like a fun job!

Here is the announcement:

Russell Barton and Michael Fu, currently completing their terms at the National Science Foundation, would like you to consider serving at NSF in one of their roles – either as Program Director for the Operations Researchprogram or for the Manufacturing Enterprise Systems/Service Enterprise Systems (SES) programs. Their replacements will take office approximately in August/September. The process will remain open until the positions are filled. Serving at NSF, write Michael and Russell, is fascinating, challenging, and extremely rewarding. The OR/INFORMS community will benefit greatly by worthy candidates being selected for these positions. Download the announcement for SES andO.R..

Summer Time Travel Plans

As I sit in a jet-lagged haze in a Beijing hotel,thoughts naturally turn to …. more travel!  The opportunity to travel all around the world is a great bonus of academia.   And while I think I have taken this bonus to extremes (I am not sure academics should really be at the highest tiers of frequent fliers), it is nice to visit new places, see new sights, and meet new people.

In operations research, we have a tremendous number of conferences all around the world.  It is clear from things like the INFORMS Conference Calendar that a suitably enthusiastic, and financed, researcher could simply spend his or her life bopping around to conferences.  For me, this is limited by a couple of things:  first, I have an administrative role now, and if I am not around then …. well, I’m not sure what happens, but I feel I should be around.  Second, my family already asks for my business card when I return to remind them of who I am.  I do not want to make this even worse.

But I do have a few trips planned:

  • INFORMS Business Analytics and Operations Research (April 14-16).  A great conference, worth the higher-than-average cost.  I’m a judge at the Edelman’s again which has the plus side that I get to watch the Edelman presentations from a front-row seat, and I have read the papers beforehand.  On the downside, I don’t get to attend many of the other presentations.  I always come back with a class or two of material for my courses.
  • EURO 2012 (July 8-11).  I like the EURO conferences:  they are like INFORMS conferences, though somewhat smaller.  This year’s conference is in Vilnius, Lithuania, so I get to visit a new-to-me country.  Further, I am on the committee for the 2013 conference in Rome, so this conference is not really optional.  On the downside, getting to Vilnius is not the easiest!  I wish I had booked some flights when I first looked a month ago:  those flights are now full and the real power of revenue management is coming to bear on the other flights.  How much can airlines squeeze out of 2000 operations researchers?
  • MOPTA (July 30-August 1).  Held at Lehigh University, this conference has the advantage that I can drive to it (take that, revenue management maximizers!).  Held for a number of years at McMaster University in Canada, this conference has moved to Lehigh and brings together continuous, discrete, and stochastic optimizers in both theory and practice.  I’ll be talking about some of the optimization we use in sports scheduling.
  • Matheuristics (September 16-21) at a beach outside of Rio de Janeiro, Brazil.  It’s a beach, it’s Rio, it combines mathematical optimization with heuristics.  Need I say more?
I do have some other travel, including a quick hop to Australia to make sure people there are working hard pushing back the frontiers (I’m sure it is all optimization of kangaroo sustainability and the like, but we’ll see).

There are a lot more conferences that I would like to attend, both big and small.  INFORMS Beijing would be great to attend, but I was in Beijing in November and again right now (for academic administration reasons) so a third trip in 8 months would be too much.   PATAT (Practice and Theory of Automated Timetabling) is a series I like very much and is in Oslo, a city I like to visit, but it occurs this year at the start of term so I have to stay in Pittsburgh so that …. again, I’m not sure why I need to academically administrate at that time, but it appears I do.  CPAIOR (Constraint Programming, Artificial Intelligence, and Operations Research) is in Nantes, France this year (May 28 – June 1) but is not close enough in timing to the Vilnius EURO conference.  Similarly, it is hard not to attend the big International Symposium on Mathematical Programming Symposium in Berlin, but it too is too long after Vilnius and too close to the start of school.

And there are a few conferences in the fall that I am thinking about:  Constraint Programming is in Quebec City (a trés bon place to visit!) October 8-12.  Computational Social Choice is another interest of mine and will be held in Krakow, Poland September 11-13.    Chances are pretty good I’ll be at the main INFORMS Conference in Phoenix October 14-17   (hmmm… I wonder how the flights are from Quebec City to Phoenix):  I never miss the chance to get together with 4000 of my closest friends!

I think I’m going to need some optimization models to help choose conferences!

 

Car Talk and TSP Paths

On the suddenly hot topic of the Traveling Salesman Problem (see here and here), this week’s Car Talk puzzle is a TSP-like problem (though it is really a graph theory problem: the hamiltonian path problem to be exact).

The company that Bobo works for just finished a new product. They wanted to promote it across the country. Bobo was asked to travel by car to each of the 48 contiguous U.S. states to promote the product. He was told that he could visit each state in whatever order he chose, but the company wanted him to start in Delaware, at their headquarters.

They asked that he visit each state only once. He could not go back into a state he had already visited because this was the “Don’t Look Back” product tour. So, Bobo sat down at his desk and began to plan his trip.

He realized immediately that it was going to be one long car trip. At that moment, his boss stopped by and said, “Hey, I’m going to join you when you reach your last state. I was born there and I’ve been looking for a reason to go back and visit. You can leave your rental car there, and I’ll fly you back in my private jet.”

Since Bobo hadn’t planned his trip yet, how did his boss know which state was going to be Bobo’s last state? And, which state would that be?

That question is not hard (I won’t ruin it by giving the solution here:  call the state X);  the key is the statement about the flight back from the final state.

But it is strange that Delaware was given as the starting state.  Does it really matter?  Well, if you start in State X, you can end up in many (but not all) of the other states.  But it if you start in some other states, there is no path through all the other states without repeating a state.  I count seven starting states that preclude paths through all the other states by road without repeating a state.  Which can you find?  The following map is just for illustrative purposes:  the question refers to the “real” United States state structure (so you might need to check a more detailed map to see what states connect directly to others).

NOTE ADDED 1/17/2012.  Reddit’s lordlicorice has drawn the graph underlying the States:

 

Thanks to @wjcook for pointing out the Car Talk problem.

A Love Letter to the Traveling Salesman Problem

Bill Cook of Georgia Tech has a new book out on the Traveling Salesman Problem entitled “In Pursuit of the Traveling Salesman” from Princeton University Press (or from Amazon or B&N).  Unlike his previous book (with David Applegate, Bob Bixby and Vašek Chvátal), this book is aimed at a general audience. Bill takes his readers down a beautiful path covering the history, applications, and algorithms associated with the TSP. It is a fascinating story, and one that shows a researcher who truly loves his research area. You would think such a love was  common among researchers, but I have seen many researchers who seem bored by, or positively hate, their research areas. Bill is obviously enraptured by the TSP.

The Traveling Salesman Problem is remarkable easy to state:  given a set of points with distances between them, find the shortest tour through all the points.  For example, as Bill wrote about recently, given 99 towns in Iowa to visit and the road distances between every pair, what is the quickest way to see all the cities, returning to your starting position?

Despite its simple statement, the problem of finding good or optimal tours has generated thousands of research papers.  The TSP is the standard testbed for discrete optimization:  practically every possible approach to optimization can be tried out on the TSP.  So research on the TSP has had a tremendous effect on approaches for all sorts of other optimization problems.  Bill covers every aspect of this research corpus.

Perhaps the most interesting part about this book is that Bill pulls no punches when it comes to presenting work. Most of us would be tempted to go only so deep into an area and then start hand-waving believing “well, no one would understand this area anyway”. Here is how Bill begins a description of finding comb inequalities, a type of constraint necessary to determine the TSP polytope:

Subtour-elimination constraints? No problem. Comb inequalities? Not so good.
At the moment there is no known polynomial-time algorithm that is guaranteed to
spot a violated comb inequality if one exists. The comb-separation problem is also
not known to be in the NP-complete complexity class, so its status is wide open.
A great need coupled with inconclusive results translates into an important research
problem.

This is not to say that combs are currently skipped over in computations. By
hook or by crook computer codes must generate combs to push LP bounds after
subtour-elimination constraints fail. This is accomplished by hit-or-miss strategies
for growing handles, shrinking teeth, splicing sets, and a host of other operations.

If I tried to write this book, I don’t think I would have even got to comb inequalities, let alone continued to the nice description Bill provides of comb-finding heuristics.  This level of discussion requires some concentration when reading but the book is accessible to a wide audience.  This is an ideal book to get a college student or a smart high school student interested in operations research and combinatorial optimization.

This is a highly personal look at the TSP. Bill tells you his favorite heuristic (farthest insertion), his favorite exotic computing model (time traveling solver: take as long as you like to solve but then go back in time to report the solution), and much more.

Chapters have interesting lead quotes (the book begins with Listen, mate, I’ve traveled every road in this here land. from Geoff Mack in the song “I’ve Been Everywhere”), and the illustrations throughout are fantastic.  I also love the way that Bill includes pictures of practically everyone who has done research in this area. Putting faces to the names is a wonderful way to personalize the research.

Through this book, you’ll learn all about the Traveling Salesman Problem and, more broadly, about the different research directions in combinatorial optimization. And you’ll also see why top-notch researchers like Bill Cook find the TSP endlessly fascinating. And you might just want to be a researcher like Bill.

I guess a bit of a disclaimer is needed here: Bill has included a very nice mention of this blog in the book (thanks Bill!) with a picture of me,  and his publisher sent me an advance copy of the book. I failed miserably in getting a nice quote in on time, but that is due to my own failings. I really love the book!

 

Death to Data Hogs! Ooops, that’s us!

The New York Times has an article on the concentration of use of mobile airwaves.  It seems that 1% of the users consume half the bandwidth:

The world’s congested mobile airwaves are being divided in a lopsided manner, with 1 percent of consumers generating half of all traffic. The top 10 percent of users, meanwhile, are consuming 90 percent of wireless bandwidth.

Arieso, a company in Newbury, England, that advises mobile operators in Europe, the United States and Africa, documented the statistical gap when it tracked 1.1 million customers of a European mobile operator during a 24-hour period in November.

Wow!  That is amazing!  Those greedy bandwidth hogs!  If it wasn’t for that 1%, usage would go down 50%. Get rid of 10% and usage goes down 90%!  Time to Occupy the Download Link!  Right?

Wrong.  As my former student Ben Peterson pointed out, measuring usage over a day doesn’t give much of an idea of the daily variability of usage.  For instance, three days ago I had some time to kill, so I downloaded a video and a few games.  I then updated all of my apps, and cleaned up my photo collection by sending some pictures to my web photo storage.   I was a complete bandwidth hog!  Since then, I haven’t used my phone much at all.  So, three days ago, I was part of the 1%;  since then I haven’t been.  Which day did you measure me?

So yes, on a given day, 1% of the people use half the bandwidth.  But, unlike financial wealth, we get to change around (every day!) who that 1% are.

If you want to use analytics, you really have to think about what your statistics mean and how you can generalize it.    The New York Times (again!), like much of journalism, rarely seems to take the next step and actually think about the numbers.

16 Clue Sudokus

I am sure everyone has seen Sudoku puzzles:  it was quite a fad a few years ago.  The puzzle begins with an 9×9 grid, partially filled with numbers from 1 to 9 (the “givens”).  The goal is to complete the grid so that that every row, column, and the nine 3×3 subgrids in the corners and center all contain the numbers 1 through 9 with no missing and none repeated.  There was a time in my life where I loved Sudoku puzzles.  I had to give them up when I started to dream solely in Sudoku.

The puzzles can be difficult or easy depending on straightforward it is to deduce missing values.  A grid with many  givens tends to be very easy, since there are few choices for missing values (though there can be hard problems with many givens and easy ones with few).  If too few values are filled in, however, the solution may not be unique, and it is a fundamental precept of puzzle-creators that the solution must be unique.  So, how many givens are needed to ensure uniqueness? It has been known for a long time that there exist problems with 17 givens that lead to unique solutions.

Gary McGuire, Bastian Tugemann, Gilles Civario of University College Dublin proved this result is the best possible:  there is no problem with 16 givens with a unique solution.  They do this in a very interesting way:  they did an exhaustive search.  Given the number of possible solutions, it is surprising that exhaustive search works, but they were clever in organizing the search, and had access to a ridiculous amount of computational power.  This combination let them run through all the choices.  They didn’t find a 16, therefore there is not a sixteen!

Fascinating work, and a sign of how fast computing can change how we look at research problems.  Technology Review has an article on this;  the technical report is at arXiv.

Super Exciting News on Super Polynomiality of LP Formulations of the TSP Polytope

Years ago, I spent a very pleasant couple of weeks in a group debunking a claimed linear programming formulation of the Traveling Salesman Problem.  I wrote on this before, and bewailed the fact that I was not smart enough to figure out there was a general theorem there:  Yannakakis showed that no symmetric linear programming formulation of polynomial size can formulate the TSP.  The “symmetric” part of the theorem was always bothersome since it seemed an unnecessary addition.  You can make a symmetric formulation “unsymmetric” by doing something goofy in adding a useless variable or similar, but the fundamental result still holds.   Can asymmetry work on a fundamental level? I worked on trying to remove the symmetric assumption, but had no success.  That’s not surprising since Yannakakis clearly would have not included the requirement if it was easy to remove.  Yannakakis is smarter than Trick.  Therefore Trick cannot remove the requirement.  Q.E.D.  But I still tried for a while.

Fortunately, research moves on, and people learn more and more, and finally enough gets proved that smart people can figure out how to move forward.   It appears that the symmetric requirement can be removed.  Sebastian Pokutta, and his coauthors Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronal de Wolf have a paper that proves that any linear programming formulation (symmetric or not) of the TSP is exponentially sized super polynomial.  Sebastian’s blog post has a very nice description of some recent history (including the astonishing result that sometimes the symmetry requirement does matter) and gives pointers to both the paper and to some slides.  I have not had time to go through things thoroughly (or at all, really) but the paper seems a trove of interesting results.  I feel like starting a Ph.D. seminar next week to study it!

Between Bill Cook’s soon-to-be-released TSP book and this news, 2012 is shaping up to the be the year of the Traveling Salesman Problem!