Category Archives: Uncategorized

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?

unsolved


Happy 50th anniversary UW-Madison Industrial and Systems Engineering!

On Saturday, my department celebrated the 50th anniversary reunion since the ISyE was first established at the University of Wisconsin-Madison. 50 years of excellence. Jeff Linderoth and alum Jessica Rannow did such a wonderful job live-tweeting the event that I will recap the reunion using tweets.

reunion

 

 

 

 

 

I gave a talk on airport security at the reunion. My slides are below.

I took out all the formulas in my talk and replaced them with comic strips and political cartoons. This comic strip was the highlight of my talk.

I took out all the formulas in my talk and replaced them with comic strips and political cartoons. This comic strip was the highlight of my talk.

 

 

 

 

 

 

 

 

 

 

 

 

And finally, we celebrated at a lovely poster reception and banquet. Jeff Roznowski — Professor at the Milwaukee School of Engineering and author of “I am the Wisconsin Idea” — talked about the Wisconsin idea. Our alums really love the idea of UW-Madison giving back to the state and extending its influence past the boundary of campus. I’m glad they love the Wisconsin Idea as much as I do.

Me heading to the reunion banquet

Me heading to the reunion banquet


airport security lines & queues

Yesterday I was on “Live at Four” on WISC-TV (theCBS affiliate in Madison, WI) to talk about airport security queues, May 31, 2016. As always, it was a lot of fun. I was thrilled to sneak in a short lesson or two about queueing theory.

You can watch the video below:

Screenshot 2016-06-01 15.52.46


Adversarial risk analysis and critical infrastructure workshop

On May 23-27, 2016 I attended a workshop on Adversarial Risk Analysis and Critical Infrastructure at the Lorentz Center in Leiden. The organizing committee consisted of:

David Banks (Durham, NC, USA)
Vicki Bier (Madison, WI, USA)
André Hoogstrate (Den Haag, The Netherlands)
Wolter Pieters (Delft, The Netherlands)
Ketil Stølen (Oslo, Norway)

The workshop had attendees from the US and Europe. My talk was entitled “Maximal coverage models for trustworthy computing” with my student Kay Zheng. I was pleased to see several other talks on cyber-security. The small workshop led to in depth discussion during and after each talk that was refreshing.

Here are a few pictures:

The workshop organizers organized a four hour tour of the waterways in the Netherlands on the “Partyboot.” It was heaven. I enjoyed the sights, chatting with other workshop attendees, and eating the amazing Indonesian buffet.

A selfie inside my office in the Lorentz center. The facilities were great! Plus, free coffee all the time.

The Leiden hotel, the conference hotel, had gorgeous views of the water

At a bar I saw the world’s cutest roll of toilet paper. I couldn’t resist posting a picture.

I enjoyed the workshop so much. The workshop was attended by a small group of about 40 researchers whom I got to know during the workshop. We had plenty of chances to talk and exchange ideas during coffee breaks and over meals. The venue (the Lorenz Center) was great. They assigned workshop attendees to offices, had great wi-fi, and had a nice break room with coffee and snacks.

 

 


If a mathematical model is solved in a forest and a decision-maker is not around to see it, does it have any impact?

I am attending a workshop on Adversarial Risk Analysis and Critical Infrastructure at the Lorentz Center in Leiden. David Banks, a statistics professor at Duke and one of the workshop organizers, proposed* three levels for modeling that applies to research in statistics, operations research, and optimization:

  • LEVEL 1: You solve the problem.
  • LEVEL 2: You solve the problem in a cost-effective manner (e.g., using heuristics to get a quick solution that is “good enough”)
  • LEVEL 3: You solve the problem in a cost-effective manner that a decision-maker will implement

The other conference attendees (mostly academics) seemed to like these three levels as much as I did. Academics like David and I spend most of our time on Level 1 even though we recognize that the point of doing all this academic work is to inform decision-making. We try to reduce the gap between Level 1 and Level 3 through our work and we occasionally make that leap. We have clearly seen that happen in optimization modeling, where academic work on cutting planes (once Level 1) first developed decades ago is now standard in off-the-shelf optimization software (definitely Level 2 without a loss in quality and maybe Level 3). It might take a few years to get to Level 3, but that is how progress and innovation work.

But that is not why David brought this up. He mentioned informing decisions during a discussion about homeland security and terrorism, and making the jump from Level 2 to Level 3 is tough because the decision-makers–who are often politicians–are not often receptive to math modeling. That’s not to say we should give up, but rather, we should sometimes start with Level 3 as the goal and work backward by rethinking what the problem is and how we solve it.

What do you think?

* David said he “made up” these levels last week.


Public sector operations research: the course!

Course introduction

I taught a PhD seminar on public sector operations research this semester. You can read more about the course here. I had students blog in lieu of problem sets and exams They did a terrific job [Find the blog here!]. This post contains summary of what we covered in the course, including the readings and papers presented in class.

Readings

Public Safety Overview

  • Green, L.V. and Kolesar, P.J., 2004. Anniversary article: Improving emergency responsiveness with management science. Management Science, 50(8), pp.1001-1014.
  • Larson, R.C., 2002. Public sector operations research: A personal journey.Operations Research, 50(1), pp.135-145.
  • Rittel, H.W. and Webber, M.M., 1973. Dilemmas in a general theory of planning. Policy sciences, 4(2), pp.155-169.
  • Johnson, M.P., 2012. Community-Based Operations Research: Introduction, Theory, and Applications. In Community-Based Operations Research (pp. 3-36). Springer New York. (Originally an INFORMS TutORial)
  • Goldberg, J.B., 2004. Operations research models for the deployment of emergency services vehicles. EMS Management Journal, 1(1), pp.20-39.
  • Swersey, A.J., 1994. The deployment of police, fire, and emergency medical units. Handbooks in operations research and management science, 6, pp.151-200.
  • McLay, L.A., 2010. Emergency medical service systems that improve patient survivability. Wiley Encyclopedia of Operations Research and Management Science.

