Category: Blogs and Web

New Year’s Resolutions from Dr. O.R. Field

In a tremendous coup for the blog, I am delighted to present this interview with Dr. Operations Research Field where she sums up the year 2010 and presents her resolutions for the upcoming year.

MT: Dr. Field …

OR: Please, call me O.R.: all my friends do, though some call me M.S. for some reason.  I’ve actually had lots of names in the past.

MT: OK, O.R., thanks for seeing me. I can’t help but notice that you are …

OR: A woman? Yes, well, as an artificial personification of an abstract idea, I can appear as I choose. This year, with the INFORMS President, President-Elect, five Vice Presidents, and interim Executive Director all women, it seems most representative of the field. Not to mention women like MIT’s interim Dean of Engineering, IBM Research’s Vice President of Business Analytics and Mathematical Sciences, and my three of my favorite bloggers (Anna, Laura and Aurelie). And we all know that WORMS has the best panel discussions and receptions!

MT: Well, you are looking very healthy. There were rumors that you were dying. How do you feel?

OR: Dying? Me? Not a chance! I’m sixty years old and healthy as a horse. People have been talking about me dying for decades, and I keep outliving them all. I don’t think there is any chance of me dying anytime soon.

MT: Funny, I could have sworn you were dying. Any proof that you are actually healthy?

OR: Look at the parties I throw every year (that is “professional meetings” when discussing reimbursements with department heads). The last party I threw in Austin drew more than 4600 people! I remember ten years ago I would hold two parties a year and be lucky to get 2000 at either one of them. Any my European parties (and what parties they are!) are also breaking records every year.

MT: Wow, that is pretty amazing. Any other signs of success?

OR: Well, the Edelman Awards showed how international I got, with finalists from the U.S., Mexico, Germany, Canada, and South Africa. INDEVAL from Mexico won with a nifty way of optimally clearing trades in a financial market, meaning financial firms didn’t have to leave loads of cash lying around.

MT: That was a cool paper.  What else?

OR: I love to see all the blogging, tweeting, and other things going on.  OR-Exchange looks to be getting a critical mass of participants, replacing the dear departed sci.op-research.

MT: Hey, that’s not dead!

OR: It does seem to be the place to go if you want a solution manual or cheap shoes.  But lots of other things are replacing it, so I think I’ll survive its loss.

MT Well, what is up for Dr. O.R. Field in the upcoming year? Have you made any New Year’s resolutions?

OR: Hey, that’s pretty clever. By bringing in the holiday, you can enter this post in INFORMS’ December Blog Challenge!

As it happens, I have made resolutions for the upcoming year. Here are a few of them

First, I resolve to embrace and define business analytics.  But, as I recently read…

MT: If people write me, I’ll let you know where you read this..

OR: …Thanks… there is a tremendous risk that business analytics will be conflated with predictive analytics, like data mining, just as the line between business intelligence and descriptive analytics became very fuzzy.  Business analytics has got to go beyond prediction to actual decision making, prescriptive analytics if you will, where complicated decisions are made based on the results of predictive and descriptive analytics.  So the best business analytics will go beyond “Should I send this person a catalog” to “Based on these three predictive models, how should I optimally allocated my marketing budget in the face of these various constraints”.  It is that level that I have the most to add.  And I’d really like to be more famous!

MT: I agree!  I wrote about that in the context of revenue management:  you can use data mining models to provide real-time input into a hotel reservation system to provide a much more profitable and effective overbooking system.  You really need to take ownership of this!

OR: I hope that the revamped INFORMS conference in the spring will really have an effect on how people think about me and business analytics.

My second resolution is to pay more attention to robustness in my models.

MT: You mean like the work of Bertsimas, Ben-Tal and many others?

OR: That is one type of robustness, but I meant something a bit broader.  Let me give you an example:  I was recently flying to one of my parties and had to change planes in Detroit.  Now, a bunch of things have to come together in order for the flight to go.  You need a plane, a pilot, a first officer, a flight attendant and so on on.  Now, if the pilot is on a flight coming in from Pittsburgh, the first officer is on a flight from Montreal, the flight attendant is coming in from Des Moines, and the plane is from Albuquerque, then what is the chance that my flight is going to go?

MT: Pretty small?

OR: Right! Zilch, zero, nix, nada, zippo.  There is no way that plane is going out on time, since it is delayed if even one of those multiple planes is late.  This system may be optimized, but it is certainly not robust.

