George Nemhauser and Laurence Wolsey win von Neumann Theory Prize

A twitter report has George Nemhauser of Georgia Tech winning the von Neumann Theory Prize from INFORMS.

 

Turns out that you can confirm this at the online conference program:  George Nemhauser and Laurence Wolsey are this year’s von Neumann Prize winners.  This is great news!  George and Laurence are two of my favorite people in the field.  I know George better than Laurence, since he and I are partners in our small sports scheduling company, so I work with him pretty closely.  And I did take a few courses from him when I was a doctoral student at George Tech a century or two ago.   I have interacted often with Wolsey at conferences, and he was kind enough to host me in Louvain years ago. The book George and Laurence wrote is a classic of integer programming and I am actually stunned they did not receive this award years ago.

But this is my blog, not George or Laurence’s, so let me say two things about me in this context:

  1. George and I have a paper that we wrote back in the late 1990s on scheduling Atlantic Coast Conference basketball.  It is dated now, of course (you can solve this problem in seconds rather than hours), but it remains one of my favorite papers, and I think it was pretty influential in kindling interest in sports scheduling optimization.  I wrote it over a 3 day period while snowed in during a year I spent at MIT.  The published version is almost identical to what I wrote in those three days.  I see it is one of George’s top 15 cited papers, but that probably is not the reason he got the von Neumann.  Note that George’s most cited work is his textbook with Wolsey:  Google Scholar is a bit confused about this.
  2. Last year’s winner of the von Neumann was Gerard Cornuejols, who is my colleague at the Tepper School.  Looks like “closeness to Michael Trick” is a key criterion for the von Neumann, though actually being Michael Trick is too close to get the bonus points.

Assuming the rumor is true, Congratulations George and Laurence!

 

Fischetti Speeds Up Optimization with Randomness

I just got back from a very nice workshop on “Matheuristics” held outside of Rio de Janeiro, Brazil.  Matheuristics is the combination of optimization and heuristics.  For instance, I talked about large scale local search for sports scheduling problems (among other things).  In this approach, portions of a sports schedule are fixed, and you optimize over the rest using integer programming.  This has aspects of both metaheuristics (large scale local search) and optimization (integer programming).

I greatly enjoyed the workshop and thank Celso Ribeiro for organizing it and inviting me.  It was a small workshop, with perhaps 40 participants, with a single track of papers.  For the first time in years I attended every talk at a conference!  Try doing that at INFORMS!

My favorite talk was given by Matteo Fischetti of the University of Padova.  The talk, entitled “Erraticism in tree search” was a real eye opener in terms of my understanding of how branch-and-bound on integer programs performs in practice.  I’m going to paraphrase some of the key points of the talk.  None of the numbers in the following are exactly what Matteo presented, but this is close enough to get the idea across.

Here’s the setup:  Matteo claims to have a new cut for general mixed integer programs.  It is parameterized, so he can actually create 10 different versions of that cut.  He downloaded the MIPLIB 2010 benchmarks and some other benchmarks he found, ran default CPLEX on them, and limited his test to hard, but not insolvable instances (tossing out all instances solved by default CPLEX in under 100 seconds or requiring more than 1000 seconds).  This left a test bed of 38 instances.

When Matteo solved the testbed using each of the ten cuts (separately), he found something amazing:  a single cut often greatly decreased computation time.  The (geometric) average decreases over the testbed relative to default CPLEX for the ten different parameterizations were:

Parametrization 1 2 3 4 5 6 7 8 9 10
Decrease 12% 14% 25% 4% -0.50% 32% 15% 12% 6% 33%

Wow!  These cuts are great!  Cut 5 had a bit of an increase in time, but it turned out that cut was kind of a dummy.  Cut 5 took a random permutation of the non-negative integer variables and added a constraint Σ xi ≥ -1. This constraint clearly doesn’t do anything: CPLEX throws it away during preprocessing.

But look at Cut 10.  It decreased computation time by 33%.  It is amazing!  Cut 10 took a random permutation of the non-negative integer variables and added a constraint Σ xi ≥ -1. And that seems to work really well!

Hold on…. What’s going on here?  In fact, each of the cuts is simply a random permutation of the variables and a redundant constraint.  How can that have any effect?

