GUPOR: Great Unsolved Problems in O.R.

By Saul I. Gass and Arjang A. Assad

About two years ago, the program committee of the Pittsburgh INFORMS annual meeting issued us a challenge: Organize a special track of four or five sessions in which the speakers would address the "Great Unsolved Problems in O.R." We were given full freedom as to how we defined such problems and selection of speakers. Our task was twofold: Define and delimit the set of such problems (to which we gave the acronym GUPOR), and then find the best speaker to address each problem.
First, we developed a GUPOR list and possible speakers. Given that our combined purview may be limited, we also canvassed an international set of O.R. academics and practitioners for their suggestions. From these efforts, we converged to 12 problems and speakers; four three-paper sessions, plus a fifth general discussion (panel) session.

The GUPOR sessions were well attended. We were encouraged by the panel audience to communicate the material to a wider O.R. audience. This article is our attempt to do just that. As space in OR/MS Today is limited, not all of the discussion papers will appear in print. We present three of them here, with others to appear in future issues. We do, however, list all of the speakers and their topics (see sidebar), and, in some cases, provide Web sites for slides of some of the presentations. In the hope that aspects of the GUPOR set can be resolved over the next few years, we encourage readers, especially O.R. students, to take a closer look at the problem areas. The reader is also encouraged to communicate with the speakers.

We wish to thank all the speakers and Pete Horner, editor of OR/MS Today, for their assistance and cooperation.


Need and Potential for Real-Time Mixed-Integer Programming

By George L. Nemhauser

Until recently, most applications of integer programming have been to planning models where solution time is not an issue. Significant improvements in methodology, high-speed computing and data availability have made it possible to apply integer programming at the operational level for instances of modest size, where solution time may take minutes.

The next challenge is real-time mixed-integer programming (RTMIP). While such problems are prevalent in numerous application areas, the technology available for their solution is still at the research level. Shabbir Ahmed, George Nemhauser, Martin Savelsbergh of Georgia Tech, Jeff Linderoth and Ted Ralphs of Lehigh University, and Michael Ferris, Andrew Miller of the University of Wisconsin and their students are involved in an NSF-sponsored research project in this virgin area.

The successful development of real-time mixed-integer programming technology has huge potential for addressing difficult operational problems. Its tactical use may dramatically improve an airline's ability to recover from disruptions, significantly enhance the quality of radiation therapy for cancer patients, and provide huge economic benefits by increasing the agility of supply chains.

We believe that this pioneering use of cyberinfrastructure will open up new possibilities for the operations research community to exploit the computational resources, data storage capabilities and communication bandwidth that are now available for use in real-time decision-making. Moreover, the methods and frameworks developed in such research will help to shape how cyberinfrastructure is harnessed to provide decision support in a wide variety of application areas.

What do we mean by RTMIP beyond obtaining solutions very rapidly? The first key point is that the output of an integer programming algorithm is not just a solution but, in addition, a certificate of optimality. More broadly interpreted, a "bound certificate" is provided with the solution which says that this solution is provably within x% of optimality. Of course, if x = 0, then the bound certificate is an optimality certificate. This requirement distinguishes integer programming from heuristics like greedy algorithms and local search, which can be very fast and possibly have finite worst case bounds, but do not provide tight optimality bounds on individual instances. Tight bounds are very important in many applications where provably good solutions are essential to the bottom line.

A second key point is solution time. Our definition of real-time can be seconds, minutes or hours depending on the requirement of the application, but we are assuming that this time constraint is not close to being satisfied with current methodology for the applications of interest. Since orders of magnitude improvements in IP methodology in general are unlikely to be achievable in the next decade, it is necessary to provide a framework for which success may be measured.

The framework we are studying relates to sensitivity analysis in MIP. We suppose that there is sufficient time to solve a core instance or a pool of such instances and also to gather other information that we may need such as dual solutions and search trees. We call this the preprocessing phase. But then it will be necessary to solve one or more slightly perturbed problem(s) from the pool in real time. Note that this framework differentiates RTMIP from existing frameworks for dealing with uncertainty, such as robust or stochastic optimization, since we are interested in solving a particular instance once its data is known rather than obtaining one solution that will be good for a large family of instances. In fact, a solution obtained by robust optimization may be useful in the preprocessing phase since it, in addition to the solution of the deterministic core problem, can provide a bound and good starting point for further exploration.