But if the plane and the whole crew worked together, then my flight would have been late only if one previous plane was late.  This is a much more robust system.

MT: I blogged about David Ryan’s work on this years ago.

OR: Well, I guess no one reads your blog, because it is a huge issue.  Imagine if the financial system was designed with robustness in mind.  We might not know where the uncertainty is coming from (just like we don’t know what plane is late), but the system would better adapt to whatever weird things happen.

MT: Kinda like methods for avoiding bus bunching.

OR: You bet, but on a much larger scale.

My third resolution is to do a better job at getting the word out about me and the wonderful things I do.  We’ve got a few bloggers and a magazine or two but we have to do more!

MT: Well, I’ll do my part!

OR: I hope so.  I don’t want to see any  more disgraces like this year when you had only one blog post in August and two in October.  I almost unfriended you on Facebook for that!

MT: Sorry, I guess I better put that down as my resolution.

So, O.R. any final comments?

OR: Well, three resolutions don’t seem to be enough for me:  I’d welcome any resolutions people might suggest.  And may you all have an optimal New Year!

MT: Happy New Year from me too!  And feel free to add your resolutions to the comments and I will be sure that O.R. sees them.

Operations Research, Sudoko, Rogo, and Puzzles

A few years back, Sudoko became a craze with seemingly everyone spending their time solving these puzzles.  The puzzle is quite simple:  take a nine by nine grid, partially filled in with numbers from one to nine, and complete it so that every row, column, and non-overlapping 3×3 square contains the numbers one through nine exactly once each.  While the grid contains numbers, there is no mathematics involved:  using the letters a-i would work as well.  But you can use mathematics (in the form of logic) to solve the puzzle.  To solve these by hand, puzzlers quickly learn logical rules, from the simple (“If only one square is open in a row, then you know what number goes there”) to advanced (say, alternate pair exclusion).  One can even use the methods of operations research (say, constraint programming or integer programming) to solve Sudoko puzzles.   It does not seem to discourage human solvers to know that these techniques can solve any Sudoko problem in milliseconds.

There is often a close relationship between puzzles and the methods of operations research, particularly networks or discrete mathematics.  Finding a path in a maze is nothing more than a shortest path problem;  “logic” puzzles (“Smith, Jones, and Robinson are (not respectively) a trucker, a fireman, and an engineer, who live in …”, followed by facts, leading to “What is the name of the engineer?”) can be handled through integer programming, and so on.  People, for some reason, like to do combinatorial search in their spare time.

Hamish Waterer, with whom I shared an office in New Zealand and who is now at Newcastle in Australia, pointed out to me a puzzle that has even closer ties to operations research: Rogo.  In Rogo, the goal is to find a loop through a grid of fixed length that contains as many reward points as possible.    So, for this example (taken from the Rogo site)

the goal in this example is to find a loop of no more than 12 steps that includes as many points as possible.   The loop must be a real loop:  it must return where it started and can’t cross itself or double back. Steps can be either horizontal or vertical:  they cannot be diagonal.  The loop cannot include any of the black squares.  Here is the solution:

Rogo was created by two faculty members (Nicola Petty and Shane Dye)  at the University of Canterbury in Christchurch, New Zealand.  Not surprisingly, Nicola and Shane teach management science there:  the problem has a very strong operations research flavor.  This is a form of the Prize Collecting Traveling Salesman problem, originally studied by my colleague Egon Balas (in the regular PCTSP, there is a penalty for distance traveled:  in Rogo, there is an upper bound).

If you want to play around with this, you can get the iPhone (touch, pad, etc.) app. Creating a solver would make a nice undergraduate project (and I suspect there are at least a few master’s theses and perhaps a doctoral dissertation on algorithmic aspects of creating and solving these).

The Great Operations Research Blog Challenge

At the recent INFORMS conference, a group of bloggORs (get it?) got together to discuss what sort of common activities we could do.  While we all read each others work, and periodically repost each others work, for the most part we work alone.  That is generally a good idea:  we each have a style to our blog (I wouldn’t dare to talk about vampires, for instance, leaving that to the expert).  But we are a community.  I point to all the OR blogs I can find and provide a feed of the latest posts in my sidebar;  we sit on panels together; there is the odd off-blog conversation about blogging and OR issues.  How can we strengthen that community?