CPLEX (as with Gurobi or any other solver) has a certain “randomness” in its operation.  This is not random in the sense that the final answers are not optimal, but rather the exact operation of the algorithm may depend on things like the ordering of the variables. So, for instance, if a solution to a linear program has multiple optimal solutions, the exact solution reported can depend on which variable is first in the internal ordering of variables.  And, of course, the exact solution reported can then affect the branch and bound tree (since different variables might have fractional values).

If you change the internal ordering of the variables, you can change the operation of the branch and bound algorithm.  Adding the redundant cut changed the internal ordering of the variables, so the timing results could vary.   Not every instance has this aspect.  Some have relatively consistent computation time independent of the ordering.  But some instances vary a lot based on the ordering.

This is insight 1:  branch and bound timings may vary a lot due just to the random choices of the algorithm.

If your computation time is too long, try permuting the variables.  If you see lots of variation in computing time, perhaps it it is worth running multiple instances in parallel with different variable orderings (or internal random number seeds) in the hopes that one instance will solve much faster than the others.

This makes me wonder how many past papers showing that an approach is useful are simply showing different (good) random draws from the search tree?  And how many good ideas have been discarded due to “bad luck” from the random number generator?

But this still leaves a puzzle:  almost every random ordering is better than default CPLEX.   Does this mean that you should at least randomly generate an variable ordering?  One gentleman at the conference, vibrating with excitement, thought he had the justification for this:

Since most of these instances come from real problems, perhaps there is something about the way people formulate problems that leads to problems with the solution code. As I code, I would normally generate all of one type of variable (say, the “x” variables), then the “y” variables, then the “z” variables.  This must be messing up CPLEX.  What a great insight!

That hyperventilating gentleman was me.  And Matteo quickly and firmly showed that I was wrong.  How could almost all of the orderings do better than default CPLEX?  Look back, the hint is there…..

 

 

 

How did we get our instances?  Let me quote myself:

He downloaded the MIP2010 benchmarks and some other benchmarks he found, ran default CPLEX on them, and limited his test to hard, but not insolvable instances (tossing out all instances solved by default CPLEX in under 100 seconds or requiring more than 1000 seconds).

In doing this, he biased the sample!  Anything default CPLEX did well on (under 100 seconds), we threw out!  So the sample was made up of things that default CPLEX did not do well on.  It is no wonder that “Cut 1” had an advantage.  If we had run all the instances on “Cut 1” and threw out anything it did well on, it would turn out the default CPLEX would do better than “Cut 1”.  If you toss out instances that an algorithm works well on, don’t be surprised if it does poorly on the rest.

So this is insight 2:  if you want to compare algorithms A and B, make sure the definition of the testbed does not depend on which gets label A and which gets label B.

I can’t tell you the number of times I have read computational papers that make the bias mistake.  And I rarely noticed it.  I will now!

Of course, Matteo doesn’t make mistakes like this in his work:  this presentation was an extremely effective way of showing how easy it is to make this error.

I cannot do full justice to Matteo’s talk:  there were many more insights and surprises.  The associated paper (with Michele Monaci) is here.  And if you get a chance to see him give the talk, do so!

After that talk, I will never look at computation in integer programming the same way again.  That presentation alone was worth the flight to Brazil!

Added 9/26:  Matteo has kindly provided his slides, which are available here.

 

Come work at Carnegie Mellon!

I teach (and, now, administrate) in the Tepper School of Business at Carnegie Mellon University.  Unlike most engineering-oriented universities, CMU does not have an Industrial (or Systems) Engineering department, so operations research people are scattered throughout the university.  The Tepper contingent is a big one (senior faculty include Balas, Cornuejols, and Hooker) and is augmented by others in the school with operations research interests (people like Sridhar Tayur who is in our operations management group).  But there are lots of OR people elsewhere, including Chemical Engineering (Ignacio Grossman, for instance), Mathematics (Alan Frieze), and Computer Science (Tuomas Sandholm).

The Heinz College of Public Policy and Information Systems has a large contingent of operations researchers, including Al Blumstein, one of the founding researchers in our field.  And the Heinz College is hiring in our area!  Here is the announcement:

