Category Archives: Uncategorized

aviation security: there and back again

This week I attended the CREATE/TSA Symposium on Aviation Security at the University of Southern California campus. Center for Risk and Economic Analysis of Terrorism Events (CREATE) and the Transportation Security Administration (TSA).

It was a nice conference attended by academics, those at government agencies (TSA, DHS, Coast Guard, etc.), and those in the private sector. It was a good mix of attendees and speakers, and no one was shy about raising interesting and provocative ideas. Many issues were discussed in the conference from multiple viewpoints, including:

  • Are we more concerned with people with a nefarious intent and no threat items or people with no bad intent but with threat items?
  • How do we even begin to characterize the deterrent effect?
  • Good security means making tradeoffs between efficiency, effectiveness, and cost.
  • Government agencies wants more collaboration with academics. Almost all non-academic speakers mentioned this.
  • What about drone security?

It was clear that aviation is still a favorite target among terrorists and that aviation security issues are still challenging. Operations research tools such as risk analysis and optimization are needed to put good ideas into action. It was nice to hear that the practitioners feel this way too. We will always have security challenges, and OR will always help us address some of these challenges.

My advisor Sheldon Jacobson talked about his work in this area, including his work with me that introduced the concept of risk-based screening (see a previous article here). Two other PhD students followed me and continued work in this area. Our work addresses on how to optimally target scarce resources at the passengers based on their risk. The models are resource allocation models that allocate screening resources to passengers statically and dynamically (in real-time). The central theme is to use limited screening resources wisely. There are inherent tradeoffs in these types of decisions: with a fixed set of resources, targeting too many resources at low-risk passengers means there are fewer resources for higher-risk passengers.

Some of the critical findings from our research include:

  • We want to match passenger risk with the right amount of security resources.
  • Risk based screening is great because it uses limited screening resources in an intelligent way. Random screening or screening everyone with all of the resources is not an intelligent use of resources (although some randomness can be effective when used intelligently – it just shouldn’t be the only way to use limited resources).
  • When risk is underestimated, high value security resources get used on high risk passengers (a good thing). Finding a threat passenger is like finding a needle in a haystack. Underestimating risk helps you make a smaller haystack.
  • When risk is overestimated, high value security resources get used on low risk passengers, which may leave fewer high value security resources available for high risk passengers. Overestimating risk prevents you from making a smaller haystack (everyone looks risky!)
  • TSA PreCheck implicitly underscreens by weeding out many of the non-risky passengers to make a smaller “haystack.” PreCheck has the potential to make the air system safer in low risk, cost-constrained environments. Side note: TSA PreCheck didn’t exist when I was a PhD student working in this area, but earlier ideas and programs were out there (e.g., trusted traveler programs).

It was nice hearing from TSA practitioners who read my papers with Sheldon and used our ideas to guide changes to policy.

Sheldon will give the long version of this talk in Arlington, Virginia on August 5 at an WINFORMS  meeting. Details are here.

You can also listen to my podcast interview with Sheldon about aviation security from 2011 here.

Special thanks to Dr. Ali Abbas (CREATE director), Kenneth Fletcher (TSA), and Jerry Booker (TSA) for organizing the conference and to Stephen Gee, Lori Beltran, and Michael Navarrete for their hard work organizing the conference. Ali promised to write an OR/MS Today article about the symposium, so stay tuned for more details. 

TSA/CREATE Symposium attendees

TSA/CREATE Symposium attendees

0221 (Large)-XL

Sheldon Jacobson talks about our aviation security research

 


punk rock OR featured on math podcast “The Other Half”

One of my blog posts about starting a fire at a gas station was featured on the math podcast The Other Half called “The Road Trip” by podcasters and professors Dr. Annie Rorem and Dr. Anna Haensch [Listen here] The podcast is about taking an optimal road trip (the Traveling Salesman Problem (TSP)) and rare risks associated with travel.

In The Road Trip, Anna and Annie look into the math that undergirds the great American summertime tradition of rolling down the windows, turning up the stereo, and touring the countryside by automobile.

Randy Olson has made the planning part easy by computing the optimal road trip across the U.S. His work to minimize the miles between landmarks in the lower 48 has been featured in the Washington Post and on Discovery News. In fact, Tracy Staedter of Discovery News can be credited not only with encouraging Olson to tackle this problem, but also with determining the list of landmarks he used. If you have a road trip you’d like to optimize, check out his code here.