Inspired by the Carnival of Mathematics , the group decided it would be fun to have a monthly theme on which we could all write.  All the resulting entries could then be collected at the end of the month.  The INFORMS Blog was elected to be the coordinator of this activity, and has just announced the first monthly Blog Challenge:

Topic for December 2010: O.R. and the Holidays

Open to all bloggers! All you have to do is a write a post on your site on that topic then send the pointer to graphics@mail.informs.org.  Given there are a couple dozen blogs in my “OR Blog Roll”, it would be great to get a big response to this. No prizes, but, as the announcement says:

What’s in it for the bloggers? Widespread fame by being listed on the INFORMS home page. Or at least a bump in readers and an increase in standing and influence in the operations research blogosphere.

Keto Diets and Linear Programming

In today’s New York Times Magazine, there is an article on how a ketogenic (“keto”) diet can be used to control epileptic seizures in kids.  The diet is quite something.  Referring to his son’s diet, the author Fred Vogelstein writes:

His breakfast eggs are mixed with heavy cream and served with bacon. A typical lunch is full-fat Greek yogurt mixed with coconut oil. Dinner is hot dogs, bacon, macadamia nuts and cheese. We figure that in an average week, Sam consumes a quart and a third of heavy cream, nearly a stick and a half of butter, 13 teaspoons of coconut oil, 20 slices of bacon and 9 eggs. Sam’s diet is just shy of 90 percent fat.

The diet contains almost no carbs, making it reminiscent of an Atkin’s diet during a particularly anti-carb phase.  This diet has the effect of greatly reducing the number of seizures in many kids, including those who have not responded to any of the possible drugs.  In Sam’s case, the seizures went from hundreds per day to perhaps a half dozen.

While a diet of bacon and ice cream seems like heaven, it is actually very hard to do.

For Sam’s diet to be effective, he must eat a certain number of calories every day with specific ratios of fat, protein and carbohydrates. These are not back-of-the-envelope calculations, but ratios that have to be hit exactly at every meal. If Sam wants a snack after school, he gets 18 grams of bacon (about two slices), 14 grams of macadamia nuts (about seven nuts) and 18 grams of apple (less than an eighth).

You can’t just throw together everything without carbs and hope that things work:

To jump through these arithmetic hoops, Evelyn, who gave up her career to take on the now full-time job of feeding Sam, plans meals on the kitchen computer using a Web-based program called KetoCalculator. It is hard to imagine how to administer keto without it. A meal for Sam might have eight ingredients. Mathematically, there are potentially millions of combinations — a bit more of this; a bit less of that — that gets you to a 400-­calorie meal and a 3-to-1 ratio.

I don’t have access to the Calculator (you need to be referred to it by a doctor), but it would be interesting to know if the site goes beyond just being a calculator.  Putting together ingredients to meet dietary requirements is a classical problem for linear programming.   Rather than just determine if a set of ingredients meets the requirements, a linear-programming approach would put the ingredients together in an optimal way to meet the requirements while optimizing some objective (like maximizing use of ingredients you have not eaten in the last week, or maximizing use of some food you have a craving for).  No hit-or-miss calculating:  the combination would be guaranteed to meet the dietary requirements.

You can check out the NEOS server to experiment with putting together a traditional diet.  I would love to experiment with a site that creates keto diets.  Imagine being able to turn an illegal, but palatable, meal into a legal meal by adding 3 macadamia nuts (and have the linear program automatically suggest that).

In the past, I have used the diet problem for laughs, but this seems to be a real application for  operations research that could be very useful (if it is not already being used).

Yet More Tag Clouds

@polybot on twitter pointed to the Tagxedo site, a site that creates displays of words, kinda like Wordle.  There are a zillion choices (and even a presentation on 101 things you can do with Tagxedo).  Here are a few I generated while Alexander did homework and I watched football on a rainy Sunday.

What is operations research?  (based on the words in this blog)

What am I tweeting about?

Who am I (from my home page, it is not obvious but the background is a picture of me)

Here are words from the biographies of my twitter followers:

I don’t know if they mean anything, but they are fun to play with!

Definitive Word on P!=NP Paper

Lance Fortnow of the blog Computational Complexity has, I believe, the definitive word on the P!=NP paper by Deolalikar (saying in a sentence what I couldn’t quite manage in two pages):

Proving P  ≠ NP will require pure genius but you shouldn’t need a Fields medalist to verify the proof.