Carnegie Mellon University’s Heinz College  is currently expanding its program targeted at analysis, design, and eventual implementation of Urban Systems and is seeking to recruit tenure-track faculty to be key participants in those developments. Heinz College (www.heinz.cmu.edu) consists of a School of Public Policy and Management and a School of Information Systems and Management.

We are seeking individuals from a diversity of related disciplines, including economics, transportation, operations research and the management sciences, statistics, and systems engineering with specific attention to civil engineering.

Our interests in Urban Systems include transportation systems, public-safety systems, and the built environment. While these problem domains are diverse, to be addressed effectively an interdisciplinary perspective is required. We are thus seeking candidates who are open to collaborating with researchers from other disciplines. We have developed relationships with a number of cities, including Pittsburgh and New York, as sources of data, experimental opportunities for improved system designs, and expertise in the realm of problems associated with their operating systems.

All candidates should have a PhD (or should demonstrate that one will be achieved shortly) in relation to one of the identified disciplines and have demonstrated research competence. Interested applicants are asked to send their application to the Urban Systems Search Committee at urban-sys-heinz-college@andrew.cmu.edu. An application should include a cover letter indicating their particular interests and their sense of fit with the Heinz College, a CV, copies of any published papers, and three sources of reference letters.

We will be conducting interviews at the October INFORMS meeting in Phoenix. For consideration at these meetings, applications should be submitted at least one month in advance.

If this sounds like you, please consider applying.  I look forward to having even more operations research on this campus!

The Treasure has been Found!

I wrote previously about an “Analytics Treasure Hunt” organized by John Toczek.  I have just heard from John that the treasure has been found:

Just wanted to give you an update on the 2012 Analytics Treasure Hunt.  The treasure was found by two member team, Madineh Sarvestani and Shepard Wallace who successfully retrieved the treasure on Saturday, 8/18/2012 at about 10am EST.  The correct coordinates were 40.07284, -75.21907.  I’ve posted their pictures on www.puzzlor.com with a short note indicating that it has been found and that the contest is over for this year.

Here are the photos of the winning pair (Shepard looks quite pleased with the cash!):

Owning the Podium: Summer 2012 edition

During the last winter Olympics, I had what I thought was a pretty good idea.  There are many ways to rank countries during the Olympics:  you can rank them by total number of medals, or you can rank them by number of gold medals, or by some point scheme (5 for gold, 3 for silver, 1 for bronze) and so on.  Point schemes seem to make sense, but then people argue about points.  Is a gold worth 5 bronzes or 4? Is 2 silvers more than, less than, or the same as a gold?

So my idea was to rank countries by the fraction of reasonable weights that result in them having the highest point count.  Not every point scheme is reasonable:  only a bronze lover (pyropusaphile?) would score bronze higher than gold.  So we need gold >= silver >= bronze.  And it seems unreasonable to have a negative weight on a medal.  Finally, the weights can be scaled so that the total weight is one.

In the Winter 2010 Olympics, Canada was edged out by the United States in the Trick Medal Championship (TMC) by a narrow margin.  Canada had 14 gold, 7 silver, and 5 bronze;  the US went 9, 15, 13.  If you put enough weight on gold, then Canada wins.  But only 45.25% of the reasonable weights put enough weight on Gold for Canada to win;  the US wins for the remaining 54.75% of the weights.

The summer Olympics are now over, with the final medal count being:

US: 46,29,29

China: 38,27,22

Russia: 24,25,33

Great Britain: 29, 17,19

with no other country winning at least 20 medals of a single type.

So the coveted TMC Award goes to …. the United States in a rout!  In fact, the US wins for every reasonable weighting.  Russia could win with a lot of weight on bronze medals, but not if the weight on gold and silver is at least that of bronze.

A necessary and sufficient condition to win for any reasonable weight is to have

  1. more gold than anyone else,
  2. more gold+silver than anyone else, and
  3. more gold+silver+bronze than anyone else.

Equality in any of these can lead to weights where the country ties for the win.