To give an idea of one possible approach for dealing with such RTMIP problems, considerobjective coefficient perturbations on binary variables in the MIP, which are not known in advance. In the preprocessing phase, we solve a sequence of problems to generate a number of feasible solutions that "cover" both 0 and 1 values of the binary components of the decision vector. These solutions can then be used to construct an (inner) approximation of the set of cost perturbations over which optimality of the current optimal solution is guaranteed to be preserved. Once the actual cost perturbation is revealed, we can then check whether the current solution is still optimal, otherwise report the best of the collected "covering" solutions.

Of fundamental importance is the ability to measure performance in some reasonable way. An obvious measure of performance is to compare the solution that was obtained under time constraints with that which would have been obtained with more time (the "optimal|" solution). Jeff Linderoth has appropriately named this quantity the "Price of Impatience."



George L. Nemhauser (george.nemhauser@isye.gatech.edu) is a professor in the Department of Industrial and Systems Engineering, Georgia Institute of Technology.

References



- M. Ball, C. Barnhart, G. Nemhauser and A. Odoni, 2006, "Managing air traffic and airline operations for schedule reliability," in "Handbook of Transportation," C. Barnhart and G. Laporte, eds., Elsevier.
- M. C. Ferris, R.R. Meyer, and W. D'Souza, 2002, "Radiation treatment planning: Mixed integer programming formulations and approaches," Optimization Technical Report 02-08, Computer Sciences Department, University of Wisconsin, Madison, Wis.

Increase in Flight Delays Calls for Better Air Traffic Management

By Michael O. Ball

In this essay, I identify and describe three operations research problem areas that both pose very significant research challenges and whose solution would substantially advance the operations of the worldwide air transportation system. Air transportation has a long and significant historical link to operations research and its growth. In particular, the air crew scheduling and fleet planning problems represent early successful application domains for integer programming (IP) and motivated early IP research. A second, very vibrant field of study within operations research, revenue management, was literally invented to address pricing issues arising within the airline industry.

In spite of, or perhaps because of, this long connection between operations research and planning problems faced by airlines, my focus in this essay is on a different problem domain within air transportation, namely, air traffic management (ATM). ATM problems have to do with the manner in which air transportation operations are managed on a day-to-day basis. ATM technology enables the vast air transportation system to operate safely and efficiently in spite of the significant variability in system demand and capacity due to weather, equipment status and a variety of disruptive events. The growth of air transportation delays in recent years points to both the possible shortcomings of current ATM systems and to the importance of research geared toward significant ATM advancements.

Before defining the research problem, it is instructive to consider some fundamental differences between air transportation systems and the possible more familiar domain of road transportation:
- Airspace has a third dimension. This provides a higher degree of flexibility in the manner in which traffic is controlled and managed and the airspace is organized.


- Airplanes cannot stop in mid-air. This vastly increases the burden on ATM systems to keep airspace congestion within certain limits.


- Safety is more critical because of high volume vehicles and the high fatality likelihood in the event of crashes. Insuring extremely high levels of safety is essential to the viability of large-scale commercial air transportation.


- ATM systems provide a greater degree of system-wide control. ATM systems represent a sophisticated control structure totally absent from road networks.


- Airlines provide an intermediate level of control. While the typical users of the road system are vehicles operated by non-coordinated individuals, a large portion of airspace demand involves flights under the control of anumber of airlines.

Significant advancements in the overall performance of ATM systems will no doubt require:
- expansion and improvements to the basic infrastructure, e.g., the building of additional runways and airports;


- enhancement to underlying ATM technology, e.g., such technology might reduce aircraft separation requirements, provide for satellite-based navigation, allow vertical takeoff, provide for pilot/aircraft centric control architectures, etc; and


- new approaches for airspace system design, operation and analysis.

Operations research should play a very fundamental role in airspace system design, operation and analysis. Following are three research challenges in this area I consider most critical.

Dynamic, stochastic optimization models: ATM must deal with high degrees of uncertainty. The most obvious source of uncertainty is the variability in the capacity of system elements due to weather conditions. Further, since ATM problems include short-term to real-time operational decision-making, effective decision-support models must be able to react dynamically to changing conditions and updated information, e.g., weather forecasts.

At the same time, problem sizes are very large with tens of thousands of flights operating per day. There is a significant body of work within the general domain of stochastic programming [4], and a growing literature on stochastic models for ATM [2], [7]. However, this has not yet developed to the extent that there has been any significant impact on ATM practice. Approximate dynamic programming has been successfully applied in other transportation domains [6], suggesting such approaches may hold promise here. Other research domains that may provide a useful basis here include Markov decision processes and control.

