Month: June 2011

Explaining Operations Research to, and being, a Muggle

In J.K. Rowling’s Harry Potter books, “Muggles” are people who have no magical ability, and, indeed, no knowledge of the magical world.  The term “Muggle” is not exactly a compliment, and veers towards a pejorative.  From the first book:

Hagrid: “I’d like ter see a great Muggle like you stop him,”
Harry: “A what?”
Hagrid: “A Muggle. It’s what we call non-magic folk like them. An’ it’s your bad luck you grew up in a family o’ the biggest Muggles I ever laid eyes on.”

It is a little hard to see anything positive about Muggle in this exchange!  Muggles are often willfully blind to the magic that goes on around them (though sometimes an Obliviator or two can help muggles forget something a little too spectacular), and are generally far less interesting than the magical folk.

But Ms Rowling is pretty even handed in its treatment of the magical world/non-magical world divide.  Just like non-magical folk have no understanding of Quidditch, dementors, Patronus charms and the rest, the magical world is equally confused about the non-magical world:

Arthur Weasley: What exactly is a rubber duckie for?

The definition of a Muggle depends on where you stand!

Now what does this have to do with operations research (other than being the theme of this month’s INFORMS Blog Challenge, of which this article forms my entry)?  A wonderful aspect of working in operations research, particularly on the practical side of the field, is that you both work with Muggles and get to be a Muggle.

Working with Muggles is pretty obvious.  We in operations research have these magical powers to do incredible feats.  Have a problem with millions of decisions to make?  Easy!  Well, easy as long as we can assume linear objective and constraints, and that the data is known and fixed, and …. (magic even in Harry Potter’s world has limitations).  But for the Muggles to believe our results, we do have to spend time explaining what we do and the assumptions we work with.  So we trot out some simple examples, like the traveling salesman problem (“Consider a traveling salesman who has to visit the cities on this napkin”:  don’t laugh!  That is the first real conversation I had with the woman who eventually decide to marry me!).  And we explain why the problem is hard (“Consider how many tours there are”).  And sometimes we convince the whole world of the difficulty so well that they don’t listen to the next part:  “Despite the difficulty, we can really solve these models”.  There are whole swathes of the world, including, it seems, much of computer science, that believes that 30 city traveling salesman instances are a true challenge, requiring an immediate application of approximation algorithms or heuristic methods.   But then we solve interesting problems, and the Muggles begin to believe.  And that is very satisfying.

But it gets even better when we in operations research get to be the Muggles.  And this happens a lot on the practical side of operations research because we get to work with a lot of very smart and very interesting people outside of our field.  A few years ago, I worked with the United States Postal Service to redesign its processing and distribution network.  I know a lot about optimization and models and algorithms.  About all I knew about postal delivery is that a very friendly guy comes by practically every day around 11, and he prefers if I park my car back about two feet so he can cut through the driveway easier.  Turns out there is a heck of a lot more to the Postal Service than Postman Pete and his walk through our neighborhood.  So I got to be the Muggle and to learn about the issues in getting mail from one side of the country to the other in a reasonably timely fashion.  There is “First Class Mail” and “Third Class Mail”, but no “Second Class Mail”.  Why?  Well, that’s quite a story, let me tell you!  And after a few months, I felt that I had passed my first class in the Magic of Mail, but was nowhere near losing my Muggle designation.  But I knew enough to create a few models, and I could explain them to the Wizards of the Mail, and they could correct my Muggle understanding of mail processing (“No, no, no:  a flat could never be handled in that way:  that is only for Third Class, silly!”).  And eventually we arrived at models that did a pretty good job of representing the mail system.  I was a bit less of a Muggle about mail, and they were a bit less Mugggley about operations research.

Over the years, I have started as a Muggle about cell-phone production, sports scheduling, voting systems, and a number of other areas.  And I got to read about these areas, and talk to smart people about issues, and, eventually, become, if not a Wizard, then at least a competent student of these areas.

Some fields are, by their nature, inward looking.  The best operations research is not, and that is a true pleasure of the field.

Another Operations Research Challenge: ROADEF, EURO, and Google