Here, the US meets that condition.  Of course, it helps that there are a zillion medals in swimming (where the US does well) and only one in, say, team handball (described here as water polo without the water, which is only marginally informative).  But a win is a win:  if any representative of the US Olympic teams would like to drop by my office, I will be glad to give them the TMC trophy (which I will be recycling from my stash of high-school curling trophies I have dragged around the world).

P.S. The Wall Street Journal Numbers Guy has a similar discussion though, sadly, it does not include the above approach.

I may be depressed but I could win some money through operations research

I got an email recently from John Toczek, an OR professional with Aramark who writes the PuzzlOR column for OR/MS Today):

You ran an article on a contest I created back in 2010 called the Analytics X Competition [http://mat.tepper.cmu.edu/blog/?p=1024] where contestants were trying to predict where homicides would occur in Philadelphia zip codes.  That contest ended some time ago but I am working on two new projects that I thought might interest you.

The first is a medical diagnostic site (www.whatsmydiagnosis.com) that uses the correlations between symptoms and diseases to predict diagnoses.  The site ranks the likelihood of all diseases in descending order based on the symptoms you select.  It’s in the proof of concept phase right now but I wanted to get the word out in order to get some feedback from the community so I can improve it.

The second is an analytics treasure hunt that is due to run in Analytics magazine on July 9th.  (www.puzzlor.com then click on “The 2012 Analytics Treasure Hunt” link.)  It’s basically a series of 5 puzzles that when completed form a latitude and longitude where I have hidden $100.  If you’ve ever heard of GeoCaching, it is similar to this.  My hope with this project was to get the word out about O.R. and hopefully attract new people to the field.

I checked out the medical diagnosis site.  After putting in my sex (Male), height (5’10” and above) and weight (over 180 lb:  seriously?  in a land of morbese obesity, over 180 is the maximum grouping?) and found …. a 42.5% likelihood of depression.  That’s a bit of a downer.  In fact, I’m feeling kinda depressed about the whole thing.  Hey! It works!

I wouldn’t take the site too seriously (as the About page there says: should not be used as professional medical advice) but perhaps as more data gets entered, the predictions will get better.

As for the treasure hunt, I am looking forward to the challenges (available July 9).  I hope the hunt is difficult, though.  I am currently in Vilnius, Lithuania and will be for most of the week.  Either I luck out and John has decided that Lithuania is the ideal place to hide his $100 or it will take a while for me to get to where the money is hidden.  That’s assuming I can solve his challenges, of course.

 

Become an Operations Research Editor!

While the popular conception of a university professor is someone who stares at arcane notation on a whiteboard until interrupted by the need to teach pesky undergraduates, there are many more activities that are part of the professorial portfolio.  We drink coffee with colleagues, gossip about departmental politics, attend conferences in far-flung locales, referee papers, train doctoral students, write blog entries, tweet, volunteer for professional societies, and much more.  There are a ton of things that can go into a professional life.

One key professional role is that of editor of a professional journal.  Editing a journal is not a job to take on lightly.  It requires a 3-5 year commitment and that commitment is contuous.  Except for editing the “big journals” like Management Science or Operations Research, an editorship is not terrifically time consuming, requiring just a few hours per week.  But it requires those hours each and every week:  nothing will kill a journal quicker than an on-and-off editor who only responds when crises have grown so large as to not be ignored.

In return for that time, the editor can have a unique and personal effect on a journal.  The editor’s judgement will determine the quality of the journal, and the editor’s energy will define the scope and creativity in the journal.

There are two journals that are looking for editors for which this scope and creativity issue is particularly important:

  1. INFORMS Journal on Education.  ITE is an online-only journal of INFORMS with a goal of advancing education in OR/MS.  The journal has published pieces on educational theory, case studies, surveys, curricula, and much more.  I have found the journal to be very useful as I prepare my classes, and I have published in it.  This would be a great post for a creative researcher with a passion for educational issues.  Nominations are due June 30, 2012
  2. Surveys in Operations Research and Management Science.  I am even closer to this journal, since I am one of the thee (along with Jan Karel Lenstra and Bert Zwart) co-editors.  This journal was designed as the followup to the well-regarded Handbooks in ORMS that Jan Karel Lenstra and George Nemhauser handled for a decade or so.  The idea was to publish high quality surveys (like in Handbooks) without the lead time required by the Handbooks.  Like many new journals, it has been a real task to get off the ground, but we will have published three years worth of journals at the changeover.  This journal needs a highly-energetic, well-connected editor who can give it near undivided attention over the next few years to put the journal on solid footing.  It is an Elsevier journal which gives it some disadvantages (some choose not to work with commercial publishers) and advantages (editorial support is very, very good).  I’ve greatly enjoyed working with Jan Karel and Bert and the rest of the team on this, but it needs an individual or group which is less scattered in their interests than I am at this point.  Applications are due July 31, 2012.

Taking on a journal is a big responsibility, but it can be very rewarding. Short of doing Lanchester Prize level work, it is one of the best opportunities you have to have a real effect on the field.

All Hail the Mighty Rose (and Mary and David and the rest of the gang at INFORMS)

A bit over a year ago, INFORMS took over sponsorship of OR-Exchange, a question and answer site for operations research and analytics.  And when I say “sponsorship”, I mean they agreed to host the site and provide all the infrastructure for the system.  It was a generous offer to a community that had been struggling to find a reliable home.

Since then, OR-Exchange has, in some ways, thrived.  There are more than 600 questions, more than two thousand answers, and scores of participants.  Almost every question gets some sort of answer, and often three or four useful responses.  The site has avoided (much) spam through the diligence of the administrators (users who receive enough karma through their engagement with the site).

But it has not all be “rosy” (a bad pun, for reasons you will see!).  The system response has been, charitably, atrocious, with countless errors, time-outs, and just plain slow days.  The INFORMS people tried, but nothing seemed to help much and the open-source community that created the underlying software (OSQA) couldn’t help enough to get things working well.

So those of us who believed in OR-Exchange put up with the slowness because the system was useful.  And fun.  But we did hope for a day when the system worked better, hoping that would encourage more to join us.

This week, that day has come.  Through the work of new INFORMS IT head-honcho Rose Futchko along with INFORMS people such as David Wirth, Mary Leszczynski, and (in earlier efforts) Herman Strom and undoubtedly others (let me know so I can add to the Hall of Heros), the problems seem to have been fixed.  The system is noticeably faster and more stable.  For proof, I offer the following giving the load times of the front page of OR-Exchange every hour for the past seven days (lower is better: every horizontal line marks 10 seconds).  See if you can figure out when the new system went in.

Of course, it might go all pear-shaped (in a wonderful expression I learned in New Zealand) over the next days, but things are looking awfully good (“Don’t jinx it Trick, ye eejit you!”).

If you haven’t yet discovered the joys of OR-Exchange, now would be a pretty good time.  You are far less likely to be greeted with a 500 error!

Operations Research at Business Schools: The Bad!

Right after returning from Egon Balas’ 90th Birthday tea, as I thought good thoughts about the role operations research plays in business schools, I read some disconcerting news from the College of of Business and Economics, University of Canterbury in Christchurch, New Zealand, from Dr. Nicola Petty:

On Wednesday the Council of the university at which I have been employed voted to close down the Operations Research programme. The university wants to “concentrate” and OR didn’t make the grade, despite two academics taking voluntary redundancy, and a concerted effort to streamline the programme so that it is financially viable. It is the end of an era.

Let me begin by saying that I love New Zealand and its universities.  I spoke at a number of them in 2007 when I was the New Zealand Operational Research Society Visiting Speaker, and I spent a wonderful couple of days at the University of Canterbury.  Christchurch is a beautiful town that has had a tough time of it recently.  And I have no direct knowledge of the challenges the university faces, or what went into the decision.

That said, I have to ask:

What the heck is that university thinking?????

Here we are, entering a golden age of analytical decision making.  We are in a world where companies are drowning in data but are unable to make sense of it to turn data into better decisions.  Where companies like IBM put business analytics front and center in their strategic plans.  Where a key managerial skill is understanding data and applying analytical approaches to problems.

What kind of management program would purposefully cut their business analytics capabilities in this world?

Stunning.

As an academic administrator in a business school, I guess I am happy to see our “competitors” making themselves weaker.  More for us, I guess.

As someone in operations research, it is depressing to see how some academic administrators just don’t get it.  It gives the rest of us academic administrators a bad name.

If you are a student planning to study management, please ask the question:  am I going to get the skills I need to survive and thrive in a data-rich environment full of complicated decisions?  A management school that is running away from analytics is a school that is living in the past.


Operations Research and Business Schools: The Good!

Way back in 1988, I was a fresh Ph.D. out of Georgia Tech doing a postdoc at the Institute for Mathematics and its Applications at the University of Minnesota.  While I had plans to spend another postdoc year, likely in Europe (and I ended up doing so, in Germany), I did decide it would be good to lock up an academic job before I left.   Email did exist at the time, but the norm was to send things out via “regular” mail.  So I went down to the copy center at the University and picked out a suitably heavy-weight paper for my vita.  I sent out a dozen or so responses to job ads and made a few phone calls (or asked my advisor to make a few calls) and was invited to visit a half-dozen or so places.  Perhaps it was  different era, or perhaps I was relaxed knowing that I had another year of postdoc funds if needed, but it certainly felt more relaxed that it appears to be these days.

One place that seemed eager to have me out was this “business school” at Carnegie Mellon:  The Graduate School of Industrial Administration.  Now, I came out of engineering and I certainly believed that my future lie in engineering.  Here is a sign of how little those of us in engineering knew about business schools:  the previous year, a fellow doctoral student went out on the market and interviewed at a number of places before finding a job at a business school.  At the time, we were all a bit surprised since he had a good dissertation and we (other doctoral students) thought that it was good enough to get a top engineering job.  Too bad he was stuck in a business school, we said:  must be a tough job market.  That school was the University of Chicago, then and now a preeminent business school that much of the field would kill to get a job at. Business schools were really not on our radar.

But I was polite, so I agreed to head out to Carnegie Mellon.  It was my first job interview, so I told myself the school would be a great place to practice my talk before moving on to the real contenders.

I hadn’t planned on liking CMU and GSIA as much as I did.  The people I talked to were much different than those at engineering schools.  Of course, there were some top-notch OR people (more on them later) but I also talked to economists and political scientists and even a psychologist or two.  They were involved in fascinating research that was a little less … transactional than much of engineering research (“Do this since the grant depends on it”).  And the Deputy Dean of the time, Tim McGuire (now at Management Science Associates) was very persuasive about how exciting things can be in business schools.

But even more persuasive was Egon Balas, an intellectual leader in the operations research since the 1960s.  While I did (and do) find him a bit intimidating, Egon had (and has) a tremendous love for integer programming, and amazing energy in research. He also had spend decades keeping up the tradition GSIA had of having a great OR group.  Founders such as Herb Simon, Bill Cooper, Al Blumstein, and Gerry Thompson had been (or in Gerry’s case, still were) part of GSIA, and the OR group was, in 1988, pretty amazing: Gerard Cornuejols and John Hooker joined Gerry and Egon to form the group.

I received an offer from GSIA and from some top engineering schools, and, to my surprise, I decided that my future lay in the business school.  And that is not a decision I have regretted.  GSIA (now Tepper) continues to have a top-notch OR group.  Gerry retired, then passed away, but we added R. Ravi, Javier Pena, Francois Margot, Willem van Hoeve, and Fatma Kilinc-Karzan.  Gerard Cornuejols continues to do amazing work, having recently won the von Neumann Theory Prize.

With the larger faculty size comes a stable and important role within the business school.  Operations research is seem as a key competitive advantage to our school.  While there are many aspects of this advantage, I’ll point to two:  the increased role of business analytics, and the role rankings play in business school success.  If you don’t believe me on the latter, I’ll point you to the list of journals Business Week uses for their intellectual capital ranking.  If you have people who can publish in Operations Research, you can be a more successful business school.  I recently heard my Dean, a hard-core finance researcher, say “We need more OR faculty”:  music to my ears!

And, the best part is, Egon Balas is still with us and still active.  He turns 90 this week, so we had a tea for him (we had a big conference when he turned 80;  we can do that again for his 100th).  A bunch of us did short video clips to wish Egon happy birthday.  Here is mine:

As you might guess, I am proud to be part of the operations research group here at the Tepper School. The school has been very good for operations research … and operations research has been very good for the school.