Designing and managing complex systems with both technical and economic controls: ATM decision makers include both the agencies charged with managing national airspace systems, e.g., the Federal Aviation Administration (FAA) in the United States, and flight operators, which include the airlines. Further, each of these individual entities has its own complex distributed decision-making hierarchy. The presence of multiple entities and organizational structures suggests the need for ATM distributed decision-making and control strategies. While building distributed architectures in general represents a challenge, it can be argued that such architectures have been successfully deployed in other domains, e.g., military operations.

On the other hand, the ATM setting has another very critical factor, namely, that the second level of managers/controllers, the flight operators, consist of competing economic entities. Thus, when one considers possible ATM architectures, the underlying implicit incentive structure must be taken into account. For example, when one observes very high levels of congestion at an airport coexisting with high frequencies of scheduled flights between certain city-pairs, it seems clear that a "system optimal" solution would reduce the frequency of service in certain markets in exchange for a reduction in delays. However, market forces together with the lack of natural incentives to reduce congestion in a setting where multiple users all contribute to the problem can lead to individual airline scheduling behavior that is detrimental to overall system performance.

On a more operational level, system performance can be enhanced when individual users provide information on the status of their flights and their intentions, e.g., to cancel flights. Yet, providing such information can be costly or, depending on how it is distributed and/or used, it could provide advantage to the provider's competitors. In such cases, it is important that resource allocation or other policies provide incentives for users to provide important information.

These examples all point to the need to consider "economic controls," such as congestion pricing, and, more broadly, the overall incentive structure in designing distributed decision-making and control strategies. The literature on the design of market mechanisms is certainly quite relevant here [5], including some recent work within the domain of ATM [1]. On the operational level, the work on collaborative decision-making in ATM provides a solid basis for further research [9], [10].

Modeling safety: As mentioned previously, extremely high levels of safety are fundamental to the viability of air transportation. At the same time, there are few examples of the broad use of models to support safety-related decision-making in ATM. As a result, ad-hoc arguments sometimes dominate such decision-making. Many cases have arisen when concerns for safety have blocked or delayed the deployment of efficiency-improving ATM systems. In such instances, it can be difficult to differentiate between true concerns for safety and underlying political motivations. Thus, high-quality safety models are needed in order to infuse objectivity into politically motivated discussions.

While it can be very challenging to quantify safety, an effective approach to modeling safety is to measure a system metric whose value is correlated with the system safety level. One can then evaluate this metric for an existing system and show that a proposed system has an increased value, implying the new system has at least as high a level of safety. Of course, any time a change is made there is always the possibility of unseen threats to safety; thus, no approach is foolproof. Examples of the application of the approach outlined in aviation include [3], [8], and [11].



Michael O. Ball (mball@rhsmith.umd.edu) is a professor at the Robert H Smith School of Business & Institute for Systems Research, University of Maryland.

References



- Ball, M.O., G. Donohue and K. Hoffman, 2005, "Auctions for the safe, efficient and equitable allocation of airspace system resources, in "Combinatorial Auctions" [5], pp. 507-538.
- Ball, M.O., Hoffman, R., Odoni, A. and Rifkin, R., 2003, "A stochastic integer program with dual network structure and its application to the ground-holding problem," Operations Research, Vol. 51, pp. 167-171.
- Barnett, A., 2000, "Free-flight and en route air safety: A first-order analysis," Operations Research, Vol. 48, pp. 833-845.
- Birge, J. and F. Louveaux, 1997, "Introduction to Stochastic Programming," Springer, New York.
- Cramton, P., Y. Shoham, and R. Steinberg, 2005, "Combinatorial Auctions," MIT Press, Cambridge, MA.
- Powell, W.B., J. Shapiro and H. P. Simao, 2002, "An adaptive, dynamic programming algorithm for the heterogeneous resource allocation problem," Transportation Science, Vol. 36, pp. 231-249.
- Richetta, O. and A. Odoni, 1993, "Solving optimally the static ground-holding policy problem in air traffic control," Transportation Science, Vol. 27, pp. 228-238.
- Thompson, S. and S. Bussolari, 2003, "Analysis of terminal separation standards and radar performance," in Proceedings of 5th USA/Europe Air Traffic Management R&D; Seminar, available at http://atm2003.eurocontrol.fr/papers_calendar.
- Vossen, T. and Ball, M.O., 2006, "Optimization and mediated bartering models for ground delay programs," Naval Research Logistics, Vol. 53, pp. 75-90.
- Wambsganss, M., 1996, "Collaborative decision-making through dynamic information transfer," Air Traffic Control Quarterly, Vol. 4, pp. 107-123.
- Willemain, Thomas R., 2003, "Factors Influencing Blind Conflict Risk in En Route Sectors Under Free-Flight Conditions," Transportation Science, Vol. 37, pp. 457-470.