And, because cars don’t run on math alone, we also consider the necessity of refueling on the road. In particular, we ask Laura McLay to weigh in on gas station safety, as she computes the conditional probability of blowing yourself up while you’re pumping gas.

The Road Trip” is n excellent podcast! Thanks to Annie and Anna for doing such a great job and for being math ambassadors. I look forward to future episodes.

The Other Half is part of ACME Science, which offers several other math and science podcasts.

One thing I would like to add to the podcast is that there are real applications of the TSP and risk analysis. We academics don’t always sit up in our ivory towers coming up with silly problems to solve that are divorced from the real world. We need to be able to characterize rare risks for numerous applications (e.g., nuclear power risks) and then communicate those risks to others for managing rare but potentially catastrophic risks. I have a few links to related blog posts at the bottom of this post. Likewise, the TSP isn’t just used to plan summer road trips. It’s used by trucking and delivery companies to plan routes, in gene sequencing, for meals-on-wheels deliveries, and in emergency response after a disaster.

A second point is that we really can optimally solve many instances of the TSP, and certainly the ones used for planning road trips. We do not always have to settle for a solution that is “good enough.” It’s true that there are more feasible solutions to many problems than there are stars in the galaxy, but we don’t solve the problems by brute force. We more intelligently solve the problems using optimization algorithms such as the simplex algorithm (a linear programming algorithm) and cutting planes (an integer programming method). Optimization algorithms traverse through the search space and find the single optimal solution among trillions of possibilities sometimes in mere seconds or minutes. It’s truly astonishing and a great contribution to basic science.

If you want more, Bill Cook is the world’s expert on the TSP and he has many examples of optimal solutions on his web site, including a TSP rout of 24,978 cities. Read Bill Cook’s (@wjcook) book and blog about the TSP for more details about the TSP’s history, algorithms, and people.

Related posts:


Life was simple before World War II. After that, we had systems.

I recently discovered one of Grace Hopper’s quotes:

Life was simple before World War II. After that, we had systems.

This reminds me of the origins of operations research in military planning in World War II. Coincidence? I think not. Operations research became a formal discipline at the same time it was desperately needed for real problems.

To be fair, systems go way back beyond World War II — I immediately thought of Ancient Rome’s bureaucracy and engineered systems of aqueducts and roads. But I appreciate what Grace Hopper implied: we continue to live in a world with increasingly complex systems that could benefit from the application of operations research.

Along the same lines, about a decade ago someone told me that the world is run on eighth grade math. I’m sure that the level of math used in many operations is embarrassing, but the financial crisis brought to light how complicated the financial system is. Likewise, other industries have followed a similar pattern of increasing complexity (and lack of transparency, but that’s a topic for another time). Knowledge of systems and math (beyond eighth grade math) is a handy tool for life.

Please share interesting stories and anecdotes about systems and your favorite use of eighth grade math.

Related posts:

 

 


just write, damn it: the dissertation edition

One of my recent blog posts entitled “just write, damn it” got a lot of hits and positive feedback. All the feedback was for just writing and none was in favor of planning first. I was surprised that my methodological and analytical readers preferred to cannonball into writing without a lot of planning.

Someone told me about an approach to writing a dissertation that was somewhere in between just writing willy nilly and planning. It’s called the One Draft PhD Dissertation [pdf] by John Carlis, a professor of Computer Science and Engineering at Minnesota. His approach is to sketch a blueprint of a dissertation by planning what will be in each paragraph and then jump in and write each of those paragraphs. He writes:

What’s my story? While writing my dissertation and, at the same time, working as a professor (yes, it was stressful), several streams of thought happily converged. I read lots about writing, and was particularly struck by the forward to the John McPhee Reader, which described his disciplined, design-before-write way of work. I read Richard Mager’s Preparing Instructional Objectives, which has this message that translates to writing: teaching (writing) is about them, the students (readers), not the teacher (author). I taught software development using Yourdon and Constantine’s “Structured Development” (Addison-Wesley, 1975). Convergence began when the strong parallels in their content struck me. By then I already believed that software should be designed and not hacked, and, coming to the same conclusion about a dissertation, I decided to try to transfer software notions to writing. Since a paragraph is a unit of development, like a software procedure, I, following McPhee, chose to design everything down to the paragraph topic sentence level before writing. And it worked!

