Open problems & unsolved mysteries in operations research

When I attend conference talks, I sometimes hear a speaker mention how a problem is “open.” Sometimes the open problem is of interest only to the speaker and sometimes the open problem is of interest to the whole community. I am blogging about the open problems in computational operations research that have broad appeal.

A list of open problems in computer science include some familiar open problems in operations research, including:

  • Does P-NP?
  • Does linear programming admit a strongly polynomial-time algorithm?

There are open problems in operations research too.

Saul I. Gass and Arjang A. Assad proposed a list of great unsolved problems in operations research (GUPOR – not my acronym!) in a 2007 OR/MS today by soliciting experts.

  1. Need and Potential for Real-Time Mixed-Integer Programming by George L. Nemhauser Engineering grand challenges
  2. Increase in Flight Delays Calls for Better Air Traffic Management by Michael O. Ball
  3. Responsibility of O.R. for Disaster Management by Martin Starr

Several sessions at the 2006 INFORMS Annual Meeting were devoted to these problems as well as other problems such as healthcare delivery.

More recently, Mikael Rönnqvist, Sophie D’Amours, Andres Weintraub, Alejandro Jofre, Eldon Gunn, Robert G. Haight, David Martell, Alan T. Murray, and Carlos Romero wrote OR challenges in forestry: 33 open problems. I won’t list all of the open problems, but will say that many are of general interest and involve transportation problems such as the vehicle routing problem.  You can read the full paper in Annals of Operations Research here.

And finally, two years ago I blogged about engineering grand challenges that operations research can help solve from an NSF report. Challenges areas from the report include:

  1. OR: A General-Purpose Theory of Analytics
    “The time has come to engage both domain experts as well as OR experts, so that policies/decisions become an integral part of analysis, not an afterthought.”
  2. OR for sustainability
    “The Earth is a planet of finite resources, and its growing population currently consumes them at a rate that cannot be sustained. Utilizing resources (like fusion, wind, and solar power), preserving the integrity of our environment, and providing access to potable water are the first few steps to securing an environmentally sound and energy-efficient future for all of mankind.”
  3. OR for security
    “As our interconnected systems grow in complexity, having a trusted operational model is even more essential for assessing system vulnerabilities and, in turn, addressing the challenge of how to secure that system.”
  4. OR for human health.
    Also see my last blog post on healthcare challenges – I’m glad the White House and the OR community agree with this one!
    “One of the most significant problems facing the health care system is keeping costs under control while providing high levels of service. Doing so requires a careful analysis of costs and benefits, but as Kaplan and Porter (2011) argue, “The biggest problem with health care is that we’re measuring the wrong things the wrong way.” “
  5. OR for Joy of Living
    “For example, reducing traffic congestion in urban areas, improving response times of first-responders, designing smart, energy efficient homes, and others raise many novel OR questions. One such example is an application related to predicting movie recommendations associated with the so-called “Netflix Prize” problem. Other “joys of life,” such as sports, have also seen many applications of analytics; in addition to the well publicized baseball movie “Moneyball,” there is Major League Baseball scheduling which is done routinely using OR models. In this sense, OR casts such a wide net in the “Joy of Living” area, that the following subsections (pertaining only to the NAE Grand Challenges) explicitly discuss only a small subset of applications for “Joy of Living.” “

Which problems do you think should be on the list of open problems in operations research?


One response to “Open problems & unsolved mysteries in operations research

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: