Knowledge that Transforms

We study an inventory system under periodic review when excess demand is lost. It is known (Huh et al. 2009) that the best base-stock policy is asymptotically optimal as the lost-sales penalty cost parameter grows. We now show that this result is robust in the following sense: Consider the base-stock level which is optimal in a backordering system (with a per-unit-per-period backordering cost) in which the backorder cost parameter is a function of the lost-sales parameter in the original system. Then there is a large family of functions (mapping the lost-sales cost parameter to the backorder cost parameter) such that the resulting base-stock policy is asymptotically optimal. We also demonstrate the robustness phenomenon through a second result. We consider the base-stock level which is optimal in a backordering system in which a unit of backorder is charged a penalty cost only once (such a system has been studied by Rosling). We show that this base-stock policy is also asymptotically optimal. Furthermore, we show that a modification suggested by Archibald of this base-stock level also results in an asymptotically optimal policy. Finally, we numerically test the performance of this heuristic policy for a wide spectrum of values for the lost-sales penalty cost parameter and illustrate the superior performance of Archibald's method.

Opaque selling has been widely adopted by service providers in the travel industry to sell off leftover capacity under stochastic demand. We consider a two-stage model to study the impact of different selling mechanisms, posted price (PP) versus name-your-own-price (NYOP), of an opaque reseller on competing service providers who face forward-looking customers. We find that in this environment, providers prefer that the opaque reseller uses a posted price instead of a bidding model. This is because the ability to set retail prices is critical for extracting surplus from customers who wait to purchase from the reseller. Such surplus extraction enables providers to set high prices for advance sales and obtain high profits. The dominance of PP over NYOP disappears, however, when competition between sellers is minimal or absent. We extend our model to multiple opaque resellers who compete in selling off last-minute capacity for service providers and find that our main insights continue to hold with differentiated resellers. Despite providers' preference in favor of PP, there are circumstances under which the opaque reseller earns higher profits under NYOP. Leisure customers might also prefer the bidding mechanism, which allows them to retain some surplus. This can help explain the rapid growth of the NYOP model over the last decade. Our findings are consistent with the evolution of opaque selling in the travel industry, and in particular, the recent trend towards more published price sales for opaque products.

A natural optimization model that formulates many online resource allocation problems is the online linear programming (LP) problem in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In such a model, a decision variable has to be set each time a column is revealed without observing the future inputs, and the goal is to maximize the overall objective function. In this paper, we propose a near-optimal algorithm for this general class of online problems under the assumptions of random order of arrival and some mild conditions on the size of the LP right-hand-side input. Specifically, our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from the revealed columns in the previous period are used to determine the sequential decisions in the current period. Through dynamic learning, the competitiveness of our algorithm improves over the past study of the same problem. We also present a worst case example showing that the performance of our algorithm is near optimal.

When we use simulation to estimate the performance of a stochastic system, the simulation often contains input models that were estimated from real-world data; therefore, there is both simulation and input uncertainty in the performance estimates. In this paper, we provide a method to measure the overall uncertainty while simultaneously reducing the influence of simulation estimation error due to output variability. To reach this goal, a Bayesian framework is introduced. We use a Bayesian posterior for the input-model parameters, conditional on the real-world data, to quantify the input-parameter uncertainty; we propagate this uncertainty to the output mean using a Gaussian process posterior distribution for the simulation response as a function of the input-model parameters, conditional on a set of simulation experiments. We summarize overall uncertainty via a credible interval for the mean. Our framework is fully Bayesian, makes more effective use of the simulation budget than other Bayesian approaches in the stochastic simulation literature, and is supported with both theoretical analysis and an empirical study. We also make clear how to interpret our credible interval and why it is distinctly different from the confidence intervals for input uncertainty obtained in other papers.

This paper studies the problem of simultaneously locating trauma centers and helicopters. The standard approach to locating helicopters involves the use of helicopter busy fractions to model the random availability of helicopters. However, busy fractions cannot be estimated a priori in our problem because the demand for each helicopter cannot be determined until the trauma center locations are selected. To overcome this challenge, we endogenize the computation of busy fractions within an optimization problem. The resulting formulation has nonconvex bilinear terms in the objective, for which we develop an integrated method that iteratively solves a sequence of problem relaxations and restrictions. Specifically, we devise a specialized algorithm, called the shifting quadratic envelopes algorithm, that (1) generates tighter outer approximations than linear McCormick envelopes and (2) outperforms a Benders-like cut generation scheme. We apply our integrated method to the design of a nationwide trauma care system in Korea. By running a trace-based simulation on a full year of patient data, we find that the solutions generated by our model outperform several benchmark heuristics by up to 20%, as measured by an industry-standard metric: the proportion of patients successfully transported to a care facility within one hour. Our results have helped the Korean government to plan its nationwide trauma care system. More generally, our method can be applied to a class of optimization problems that aim to find the locations of both fixed and mobile servers when service needs to be carried out within a certain time threshold.

Distributionally robust optimization is a paradigm for decision making under uncertainty where the uncertain problem data are governed by a probability distribution that is itself subject to uncertainty. The distribution is then assumed to belong to an ambiguity set comprising all distributions that are compatible with the decision maker’s prior information. In this paper, we propose a unifying framework for modeling and solving distributionally robust optimization problems. We introduce standardized ambiguity sets that contain all distributions with prescribed conic representable confidence sets and with mean values residing on an affine manifold. These ambiguity sets are highly expressive and encompass many ambiguity sets from the recent literature as special cases. They also allow us to characterize distributional families in terms of several classical and/or robust statistical indicators that have not yet been studied in the context of robust optimization. We determine conditions under which distributionally robust optimization problems based on our standardized ambiguity sets are computationally tractable. We also provide tractable conservative approximations for problems that violate these conditions.