I am a big fan of “challenges” in operations research.  Almost twenty years ago, I ran a DIMACS Challenge on finding cliques, coloring graphs and solving satisfiability problems.  That challenge gave a clear picture of where we were then in those areas and showed the variety of approaches possible for those three problems.  I also  met a large number of people and took pride in creating something useful to many.

ROADEF (the French OR Society) has run a series of Challenges over the years.  These challenges have been inspired by real-world problems and are generally very rich in detail (details on past Challenges, including test instances, are available at the Challenge site).  The recently announced 2012 Challenge is no different.  The problem to be solved comes from Google, and involves assigning jobs to machines.

The aim of this challenge is to improve the usage of a set of machines. A machine has several resources as for example RAM and CPU, and runs processes which consume these resources. Initially each process is assigned to a machine. In order to improve machine usage, processes can be moved from one machine to another. Possible moves are limited by hard constraints, as for example resource
capacity constraints, and have a cost. A solution to this problem is a new process-machine assignment which satisfies all hard constraints and minimizes a given objective cost.

The problem description then goes on for 10 pages, including issues such as locations, services, conflicts, moving costs and much, much more.  This certainly looks like a real problem and one that a firm like Google would need to solve routinely and quickly.  I can also see a number of different approaches that might work.  I look forward to seeing what methods are successful for this.

This Challenge is sponsored by ROADEF, EURO, and Google.  Google, for all its success, has only recently started to use and support operations research (though the line between computer science and operations research is very fuzzy in this area), so I am delighted to see their support of this Challenge.  Now, how about some million dollar prizes to go with it … (though 20,000 euros is not to be sniffed at).

Are you an Undergraduate who has done Great OR?

If you are an undergraduate student who has done great operations research, or know someone like that, note that INFORMS has a prize for great undergraduate work.   The work can be in OR theory or practice, but the judging is based on a paper.  You can find out more information at the INFORMS website.  Better hurry, though:  the due date for submissions is July 1.

On the Shoulders of Giants

Yesterday I was messing around with The Mathematics Genealogy Project and I learned that Anna Nagurney, among others, is a not-so-distant cousin.  That inspired me to shoot off a couple of emails trying to trace my history farther back.

To recap, my advisors were Don Ratliff and John Bartholdi.  John was a student of Don, so Don is both my father and grandfather, a situation that would certainly raise eyebrows outside of academia.  Don’s advisor was Manny Bellmore who did a lot of fundamental work in the late 1960s and 70s on the traveling salesman problem and various other optimization problems.  Manny’s advisor was Frederick (Tom) Sparrow, who did extensive work in energy modeling and policy, among other things.  Bellmore also worked with George Nemhauser, but George was on leave in England when Manny graduated, so Sparrow was the advisor.  It is through Sparrow that I am related to Nagurney.

To continue earlier in history, I shot off an email to Tom, who is emeritus from Purdue.  Fortunately my email got through the spam filters (starting an email “Hello Great-Grandfather” does make it sound like a plea from a Nigerian prince), and he could tell me about his advisors.  He had two  The first was an economist named Kenneth Boulding.  This is a name I should know but do not.  He did some fundamental work in systems science and conflict analysis starting in the mid-1950s with some papers that are incredibly well cited.  When the wikipedia description begins with:

Kenneth Ewart Boulding (January 18, 1910 – March 18, 1993) was an economist, educator, peace activist, poet, religious mystic, devoted Quaker, systems scientist, and interdisciplinary philosopher

it is clear we are talking about someone unusually interesting.

Tom’s other advisor is, however, known to me (as it is to many in operations research):  Merrill Flood (1908-1991).  Flood was a founder of the field of operations research.  He worked on transportation problems in the 1930s and developed the “Northwest Corner” rule for finding a solution to such problems, before Dantzig developed a general method for optimizing these problems.  He also was an early researcher on the game-theory problem Prisoner’s Dilemma.  He was also an influential popularizer of the Traveling Salesman Problem.   He was the second President of TIMS, and he received the Kimball Medal for services to the field (a designation I have the honor to share with him).

Flood happens to be in the Mathematics Genealogy Project (though without listed advisees) and his advisor was Joseph Henry Maclagan Wedderburn (1882-1948), Scottish-born algebraist who taught at Princeton for most of his career.  Wedderburn’s advisor was George Chrystal (1851-1911),  whose advisor was James Clerk Maxwell (1831-1879), father of electromagnetic theory!  Checking out his wikipedia article leads to the immortal verse:

Gin a body meet a body
Flyin’ through the air.
Gin a body hit a body,
Will it fly? And where?

Going back from Maxwell, we get William Hopkins (1793-1866), who combined mathematics with geology.  I love the wikipedia entry on his private life:

Hopkins enjoyed music, poetry and landscape painting. He spent the end of his life in a lunatic asylum in Stoke Newington. He died there of chronic mania and exhaustion.

Perhaps not an unusual ending for mathematicians.

Back from there we get Adam Sedgwick (1785-1873), a founder of geology.  He had two advisors:  Thomas Jones (1756-1807) and John Dawson (1734–1820), a mathematician and surgeon.  Dawson leads to Edward Waring (1736-1798), a Lusasian Professor of Mathematics.

On the Jones side, we get two advisors: John Cranke (1746-1816) and Thomas Postlethwaite (1731-1798).  Fortunately Cranke was the student of Postlethwaite, so we don’t branch (making an already large lineage even bushier).  At this point we hit two Cambridge tutors:  Stephen Whisson (?-1783) and Walter Taylor (c1700-1743).  Taylor was trained by Robert Smith (1689-1768), known as Old Focus for his work in optics.  Smith leads to Roger Cotes (1682-1716), who worked closely with his advisor… Sir Isaac Newton!  That makes Sir Isaac my Great-Great-Great-Great-Great-Great-Great-Great-Great-Great-Great-Great-Great-Grandfather (academically speaking).

From Philosophiæ Naturalis Principia Mathematica to A Dynamical Theory of the Electromagnetic Field to trying to schedule 8 team sports leagues in a mere 15 generations. On the shoulders of giants indeed!

I suspect that if the system was completely filled in, we would all be descendants of Newton.  But I am walking a little taller today, and feeling a bit more pressure in my research, knowing of my illustrious ancestors.

Hello Cousin!

My father has spent time over the last decade collecting pictures and documents related to our family tree.  I greatly appreciate him doing this, and the result is fascinating.  There is no one really famous in my tree, unless you are a follower of (Canadian) prairie socialism, since I think J.S. Woodsworth is in there, by marriage into the Staples family, my father having Staples as a middle name.  But the pictures of past generations are evocative and the stories of families moving from Europe to rural Canada are inspirational.  The bravery in pulling up roots in a world when communication times are measured in weeks or months is unbelievable.  It makes me realize how easy I have had it, and how my own choices are so relatively costless either way.

I addition to real ancestry, there is also academic ancestry, tracing descendents through the academic advisement.  Within operations research (and mathematics more generally), we have a central collection point for academic ancestry:  the Mathematics Genealogy Project.   This site has collected the the advisor/advisee relationships for more than 150,000 mathematicians, including many in operations research.  This site is certainly not new, dating back to 1999 or so 1997, and I have known about it practically since the start.  It is only now, however, that I sent in the information on my own advisors (Don Ratliff and John Bartholdi) and my seven advisees.  It will take a bit of time to update the site.  In the world of Web 2.+, it is strange to have such a delay, but it appears there is still a bit of hand editing.  Soon my tiny part of the tree will be accurate.

For finding my ancestry, the first part is easy:  John Bartholdi was a student of Don Ratliff (starting me on a non-branching family tree), and Don was the student of Manny Bellmore, who also advised now-billionaire John Malone.   Bellmore was the student of Frederick (Tom) Sparrow, a long time faculty member at Purdue.  Looking at Tom’s descendents, I see he was the advisor to Stella Dafermos who advised … fellow OR-blogger, and network guru, Anna Nagurney!  In fact, the picture of Dr. Sparrow comes from Anna’s Virtual Center for Supernetworks. So it turns out that Anna is my … umm… first cousin once removed?  Anyway, we are definitely related, as you can tell by the fact that she writes very well, and I … type things into my blog (generally with too many parentheses and exclamation points!).

I’m continuing to work my way back.  It seems that most people end up back at Gauss, but we’ll see where I end up.  I think I would be more delighted to see that most of operations research blogORsphere comes from close academic relatives!