The one draft dissertation is a 5 step process:

  1. Believe you can do it.
  2. Understand that the purpose of a dissertation is to defend your claimed contributions to your field.
  3. Write for the right audience. Start by sketching a blueprint by writing for yourself then do the formal writing for your committee.
  4. Acquire draft writing skills (paragraph topic sentences, story telling, and logic to tie paragraphs together to tell your story)
  5. Design a dissertation.

What does “draft” mean? Here a draft is a completed unit, something that you give to others for review. I do not consider small scale revising, say editing within a paragraph while leaving the structure alone, the same as re-drafting. Do not misunderstand; “one draft” does not mean that you just start from a blank slate with final words of truth and beauty rolling off your fingertips. No, producing a dissertation is work, but it is merely work, not some mystical thing… You should believe that you can produce a one-draft dissertation, because focusing on contributions allows you to first choose vocabulary, craft figures, and grow a story tree down to paragraph topic sentences, and to then, for an audience of other experts, draft, one at a time, what you have the skill to draft, namely, paragraphs.

This approach has been tested on his students. It’s similar to one of my writer’s block antidotes. When I’ve struggled with writing something new, I often dive in and plan my story paragraph by paragraph by writing topic sentences, much like in the One Draft Dissertation. It’s planning, but it feels like another way to jump in and write. Just write topic sentences, damn it.

Finally, here is the average length of a dissertation by field, courtesy of beckmw.wordpress.com.


ORiginals: a youtube channel about outstanding research in everyday language

I am very excited about a new project by Banafsheh Behzad (@banafsheh_b) and David Morrison (‏@drmorr0) promoting operations research. Their project is a YouTube channel called ORiginals: outstanding research in everyday language. I may be a bit biased because their first episode is about my research (Thanks Banafsheh and David!), but I think you will agree that the final product is gorgeous and leaves me anxious more.

Both Banafsheh and David are young OR professionals and both are already movers and shakers in our field. Banafsheh is a Professor of Information Systems at California State University, Long Beach and David is a Research Scientist and Director at a small startup. Banafsheh’s research is in healthcare and David was a finalist in the Doing Good with Good OR competition a couple of years ago. Both are very familiar with talking about OR with a societal impact, and that really comes through in their project.  Their YouTube channel is brilliant, and it is great for our field! Please subscribe (do so here) and help spread the word.

ORiginals!


what Punk Rock OR is reading

Have a wonderful Fourth of July weekend!

  1. The queen of college tours: a post by Bill Cook about the TSP and how to solve it.
  2. When maps lie: a fascinating read about geography and map literacy
  3. How analytics transformed the NBA
  4. An overpass built for a bear
  5. Finding the beauty in optimization models: visualizing MPS files by Imre Polik at SAS. I also found a 1987 paper by Irv Lustig [pdf] that does just that using old school tools.

happy belated anniversary operations research and management science!

A recent literature review turned up a reference to a classic 1981 paper by Marshall Fisher that introduced Lagrangian relaxation. I was surprised to note a 2004 publication date and upon further analysis, I noticed that the paper was republished in 2004 in a special issue of Management Science devoted to the ten most influential papers in the journal’s first 50 years. I didn’t have a blog in December 2004 when the issue came out, so I am going to wish Management Science a belated anniversary 10.5 years later.

The list of papers is pretty amazing. It includes:

  1. Linear Programming Under Uncertainty by George Dantzig
  2. Dynamic Version of the Economic Lot Size Model by Harvey M. Wagner, Thomson M. Whitin
  3. A Suggested Computation for Maximal Multi-Commodity Network Flows by L. R. Ford Jr., D. R. Fulkerson
  4. Optimal Policies for a Multi-Echelon Inventory Problem by Andrew Clark and Herbert Scarf
  5. Jobshop-like Queueing Systems by James Jackson
  6. Games with Incomplete Information Played by “Bayesian” Players, I–III: Part I. The Basic Model by John Harsanyi
  7. A New Product Growth for Model Consumer Durables by Frank Bass
  8. Models and Managers: The Concept of a Decision Calculus by John D. C. Little
  9. The Lagrangian Relaxation Method for Solving Integer Programming Problems by Marshall L. Fisher
  10. Information Distortion in a Supply Chain: The Bullwhip Effect by Hau L. Lee, V. Padmanabhan, and Seungjin Whang