Responsibility of O.R. for Disaster Management

By Martin K. Starr

Disasters occur in three ways: (1) by intentional malevolence; (2) by human errors and technological failures; and (3) by acts of nature (e.g., hurricanes, earthquakes, and tsunamis). Such regional disasters often trigger additional catastrophes such as long-term power outages, buildings destroyed and serious dam destruction. This paper starts to examine how O.R. models can begin to structure the three types of situations before they occur, during emergency periods and after their occurrence.

Our emphasis in this paper is on before scenarios. Avoiding catastrophes removes severe penalties incurred during and after their occurrence. This means that substantial investments in detection and prevention of disasters (all three kinds plus some variations) can be justified. Detection and prevention of events such as the Oklahoma City bombing of the Murrah Federal Building (April 19, 1995), the suicide bombing of the World Trade Center (Sept. 11, 2001), the breaching of levies during hurricane Katrina (Oct. 19, 2005) and the explosion of NASA space flight STS-51-L, the Challenger disaster (Jan. 28, 1986), would have saved billions of dollars and many priceless lives.

It is surprising that major efforts have not been devoted to detecting and preventing impending calamities. It might be sociologically useful to study why this is so, but that is a purpose beyond the intentions of this paper. O.R. practitioners are not the only scientists who have not responded to the potential savings of even limited success in these domains of colossal tragedy. There are examples of studies intended to detect and prevent terrorist acts, hurricanes, shuttle failures and tornadoes. The primary goal of this paper is to note and comment upon some work that has been done, and to point to successes and failures.

Other variants of disasters can be listed. Mainly, these are combinations of classes 1, 2 and 3, previously cited. For example, bird flu pandemics are the result of acts of nature in conjunction with human errors. The anthrax attacks on U.S. senators in Washington, D.C., that followed 9/11/01 were malevolent acts of terror. Human error can also be blamed in preventing future attacks since the original assaults remain unsolved.

Among the worst disaster variants are the 40,000 auto fatalities annually in the United States and the 66,000 that occur annually in Europe. Major causes are human errors associated with falling asleep, alcohol and drugs. There are also technological failures from tire failures, skids and rollovers. Acts of nature can play a part. Weather conditions may be crucial. Costs of even partial prevention arecompared to the staggering benefits obtained by reducing the 100,000 fatalities and 40 million injuries. Property damage reduction will save billions of dollars in the United States, Europe and worldwide.

What role has O.R. played in gaining control over the above situations? While there are some studies in each of these areas, the effort mounted is not proportional to the penalties of unsolved problems. That is why the great unsolved problems in the areas of detecting and preventing disasters (attributed to terror, errors and acts of nature) need to be addressed. This is not to say that great benefits do not also accrue to improvement in the response to emergencies during a disaster and remedial treatment after a disaster.

However, car and road design issues, critical to disaster prevention, are considered to be the province of engineers. That point of view will probably continue until O.R. participates with, or without, invitation in the determination of car and road design. The many alternatives, such as the viability of road-guidance by computer, insurance and health-care considerations, which are crucial in the after stages of car disasters, should be by analyzed by O.R. whole system models that include the three stages of before, during (emergency services) and after.

Hurricane prevention or reduction of storm intensity may become a primary "initiative" for O.R. A clear model of cost/benefit is required to move science, engineering and society in this direction. Any one of three recent hurricanes — Andrew, Katrina and Rita — provide justification for research to reduce the devastating effects in human suffering and costs. Perhaps supply chain protection will provide the economic catalyst to overcome political and legal roadblocks.

Can prevention really be accomplished? Nobel Prize winner Irving Langmuir and his colleague, Bernard Vonnegut, both of GE Labs, believed so. They devoted much time researching cloud seeding to decrease the power of hurricanes. Langmuir's notebooks reveal that he was convinced that his results were significant and worthy of further research for rain in drought areas and hurricane abatement, as well.

