Knowledge that Transforms

Improving Operating Room, Surgery, and Anesthesiologist Scheduling Using Stochastic and Robust Optimization Efficient planning and scheduling of operating room (OR) activities is crucial for managing costs and delivering high-quality surgical care. However, this task is extremely complex for several reasons. First, it requires coordinating multiple resources, such as ORs and anesthesiologists. Second, in addition to limited OR capacity and time, there is a significant shortage of anesthesiologists required to perform surgeries. Third, surgery durations are uncertain and difficult to predict. Ignoring such uncertainty may lead to substantial overtime, idling, and surgery delays, among other schedule deficiencies. Thus, hospital managers could benefit greatly from advanced methodologies to improve OR utilization, surgical care, and quality as well as to minimize OR operational costs. In “Stochastic Optimization Approaches for an Operating Room and Anesthesiologist Scheduling Problem,” M. Y. Tsang, K. S. Shehadeh, F. E. Curtis, B.R. Hochman, and T. E. Brentjens propose computationally tractable stochastic programming and distributionally robust optimization methodologies for an integrated allocation, assignment, sequencing, and scheduling problem under uncertainty involving multiple ORs, anesthesiologists, and surgery types. Using real-world surgery data and a case study from a health system in New York, they conduct extensive experiments demonstrating the computational efficiency of the proposed methodologies, allowing for their implementation in practice. Moreover, they show the negative consequences of adopting the existing non-integrated approaches and provide valuable practical insights.

The “long tail” theory was celebrated by BusinessWeek as the biggest idea of the year 2004, soon after the book The Long Tail by Chris Anderson was published. The long tail theory calls for applying a low-budget strategy—producing a (relatively) large number of products with (relatively) low investment levels. However, some other cultural industries may tell a different story. The concentration of the most popular titles in the video game industry is growing, a phenomenon known as the blockbuster phenomenon. This phenomenon suggests that firms may adopt a high-budget strategy—producing a (relatively) small number of products with (relatively) high investment levels. In “Market Entry and Competition Under Network Effects,” Y. Feng and M. Hu analytically study the impact of a network effect on entry decisions and investment strategies (i.e., the high-budget versus low-budget strategies) adopted by competing firms based on which they further provide a theory that links the ex post sales volume concentration with the ex ante product variety in a market under network effects.

In large-scale simulation optimization, it is impossible to exhaustively simulate every choice. However, there are often inherent similarities between choices: for example, two similar sets of input settings to a simulation model can reasonably be expected to produce similar output. The information gained from simulating one choice can thus be used to infer the values of other similar choices, enabling learning more from a relatively small number of samples. The paper “Sequential Learning with a Similarity Selection Index,” by Zhou, Fu, and Ryzhov, develops a new similarity model to improve the final selection decision after all samples have been collected. The new “similarity indices” are complementary to all existing information collection procedures, which do not focus on the final decision. At the same time, the new model allows a tractable theoretical treatment of an optimal procedure, which can be efficiently approximated.

In “An Improved Approximation Algorithm for TSP,” Karlin, Klein, and Oveis Gharan design the first improvement over the classical 1.5 approximation algorithm of Christofides-Serdyukov after more than 40 years. Their algorithm first chooses a random spanning tree from the maximum entropy distribution of spanning trees with marginals equal to the optimum LP solution of TSP, and then, similar to Christofides’ algorithm, it adds the minimum cost matching on the odd degree vertices of the tree. To analyze their simple algorithms, they prove and exploit new tools from the theory of strongly Rayleigh distributions.

Managing Shipping Emission Control Areas The design of emission control areas (ECAs) is crucial for reducing global shipping emissions and protecting the environment. In “Shipping Emission Control Area Optimization Considering Carbon Emission Reduction,” Zhuge, Wang, and Zhen focus on the ECA optimization problem for sailing legs with ECAs. First, a case with a no-ECA policy and a case with the current ECA policy are discussed. Then, two new voyage-dependent ECA policies with sulfur limits, designated sailing paths, and speed limits are proposed, under which Stackelberg game models with the ECA regulator and a shipping company are developed. The authors extend the research problem from a sailing leg to a shipping network to improve the practicality of the findings. They also develop a dynamic programming-based algorithm to optimize the ECA policies for the shipping network from the perspective of the ECA regulator. The effectiveness of the proposed policies in reducing social costs is validated by numerical experiments.

This paper presents the first comprehensive study of a data-driven formulation of the distributionally robust second order stochastic dominance constrained problem (DRSSDCP) that hinges on using a type-1 Wasserstein ambiguity set. It is, furthermore, for the first time shown to be axiomatically motivated in an environment with distribution ambiguity. We formulate the DRSSDCP as a multistage robust optimization problem and further propose a tractable conservative approximation that exploits finite adaptability and a scenario-based lower bounding problem. We then propose the first exact optimization algorithm for this DRSSDCP. We illustrate how the data-driven DRSSDCP can be applied in practice on resource-allocation problems with both synthetic and real data. Our empirical results show that, with a proper adjustment of the size of the Wasserstein ball, DRSSDCP can reach acceptable out-of-sample feasibility yet still generating strictly better performance than what is achieved by the reference strategy.

In “Real-Time Spatial–Intertemporal Pricing and Relocation in a Ride-Hailing Network: Near-Optimal Policies and The Value of Dynamic Pricing,” Chen, Lei, and Jasin consider a dynamic pricing problem faced by a ride-hailing service provider who manages a fixed number of servers and serves price-sensitive customers within a network. Servers serve arriving customers by relocating from the requested origins to destinations within a certain travel time. The authors first propose a static pricing policy based on the optimal solution to a deterministic relaxation of the original stochastic problem. They show that the proposed static policy matches the best possible asymptotic performance of any static policy. The authors further propose a dynamic pricing policy that adaptively changes the prices in a way that reduces the impact of past demand randomness on the balance of future distributions of servers and customers across the network. They show that the dynamic pricing policy achieves significantly better asymptotical performance. The proposed policies and their performance guarantees are further extended to a case where the firm jointly decides the relocation of vacant servers

A Dual Perspective to the Robust Screening Problem Robust screening problem is concerned with the problem of a seller seeking a selling mechanism that maximizes the worst-case revenue obtained from a buyer whose valuation distribution lies in a certain ambiguity set. In the paper “Screening with Limited Information: A Dual Perspective”, Z. Chen, Z. Hu, and R. Wang show that strong duality holds between the problem of finding the optimal robust mechanism and a minimax pricing problem, where the adversary first chooses a worst-case distribution and then the seller decides the best posted price mechanism. The duality result connects prior literature that separately studies the primal (robust screening) and problems related to the dual and offers a unified geometric intuition in solving the problem.

The curse of dimensionality has long been one of the biggest challenges in solving large-scale simulation ranking and selection (R&S) problems. As the number of systems grows, existing approaches to R&S relying on the Bonferroni correction become increasingly conservative, rendering them overachieving in error control and consuming more computational resources than necessary. In “Bonferroni-Free and Indifference-Zone-Flexible Sequential Elimination Procedures for Ranking and Selection,” Wang, Wan, and Chen develop Bonferroni-free and indifference-zone-optional ranking and selection procedures to deliver the prescribed probabilistic guarantee without overshooting. Their approach is to conduct always valid and fully sequential hypothesis tests that enable continuous monitoring of each candidate system and control the probability of correct selection. In addition, the indifference-zone parameter becomes dispensable in their procedures; however, when provided appropriately, it could improve the procedures’ computational and statistical efficiency.

Random Consideration Set Model We operationalize a microfounded consumer choice model—the random consideration set (RCS) choice model of Manzini and Mariotti [Manzini P, Mariotti M (2014) Stochastic choice and consideration sets. Econometrica 82(3):1153–1176]—that captures the limited attention of consumers, assuming that purchases are based on fixed preference orderings with consideration sets formed from independent attentions. We provide a condition for uniquely identifying model parameters and design an efficient algorithm for model parameters estimation. We offer a greedy-like algorithm for assortment optimization, adaptable for optimal assortment subject to cardinality constraint or discovering efficient sets. We extend the model to consider random product preferences, with a 1/2 performance-guaranteed approximation algorithm. Using data from a major U.S. airline, we find that the RCS model outperforms the mixed multinomial logit model in approximately half of the markets, particularly with smaller, less varied data sets.