Later I discovered an expanded list of the 50 most influential papers. Additionally, there are anniversary review papers in every issue of the 50th volume of Management Science, including “Improving emergency responsiveness with management science” by Linda Green and Peter Kolesar (one of my favorites). More are here.

The journal Operations Research celebrated its 50th anniversary in 2002. Volume 50, issue 1 of Operations Research is dedicated to the celebration, and it contains 33 articles that contain musings of the origins of important breakthroughs in operations research:

  1. The Genesis of “Optimal Inventory Policy” by Kenneth J. Arrow
  2. Solving Real-World Linear Programs: A Decade and More of Progress by Robert E. Bixby
  3. Crime Modeling by Alfred Blumstein
  4. Army Operations Research—Historical Perspectives and Lessons Learned by Seth Bonder
  5. Abraham Charnes and W. W. Cooper (et al.): A Brief History of a Long Collaboration in Developing Industrial Uses of Linear Programming by W. W. Cooper
  6. Linear Programming by George B. Dantzig
  7. Richard Bellman on the Birth of Dynamic Programming by Stuart Dreyfus
  8. Some Origins of Operations Research in the Health Services by Charles D. Flagle
  9. The First Linear-Programming Shoppe by Saul Gass
  10. The Origins of Traffic Theory by Denos C. Gazis
  11. Early Integer Programming by Ralph E. Gomory
  12. War and Peace: The First 25 Years of or in Great Britain by K. Brian Haley
  13. Energy Modeling for Policy Studies by William W. Hogan
  14. Learning How to Plan Production, Inventories, and Work Force by Charles C. Holt
  15. Comments on the Origin and Application of Markov Decision Processes by Ronald A. Howard
  16. Navy Operations Research by Wayne P. Hughes Jr.
  17. Interdisciplinary Meandering in Science by Samuel Karlin
  18. How Networks of Queues Came About by Jim Jackson
  19. Creating a Mathematical Theory of Computer Networks by Leonard Kleinrock
  20. Being in the Right Place at the Right Time by Harold W. Kuhn
  21. Public Sector Operations Research: A Personal Journey by Richard Larson
  22. Philip M. Morse and the Beginnings by John D. C. Little
  23. Operations Research at Arthur D. Little, Inc.: The Early Years by John F. Magee
  24. Efficient Portfolios, Sparse Matrices, and Entities: A Retrospective by Harry M. Markowitz
  25. Perspectives on the Evolution of Simulation by Richard E. Nance and Robert G. Sargent
  26. Memoirs on Highway Traffic Flow Theory in the 1950s by G. F. Newell
  27. Decision Analysis: A Personal Account of How It Got Started and Evolved by Howard Raiffa
  28. Inventory Theory by Herbert E. Scarf
  29. Game Theory and Operations Research: Some Musings 50 Years Later by Martin Shubik
  30. Analysis, Design, and Control of Queueing Systems by Shaler Stidham Jr.
  31. And Then There Were None by Harvey M. Wagner
  32. Applied Probability in Great Britain by Peter Whittle

There are other anniversary collections. In 2008, Springer published a book called “50 Years of Integer Programming, 1958 – 2008″ edited by Juenger, M., Liebling, Th.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. The book contains new material summarizing important integer programming algorithms and ideas that have been introduced over the years. The book is described as follows:

In 1958, Ralph E. Gomory transformed the field of integer programming when he published a short paper that described his cutting-plane algorithm for pure integer programs and announced that the method could be refined to give a finite algorithm for integer programming. In January of 2008, to commemorate the anniversary of Gomory’s seminal paper, a special session celebrating fifty years of integer programming was held in Aussois, France, as part of the 12th Combinatorial Optimization Workshop. This book is based on the material presented during this session.

Peter Horner wrote a 2002 article in OR/MS Today celebrating the 50th anniversary of INFORMS about the history of INFORMS and where we need to go as a field. He ends his article with this:

After 50 years of combined history, INFORMS still finds itself knee-deep in confusion. Plenty of problems have been solved… and plenty of problems remain.

What is your favorite OR/MS birthday memory?


Follow

Get every new post delivered to your Inbox.

Join 2,875 other followers