Unexpected legal and political issues persuaded GE to drop the line of inquiry concerning weather controls. There are other indications that legal issues dealing with weather modification are in play. Dyn-O-Mat's super-desiccant experiments with environmental absorbent technologies were widely reported as being successful. The continued experiments were aborted without any explanation.

Early deflection of incipient storms has been briefly examined with promising results, but O.R. has not been used to build the case for further work. The same situation applies to various theories about greening the African coast where storms are born. Other ideas also exist about water temperature reduction and surface manipulations which might reduce the severity of storms.

Perhaps some of this work would apply to other natural disasters. Various organizations are working on anomaly detection as a means of discovering terrorist plots. A variety of new technologies are promising in application to air travel security systems. Predictive maintenance methodologies have potential application to incipient failures of technology and security. To achieve significant accomplishments, traditional scientists need an O.R. partner to show the benefits of working on unconventional projects.



Martin K. Starr (mstarr@rollins.edu) is professor emeritus of Operations Management and Management Science, Crummer Graduate School of Business, Rollins College.

References



- Perrow, Charles, 1999, "Normal Accidents: Living With High-Risk Technologies", Princeton, N.J., Princeton University Press.
- Reason, James, 1990, "Human Error," Cambridge, U.K., Cambridge University Press.
- Starr, Martin K., 2004, "Safety and Security: An International Imperative for Production and Operations Management Applications in a Post 9/11 World," Rollins Business Journal, Vol. 3, No. 2, pp. 3-4.
- Yu, Gang and Xiangtong Qi, 2004, "Disruption Management Framework, Models and Applications," Singapore and River Edge, N.J., World Scientific Publishing Co. Pte. Ltd.





The GUPOR Sessions


Session I
"Representing Uncertainty in Decision Support," Harvey J. Greenberg, Mathematics Department, University of Colorado at Denver, PO Box 173364, Denver, CO 80217-3364

www-math.cudenver.edu/~hgreenbe/UncertaintyInforms06.pdf

"Large-Scale Dynamic Stochastic Programming," John R. Birge, University of Chicago, Graduate School of Business, 5807 South Woodlawn Avenue, Chicago, IL 60637

http://faculty.chicagogsb.edu/john.birge/research/birge_informs_pgh_largescale_unsolved_2006nov.pdf

"Computational Global Optimization," János D. Pintér, Pintér Consulting Services, 129 Glenforest Drive, Halifax, Nova Scotia, Canada B3M IJ2

Session II
"Need and Potential for Real-time Integer Programming," George L. Nemhauser, Dept of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205

"Problems in Air Transportation," Michael O. Ball, Robert H. Smith School of Business, University of Maryland, College Park, MD 20742

"Recent Results and Unsolved Problems in Computational Biology," James B. Orlin, Operations Research Center, Massachusetts Institute of Technology, E40-147, Cambridge, MA 02139

http://web.mit.edu/jorlin/www/talks.html

Session III
"Responsibility of O.R. for Disaster Management," Martin Starr, Management Science Department, Crummer Graduate School of Business, Rollins College in Winter Park, 1000 Holt Ave., Winter Park, FL 32789

"Can There be a Unique O.R. Paradigm?" Heiner Müller-Merbach, Technische Universität Kaiserlauten, Postfach 30 49, D-67653,Kaiserlauten, Germany

"Are We There Yet? The Marriage between Simulation and Optimization," Michael C. Fu, Robert H. Smith School of Business, University of Maryland, College Park, MD 20742

Session IV
"The Challenge of OR/MS in Healthcare Delivery," Ronald L. Rardin, Department of Industrial Engineering, Director of Academic Operations for the Regenstrief Center for Healthcare Engineering, Purdue University, West Lafayette, IN 47907-2022

"Great Unsolved Problems in Inventory Theory," Paul H. Zipkin, Fuqua School of Business, Duke University, Durham, NC 27708-0120

"Great Unsolved Problems in Revenue Management," Garrett van Ryzin, Graduate School of Business, Columbia University, 3022 Broadway, NY, NY 10027

Session V
"Panel discussion: Resolution of Great Unsolved Problems in O.R." Panelists: Arjang A. Assad, Saul I. Gass, Harvey Greenberg, Heiner Müller-Merbach, George Nemhauser