Secondary message:  a good way to determine if a proof will work is to count the “clearly”s and “should be able to”s:  more than one or two and the proof likely will fall apart at the slightest breath.

P versus NP and the Research Process

By now, everyone in computer science and operations research is aware of the purported P<>NP proof of Vinay Deolalikar of HP Labs.  After intense discussion (mainly through blogs and wikis), the original paper was taken down, and Vinay has prepared a new version for submission.  He claims:

I have fixed all the issues that were raised about the preliminary version in a revised manuscript (126 pages); clarified some concepts; and obtained simpler proofs of several claims. This revised manuscript has been sent to a small number of researchers.  I will send the manuscript to journal review this week. Once I hear back from the journal as part of due process, I will put up the final version on this website.

I am convinced by Dick Lipton’s blog entry and by Scott Aaronson’s commentary suggesting fundamental flaws in the paper, but since Vinay has not retracted the paper, I will look forward to the definitive version of the paper.  For a detailed description of the issues, press coverage, and other aspects, polymath has an extensive wiki on the topic.

What I find most intriguing is the field’s response to this claimed proof.  Proofs that P=NP or P<>NP are certainly not uncommon.  Gerhard Woeginger faithfully keeps track of these claims and is up to 62 in his list.  Some of these results come out of the operations research world.  For instance, Moustapha Diaby is a faculty member at the business school at the University of Connecticut and believes he has found linear programming formulations for NP-hard problems (number 17 on Woeginger’s list).

The Deolalikar paper is unique, however, in that many, many top mathematicians looked very closely at the paper and worked very hard to determine its correctness.  This group includes people like Fields-medal winner Terrence Tao and Polya and Fulkerson prize winner Gil Kalai.  Why did so many very smart people (and successful!  They don’t do wikipedia pages on just anyone [yet]) spend time on this while practically no one spends time with the other 61 purported proofs?

The most obvious reason is that this paper presented a fundamentally new approach to this problem.  As Lipton says: “the author has advanced serious and refreshingly new ideas of definite value”.  In this proof, Deolalikar uses finite model theory, an area of logic, to deduce structures in random satisfiability problems.  If P=NP, then the structures would have to be different than what is already known about random satisfiability problems in the critical region (this synopsis is vague to the point of not being usable). This is definitely a different direction than past efforts, bringing together a number of disparate fields.

Further, Deolalikar knows very well that there are a number of proofs in the literature that say “P<> NP cannot be proved this way”.  For instance, any result that cannot distinguish between the easy 2-satisfiability and the hard 3-satisfiability is doomed to failure (Aaronson’s blog entry gives a few others along with other signs to check for in claimed proofs). Deolalikar presented reasons for believing that his approach evaded the barriers.    This leads to excitement!  Could this approach avoid known invalid approaches?

Contrast this with papers that suggest that a linear programming model can correctly formulate an NP-complete problem.  Yannakakis showed that no symmetric formulation can do so, and that provides a powerful barrier to linear programming formulations.  Not only must a a formulation not be symmetric, but its asymmetry must be of the sort that continues to evade Yannakakis’ proof.  Without a strong argument on why an LP formulation fundamentally avoids Yannakakis’ argument, it is not even worthwhile spending time with LP formulations of  NP-complete problems.

This overwhelming doubt was clearly not felt by some referees who allowed Diaby’s papers to be published in “International Journal of Operational Research”, lending credence to the idea that the refereeing and journal process in operations research is broken (in my view, of course).  For the steps given in the Computational Complexity blog, we have have to add a step: “Your paper is accepted by a third tier journal and still no one believes it.”  Similarly, it will not be enough for me to see that Deolalikar’s paper is published:  at this point I trust the blogs (some of them, anyway) more than the journals!

Even if the Deolalikar result is shown not to be valid, the paper gives me enormous hope that someday the P<>NP (as I believe it is, rather than P=NP) will be proved.  We appear to be developing methods that will have some traction in the area.



Five Sundays, Mondays, and Tuesdays and Operations Research Training

A half dozen times in the past couple of weeks I have either been told, received an email, or otherwise ran across the following “fact”:

August 2010 has five Sundays, Mondays, and Tuesdays, and this won’t happen again for 823 years!

Wow!  That is pretty amazing.