Facility location

  • Daskin, M.S., 2008. What you should know about location modeling. Naval Research Logistics, 55(4), pp.283-294.
  • Brotcorne, L., Laporte, G. and Semet, F., 2003. Ambulance location and relocation models. European journal of operational research, 147(3), pp.451-463.

Probability models for public safety

  • Larson, R.C. and Odoni, A.R., 1981. Urban operations research. This was the textbook we used to cover probability models, queueing, priority queueing, and spatial queues (the hypercube model).

Disasters, Homeland Security, and Emergency Management

Deterministic Network Interdiction

  • Smith, J.C., 2010. Basic interdiction models. Wiley Encyclopedia of Operations Research and Management Science.
  • Morton, D.P., 2011. Stochastic network interdiction. Wiley Encyclopedia of Operations Research and Management Science.

Papers presented by students in class

Papers selected for the first set of student presentations (background papers)

  • Blumstein, A., 2002. Crime Modeling. Operations Research, 50(1), pp.16-24.
  • Kaplan, E.H., 2008. Adventures in policy modeling! Operations research in the community and beyond. Omega, 36(1), pp.1-9.
  • Wright, P.D., Liberatore, M.J. and Nydick, R.L., 2006. A survey of operations research models and applications in homeland security. Interfaces, 36(6), pp.514-529.
  • Altay, N. and Green, W.G., 2006. OR/MS research in disaster operations management. European journal of operational research, 175(1), pp.475-493.
  • Simpson, N.C. and Hancock, P.G., 2009. Fifty years of operational research and emergency response. Journal of the Operational Research Society, pp.S126-S139.
  • Larson, R.C., 1987. Social justice and the psychology of queueing. Operations research, 35(6), pp.895-905.

Papers selected for the second set of student presentations (methods)

  • Ashlagi, I. and Shi, P., 2014. Improving community cohesion in school choice via correlated-lottery implementation. Operations Research, 62(6), pp.1247-1264.
  • Mandell, M.B., 1991. Modelling effectiveness-equity trade-offs in public service delivery systems. Management Science, 37(4), pp.467-482.
  • Cormican, K.J., Morton, D.P. and Wood, R.K., 1998. Stochastic network interdiction. Operations Research, 46(2), pp.184-197.
  • Brown, G.G., Carlyle, W.M., Harney, R.C., Skroch, E.M. and Wood, R.K., 2009. Interdicting a nuclear-weapons project. Operations Research, 57(4), pp.866-877.
  • Lim, C. and Smith, J.C., 2007. Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Transactions, 39(1), pp.15-26.
  • Rath, S. and Gutjahr, W.J., 2014. A math-heuristic for the warehouse location–routing problem in disaster relief. Computers & Operations Research, 42, pp.25-39.
  • Argon, N.T. and Ziya, S., 2009. Priority assignment under imperfect information on customer type identities. Manufacturing & Service Operations Management, 11(4), pp.674-693.
  • Pita, J., Jain, M., Marecki, J., Ordóñez, F., Portway, C., Tambe, M., Western, C., Paruchuri, P. and Kraus, S., 2008, May. Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track(pp. 125-132). International Foundation for Autonomous Agents and Multiagent Systems.
  • Mills, A.F., Argon, N.T. and Ziya, S., 2013. Resource-based patient prioritization in mass-casualty incidents. Manufacturing & Service Operations Management, 15(3), pp.361-377.
  • Mehrotra, A., Johnson, E.L. and Nemhauser, G.L., 1998. An optimization based heuristic for political districting. Management Science, 44(8), pp.1100-1114.
  • Koç, A. and Morton, D.P., 2014. Prioritization via stochastic optimization.Management Science, 61(3), pp.586-603.

I missed a class to attend the INFORMS Analytics meeting. I assigned two videos about public sector OR in lieu of class:

Jon Caulkins’ Omega Rho talk on crime modeling and policy

Eoin O’Malley’s talk about bike sharing and optimization (start at 3:51:53)

Blog posts I used in teaching:

We played Pandemic on the last day of class!


teaching hack: student moderators for in-class presentations

This semester I taught a PhD seminar course on Public Sector Operations Research. You can read about it here on our class blog and here on Punk Rock OR.

The students presented three research papers over the course of the semester. I created a schedule for the student speakers, and I matched each student with another student who served as the moderator. The moderator’s job was to introduce the speaker and to field questions after the talk like in department colloquiums. If there are no questions following a talk, the moderator should be ready to kick things off with a question or two.

Students often follow my lead and wait for me to ask the first question. Sometimes when a presentation ends I am too busy jotting down notes on my grading sheet to kick of the questions. Awkward silence follows. My intent was to get the students more engaged in the other presentations and to encourage them to demonstrate leadership in the classroom without assigning extra work. I would say that it worked very well. Following each presentation I had at least one student ready to ask insightful questions, which often led to other students asking interesting follow up questions. The students took ownership in the Q&A session following each presentation.

My favorite part was the unexpected consequences. I did not envision students stepping up to introduce their peers. One introduction was really sweet. I think we all got a little choked up when one student introduced her peer as a “good researcher and a great friend.”

 

 


Follow

Get every new post delivered to your Inbox.

Join 3,520 other followers