In This Issue
Outpatient Scheduling in a Hospital
Outpatient services account for more than four-fifths of patient care in the United States, and most patients access these services via appointment scheduling. Because of the possibility of patient no-shows, healthcare providers usually rely on overbooking. If very few patients show up, it will leave hospital resources underutilized, whereas too many showing up will increase patient wait times and increase staff overtime costs. In a hospital or a network of clinics, where patients could enter and exit at various stations and have complex flow patterns, scheduling becomes even more of a challenge. In “Coordinated Patient Appointment Scheduling for a Multistation Healthcare Network,” Wang, Muthuraman, and Morrice propose a multistation network model that carefully strikes a balance between assumptions that allow tractability and assumptions that disallow real-world adoption. Given the complexity involved in solving the model, they explore a sequence of approximations and find one that offers a significant computational advantage.
Treatment of Infectious Diseases with Drug Resistance
Antimicrobial use contributes to the growing public health challenge of infectious diseases that are resistant to all but a few remaining treatments via natural selection. When few treatment options remain, should the last effective treatment be reserved for controlling larger outbreaks in the future? In “Dynamics of Drug Resistance: Optimal Control of an Infectious Disease,” Chehrazi, Cipriano, and Enns formulate this important policy question as a control problem with two state variables—disease prevalence and the level of treatment resistance—for an established family of SIS infectious disease models with resistance. They prove that when the disease transmission rate is constant, it is optimal to treat everyone until the level of resistance is so high that it is no longer economical to treat anyone. Public health policies and social distancing can cause a nonconstant disease transmission rate; in these cases, it may be optimal to preserve the drug for relatively larger outbreaks or to use the drug to treat some, but not all, infected individuals.
Designing Product Lines with Modern Optimization
Which products should a firm offer based on its customers' preferences? This is the question posed in the problem of product line design, a well-studied and notoriously difficult problem that is central in marketing science. In “Exact First-Choice Product Line Optimization,” Bertsimas and Mišić propose a new approach for solving this problem when segments of customers choose products according to a ranking. They propose a new mixed-integer optimization model of the problem, which they show to be tighter than prior formulations, and a solution approach based on Benders decomposition, which exploits the surprising fact that the subproblem can be solved efficiently for both integer and fractional master solutions. A well-known product line instance based on a conjoint data set of over 3,000 products and 300 respondents, which required a week of computation time to solve in prior work, is solved by the authors' approach in just over 10 minutes.
Learning Fast and Slow When There Is Not Enough Time but Too Many Choices
How do we collect and process information before we make a decision? Although this question is very fundamental, a compelling model based on information theory, which incorporates limited time, attention, and cognitive capabilities of consumers, has only been developed in recent years. Because information is costly and attention is limited, consumers trade-off the value of better information against its cost and make their final product choices based on imperfect information. In “Consumer Choice Under Limited Attention When Alternatives Have Different Information Costs,” Huettner, Boyacı, and Akçay capture the idea that learning about some product is easier than about others. They show that this has significant impact on consumer choice and hence on optimal assortment and information provision, and how market share data can be used to infer the utility of customers with limited attention using methods from logit models.
Planning for Public Health Emergencies
Public health security—achieved by effectively preventing, detecting, and responding to events that affect public health, such as bioterrorism, disasters, and naturally occurring disease outbreaks—is a key aspect of national security. However, effective public health preparedness depends on answering largely unanswerable questions such as determining the chance of a bioterror attack in the United States over a given time horizon, or chance of an anthrax attack, or the location and magnitude of such an attack. In “Public Health Preparedness: Answering (Largely Unanswerable) Questions with Operations Research—The 2016–2017 Philip McCord Morse Lecture,” Brandeau describes the important role that OR-based analyses can play in providing insight into complex public health preparedness planning problems, thereby supporting good decisions. The author presents three examples from her work: logistics of response to an anthrax attack, prepositioning of medical countermeasures for anthrax, and stockpiling decisions for the United States' Strategic National Stockpile.
Dynamic Mechanism Design with Budget-Constrained Buyers Under Limited Commitment
Motivated by modern display advertising auction markets, in “Dynamic Mechanism Design with Budget Constrained Buyers under Limited Commitment,” Balseiro, Besbes, and Weintraub study a novel dynamic mechanism design problem with two notable features. First, buyers making repeated purchases of independent items face a cumulative budget constraint. Second, the seller can commit to the rules of the current auction but not of future auctions. The authors show that the classical Myersonian approach that leverages the envelope theorem fails in a discrete time model. However, they establish that this approach is recovered in a “fluid” continuous time model, leading to the characterization of an approximately optimal dynamic mechanism. This yields concrete prescriptions for a profit-maximizing seller who should allocate based on “modified virtual values,” capturing the dynamics introduced by budgets. Further, the mechanism balances the seller's desire to extract buyers' budgets by selling as few items as possible and the buyers' threat of not participating.
How to Choose Between Exponentially Many Strategies
In “Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games,” Hellerstein, Lidbetter, and Pirutinsky consider zero-sum games between a minimizer and a maximizer, where the number of pure strategies of the minimizer is exponential in the number of pure strategies of the maximizer. Such games are frequent in the search-games literature. Solving them with standard algorithms typically takes exponential time. The authors show how to compute (approximate) solutions in polynomial time, provided that there is a polynomial time (approximate) algorithm solving the best-response problem: given a mixed (randomized) strategy of the maximizer, what is a best response of the minimizer? The paper presents both a learning approach using weight updates, and an approach of solely theoretical interest based on the ellipsoid algorithm. The learning approach performs well experimentally compared with approaches in the literature. The results are applied to obtain new algorithms for solving specific search games.
Optimal Pricing in a Ride-Sharing Network
Motivated by the prevalence of ride-sharing platforms, in “Spatial Pricing in Ride-Sharing Networks,” Bimpikis, Candogan, and Saban explore the impact of the demand pattern for rides across a network's locations on a platform's optimal pricing and compensation policy, profits, and consumer surplus. They explicitly account for the pricing problem's spatial dimension and the fact that the drivers endogenously determine whether and where to provide service. Their first contribution is to develop a tractable model to study a platform operating on a network of locations that may differ in both the size of their potential demand and the destination preferences of riders. Second, they provide a characterization of the platform's optimal policy and identify “balancedness” of the demand pattern as a property that captures the profit potential of a given network. Finally, they discuss the benefits and limitations of a number of alternative pricing and compensation schemes.
Dynamic Development, Launch, and Post-Launch Strategies for a Network of Customers
Network products such as mobile apps and computer games are of paramount importance, as these products constitute a large value in today's economy. Motivated by this observation, in “Optimal Dynamic Product Development and Launch for a Network of Customers,” Sunar, Birge, and Vitavasiri consider a firm that dynamically chooses its effort to develop a product for a network of customers represented by a connected graph. The technology of the product evolves as a stochastic process that depends on the firm's dynamic efforts over time. In addition to dynamically choosing its development effort, the firm chooses when to launch or abandon the product. If the firm launches the product, the firm also chooses a selling price, a promotional price, and a target customer to offer promotion. Once the target customer adopts the product, the product diffuses over the customer network based on the topology of the graph and the selling price. The paper provides the explicit solution of the firm's jointly optimal development, launch, and post-launch strategies for any connected network, and introduces metrics that allow ordering customer networks with respect to the firm's optimal expected discounted profit, launch technology, and consumer surplus.
Bidirectional Traffic Scheduling in Artificial Waterways
In “Ship Traffic Optimization for the Kiel Canal,” Lübbecke, Lübbecke, and Möhring develop graph-based models and algorithms to solve a practical traffic scheduling problem. It arises in the operational planning of bidirectional traffic where vehicles can pass each other only at dedicated locations—for example, vessels that navigate narrow waterways. The authors provide decision support for the particular planning problem at the German Kiel Canal, the world's most frequented artificial waterway, but their findings generalize, for example, to scheduling trains on a stretch of single tracks or collision-free routing of robot arms. Mathematically, these planning problems expose a rich combinatorial structure. Ideas from quickest path algorithms and job-shop scheduling are integrated to handle all practical constraints at a high level of detail. The modelling does not need any time or space discretization. The software tool developed during the study was also used to assess strategic options of enlarging the canal.
Long-term Planning Problems Revisited: A Scalable Solution Scheme for Multi-Stage Robust Optimization Problems
In the paper “Robust Dual Dynamic Programming,” Georghiou, Tsoukalas, and Wiesemann propose a novel solution scheme for addressing planning problems with long horizons. Such problems can be formulated as multistage robust optimization problems. The proposed method takes advantage of the decomposable nature of these problems by bounding the costs arising in the future stages through lower and upper cost-to-go functions. The proposed scheme does not require a relatively complete recourse, and it offers deterministic upper and lower bounds throughout the execution of the algorithm. The promising performance of the algorithm is shown in a stylized inventory-management problem in which the proposed algorithm achieved the optimal solution in problem instances with 100 time stages in a few minutes.
Disruption Risk Mitigation in Supply Chains — The Risk Exposure Index Revisited
In recent years, supply chains are more prone to disruptions. The impact on performance depends on the system's ability to discover and then recover after the disruption has occurred. In “Disruption Risk Mitigation in Supply Chains: The Risk Exposure Index Revisited,” Gao, Simchi-Levi, Teo, and Yan propose a new method to integrate probabilistic assessment of disruption risks into the Risk Exposure Index (REI) approach proposed previously by Simchi-Levi et al. and measure supply chain resiliency by analyzing the worst-case CVaR (WCVaR) of total lost sales under disruptions. The authors show that the optimal strategic inventory positioning strategy in this model can be fully characterized by a conic program. The optimal primal and dual solutions to the conic program can be used to shed light on comparative statics in the supply chain risk mitigation problem. This information can help supply chain risk managers focus their mitigation efforts on critical suppliers and/or installations that will have greater impact on the performance of the supply chain when disrupted.
Hepatitis C Treatment Prioritization in Prisons Under Resource Constraints
Hepatitis C virus (HCV) prevalence in prison systems is about 10 times higher than in the community. As such, prison systems offer a unique opportunity to control the HCV epidemic. New HCV-treatment drugs are very effective, but providing treatment to all inmates is prohibitively expensive unless prices fall. Current practice is to prioritize treatment based on disease severity and puts less emphasis on other factors such as the remaining sentence length and injection drug use behavior. In “Prioritizing Hepatitis C Treatment in U.S. Prisons,” Ayer, Zhang, Bonifonte, Spaulding, and Chhatwal analyze optimal approaches for treatment prioritization under resource constraints by developing a restless bandit modeling framework. They present an easy-to-implement closed-form index policy to support hepatitis C treatment prioritization decisions in U.S. prisons. They also test their proposed policy using a detailed, realistic agent-based simulation model and shed light on several controversial health policy decisions related to hepatitis C treatment prioritization.
A Novel Class of Gaussian Random Fields for Simulation Metamodeling Using Gaussian Process Regression
In operations research, stochastic simulations are often used to model complex systems. Simulation runs can be time-consuming to execute, especially when there are many scenarios that need to be evaluated, or the scenarios to be evaluated cannot be anticipated in advance of when the results are needed. Simulation metamodels are statistical models built using the simulation output at a small set of scenarios and can be used to predict the value of the response surface for any scenario, simulated or not. Thus, simulation metamodels can provide support for real-time decision making and sensitivity analysis. Gaussian process (GP) regression is a popular technique for metamodeling; GP regression represents the unknown response surface as the realization of a Gaussian random field (GRF). Specifying the proper GRF is crucial for effective metamodeling. In “Generalized Integrated Brownian Fields for Simulation Metamodeling,” Salemi, Staum, and Nelson propose a novel class of GRFs called generalized integrated Brownian fields. These GRFs have several desirable properties, including differentiability that can be customized in each coordinate direction, no mean reversion, and the Markov property. These properties are shown to lead to better metamodels than those obtained from standard choices for the GRF.
Operations Research Techniques for Analyzing Hyperlink and Social Networks
There is a growing interest in the analysis of networks found in the World Wide Web and in social networks. A common feature of these networks is that the finite-state Markov chain modeling the influence relation between nodes typically has several (nearly) ergodic classes. In “Analysis of Markov Influence Graphs,” Berkhout and Heidergott introduce a new decomposition algorithm for Markov chains that allows to split the graph of the Markov chain into subgraphs such that the connectivity of the chain—measured by the Kemeny constant—is maximally decreased. In other words, the authors show how the structure dormant in a nearly decomposable chain can be brought to light. The authors present applications to influence ranking in social networks, decomposition of a social network into subnetworks, and cluster analysis.