It is also completely ridiculous and false.  May, 2011, for instance, has five Sundays, Mondays, and Tuesdays.  Even if the issue is an “August” with this structure, this occurs again in 2021 and 2027.  A moment’s thought reveals that you get five of those days anytime a month with 31 days starts on a Sunday, which has to be about 1/7 of them.   Since 7/12 of the months have 31 days, you would really expect about one month a year to have this structure, and that seems to be the case.

But, given all the repeats of this, there clearly are a lot of people who will buy into this sort of nonsense.  Why is that?  This really is a failure of mathematical training.  One reason we teach mathematics is to get people to think clearly and analytically on issues.  Ideally this would mean that people would immediately have an intuition that a result like this means that 31 day months (or August in particular) rarely start on a Sunday.  But experience shows that is not the case:  if the first day of some months is rarely a Sunday, surely I would have noticed that by now!  A quick check of any online calendar shows that the “fact” is false, and somebody has invented something ridiculous in order to see how many people can fall for this false meme.

Perhaps in operations research we have an advantage:  we are used to questioning the assumptions that go into models and looking carefully at the resulting solutions.  “Is this really linear?”  “If I assume X, what does that imply about Y?” “Does this answer make sense?”  Perhaps with a bit more OR training, urban myths will have to become a bit more sophisticated before they grab the public’s attention.

Become Rich and Famous at INFORMS Online

Well, not rich in the financial sense, but rich in social capital and other rewards.

INFORMS is looking for the next editor of INFORMS Online.  I was the founding editor of IOL, with a term from 1995-2000, and it was one of the formative experiences of my life.  I learned a lot about operations research, INFORMS, organizing things, inspiring people, and myself during that time.  In that time, the IOL team took INFORMS into the internet age.  A person I admire greatly said that the best part of the merger of ORSA and TIMS (the predecessors of INFORMS) was that something like INFORMS Online could happen and I am very proud to have been part of that.

Back then, in the dark ages, the job of Editor was very hands-on.  The editorial team and I hand-coded much of the visible portions of IOL.  We installed database programs and wrote codes that handled the membership directory and the conference database.  In short, we did a lot of grunt work.  You can still see some remnants of that period:  if you go to IOL and check the tab on your browser, you will see a little square icon saying “OR/MS” in white and blue (you can see it on the graphic next to this post).  I hand-created that, picking out the blocks using a freeware icon editor in 1997 (when Internet Explorer 4 was released, supporting such icons).  It is still there:  my little bit of fame on the internet.

The job of editor of IOL is a lot different now.  Between INFORMS’s wonderful staff and IOL’s content management system, there is little actual coding done by the editor.  Instead, the editor and his or her team gets to think of all the ways that IOL could be used to advance INFORMS and the field of operations research.  How can we create real communities?  What services do subdivisions need that IOL can provide?  How can we better advertise all the wonderful things our field does?

Being Editor of IOL lets you meet with a wide variety of people in operations research (and become a little famous along the way).  It does take work:  we estimate it takes around 4 hours per week, but the effort depends on the goals and aspirations of the Editor.

If you are interested, nominations are due by the end of August.  And self-nominations are perfectly fine, and even expected.

New Use for Abstracts

For a previous post on data mining, I received the following comment from “liseli bakire”:

Abstract
The purpose of this article is to investigate some managerial insights related to using the all-unit quantity discount policies under various conditions. The models developed here are general treatments that deal with four major issues: (a) one buyer or multiple buyers, (b) constant or price-elastic demand, (c) the relationship between the supplier’s production schedule or ordering policy and the buyers’ ordering sizes, and (d) the supplier either purchasing or manufacturing the item. The models are developed with two objectives: the supplier’s profit improvement or the supplier’s increased profit share analysis. Algorithms are developed to find optimal decision policies. Our analysis provides the supplier with both the optimal all-unit quantity discount policy and the optimal production (or ordering) strategy. Numerical examples are provided. © 1993 John Wiley &amp; Sons. Inc.

Looks vaguely relevant, though not really pertinent to the topic.  My spam filter had no chance on it:  it passed it through as legit.  But why this abstract?  Ah, “liseli” has a porn site linked to the name (and it turns out the name means “high school virgins” in Turkish).  All part of the cat and mouse game as people try to get links on to the all-powerful “Michael Trick’s Operations Research Blog”.   But extra points for actually using an operations research oriented abstract!

By the way, the paper with that abstract is by Kevin Weng and Richard Wong, “General models for the supplier’s all-unit quantity discount policy, Naval Research Logistics, 1993.  Looks like an interesting paper!