Knowledge that Transforms

We consider the problem of minimizing daily expected resource usage and overtime costs across multiple parallel resources such as anesthesiologists and operating rooms, which are used to conduct a variety of surgical procedures at large multispecialty hospitals. To address this problem, we develop a two-stage, mixed-integer stochastic dynamic programming model with recourse. The first stage allocates these resources across multiple surgeries with uncertain durations and prescribes the sequence of surgeries to these resources. The second stage determines actual start times to surgeries based on realized durations of preceding surgeries and assigns overtime to resources to ensure all surgeries are completed using the allocation and sequence determined in the first stage. We develop a data-driven robust optimization method that solves large-scale real-sized versions of this model close to optimality. We validate and implement this model as a decision support system at the UCLA Ronald Reagan Medical Center. This system effectively incorporates the flexibility in the resources and uncertainty in surgical durations, and explicitly trades off resource usage and overtime costs. This has increased the average daily utilization of the anesthesiologists by 3.5% and of the operating rooms by 3.8%. This has led to an average daily cost savings of around 7% or estimated to be $2.2 million on an annual basis. In addition, the insights based on this model have significantly influenced decision making at the operating services department at this hospital. The e-companion is available at https://doi.org/10.1287/opre.2017.1634 .

In this paper, we present a new budget allocation framework for the problem of selecting the best simulated design from a finite set of alternatives. The new framework is developed on the basis of general underlying distributions and a finite simulation budget. It adopts the expected opportunity cost (EOC) quality measure, which, compared to the traditional probability of correct selection (PCS) measure, penalizes a particularly bad choice more than a slightly incorrect selection, and is thus preferred by risk-neutral practitioners and decision makers. To this end, we establish a closed-form approximation of EOC to formulate the budget allocation problem and derive the corresponding optimality conditions. A sequential budget allocation algorithm is then developed for implementation. The efficiency of the proposed method is illustrated via numerical experiments. We also link the EOC and PCS-based budget allocation problems by showing that the two are asymptotically equivalent. This result explains, to some extent, the similarity in performance between the EOC and PCS allocation procedures observed in the literature. The online appendix is available at https://doi.org/10.1287/opre.2016.1581 .

Bilevel optimization problems are very challenging optimization models arising in many important practical contexts, including pricing mechanisms in the energy sector, airline and telecommunication industry, transportation networks, critical infrastructure defense, and machine learning. In this paper, we consider bilevel programs with continuous and discrete variables at both levels, with linear objectives and constraints (continuous upper level variables, if any, must not appear in the lower level problem). We propose a general-purpose branch-and-cut exact solution method based on several new classes of valid inequalities, which also exploits a very effective bilevel-specific preprocessing procedure. An extensive computational study is presented to evaluate the performance of various solution methods on a common testbed of more than 800 instances from the literature and 60 randomly generated instances. Our new algorithm consistently outperforms (often by a large margin) alternative state-of-the-art methods from the literature, including methods exploiting problem-specific information for special instance classes. In particular, it solves to optimality more than 300 previously unsolved instances from the literature. To foster research on this challenging topic, our solver is made publicly available online. The online appendix is available at https://doi.org/10.1287/opre.2017.1650 .

We propose an expectation-maximization (EM) method to estimate customer preferences for a category of products using only sales transaction and product availability data. The demand model combines a general, rank-based discrete choice model of preferences with a Bernoulli process of customer arrivals over time. The discrete choice model is defined by a probability mass function (pmf) on a given set of preference rankings of alternatives, including the no-purchase alternative. Each customer is represented by a preference list, and when faced with a given choice set is assumed to either purchase the available option that ranks highest in her preference list, or not purchase at all if no available product ranks higher than the no-purchase alternative.We apply the EM method to jointly estimate the arrival rate of customers and the pmf of the rank-based choice model, and show that it leads to a remarkably simple and highly efficient estimation procedure. All limit points of the procedure are provably stationary points of the associated incomplete data log-likelihood function, and the output produced are maximum likelihood estimates (MLEs). Our numerical experiments confirm the practical potential of the proposal.The online appendix is available at https://doi.org/10.1287/opre.2016.1559 .

In this study, we introduce the regenerator location problem in flexible optical networks. With a given traffic demand, the regenerator location problem in flexible optical networks considers the regenerator location, routing, bandwidth allocation, and modulation selection problems jointly to satisfy data transfer demands with the minimum cost regenerator deployment. We propose a novel branch-and-price algorithm for this challenging problem. Using real-world network topologies, we conduct extensive numerical experiments to both test the performance of the proposed solution methodology and evaluate the practical benefits of flexible optical networks. In particular, our results show that, making routing, bandwidth allocation, modulation selection, and regenerator placement decisions in a joint manner, it is possible to obtain drastic capacity enhancements when only a very modest portion of the nodes is endowed with the signal regeneration capability.

We study inventory control of serial supply chains with continuous, Markov-modulated demand (MMD). Our goal is to simplify the computational complexity by resorting to certain approximation techniques, and, in doing so, to gain a deeper understanding of the problem. First, we perform a derivative analysis of the problem’s optimality equations and develop general, analytical solution bounds for the optimal policy. This leads to simple-to-compute near-optimal heuristic solutions, which also reveal an intuitive relationship with the primitive model parameters. Second, we establish an MMD central limit theorem under long replenishment lead time through asymptotic analysis. We show that the relative errors between our heuristic and the optimal solutions converge to zero as the lead time becomes sufficiently long, with the rate of convergence being the square root of the lead time. Third, we show that, by leveraging the Laplace transform, the computational complexity of our heuristic is superior to the existing methods. Finally, we provide the first set of numerical study for serial systems under MMD. The numerical results demonstrate that our heuristic achieves near-optimal performance even under short lead times and outperforms alternative heuristics in the literature. In addition, we observe that, in an optimally run supply chain under MMD, the internal fill rate can be high and the demand variability propagating upstream can be dampened, both different from the system behaviors under stationary demand. The online appendix is available at https://doi.org/10.1287/opre.2017.1615 .

Consolidation carriers transport shipments that are small relative to trailer capacity. To be cost effective, the carrier must consolidate shipments, which requires coordinating their paths in both space and time; i.e., the carrier must solve a service network design problem. Most service network design models rely on discretization of time—i.e., instead of determining the exact time at which a dispatch should occur, the model determines a time interval during which a dispatch should occur. While the use of time discretization is widespread in service network design models, a fundamental question related to its use has never been answered: Is it possible to produce an optimal continuous-time solution without explicitly modeling each point in time? We answer this question in the affirmative. We develop an iterative refinement algorithm using partially time-expanded networks that solves continuous-time service network design problems. An extensive computational study demonstrates that the algorithm not only is of theoretical interest but also performs well in practice.

Sales promotions are important in the fast-moving consumer goods (FMCG) industry due to the significant spending on promotions and the fact that a large proportion of FMCG products are sold on promotion. This paper considers the problem of planning sales promotions for an FMCG product in a grocery retail setting. The category manager has to solve the promotion optimization problem (POP) for each product, i.e., how to select a posted price for each period in a finite horizon so as to maximize the retailer’s profit. Through our collaboration with Oracle Retail, we developed an optimization formulation for the POP that can be used by category managers in a grocery environment. Our formulation incorporates business rules that are relevant, in practice. We propose general classes of demand functions (including multiplicative and additive), which incorporate the post-promotion dip effect, and can be estimated from sales data. In general, the POP formulation has a nonlinear objective and is NP-hard. We then propose a linear integer programming (IP) approximation of the POP. We show that the IP has an integral feasible region, and hence can be solved efficiently as a linear program (LP). We develop performance guarantees for the profit of the LP solution relative to the optimal profit. Using sales data from a grocery retailer, we first show that our demand models can be estimated with high accuracy, and then demonstrate that using the LP promotion schedule could potentially increase the profit by 3%, with a potential profit increase of 5% if some business constraints were to be relaxed. The online appendix is available at https://doi.org/10.1287/opre.2016.1573

We present a randomized O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem (ATSP). This provides the first asymptotic improvement over the long-standing Θ(log n)-approximation bound stemming from the work of Frieze et al. (1982) [Frieze AM, Galbiati G, Maffioki F (1982) On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12(1):23–39]. The key ingredient of our approach is a new connection between the approximability of the ATSP and the notion of so-called thin trees. To exploit this connection, we employ maximum entropy rounding—a novel method of randomized rounding of LP relaxations of optimization problems. We believe that this method might be of independent interest.

We consider revenue management problems when customers choose among the offered products according to the Markov chain choice model. In this choice model, a customer arrives into the system to purchase a particular product. If this product is available for purchase, then the customer purchases it. Otherwise, the customer transitions to another product or to the no purchase option, until she reaches an available product or the no purchase option. We consider three classes of problems. First, we study assortment problems, where the goal is to find a set of products to offer to maximize the expected revenue obtained from each customer. We give a linear program to obtain the optimal solution. Second, we study single resource revenue management problems, where the goal is to adjust the set of offered products over a selling horizon when the sale of each product consumes the resource. We show how the optimal set of products to offer changes with the remaining resource inventory. Third, we study network revenue management problems, where the goal is to adjust the set of offered products over a selling horizon when the sale of each product consumes a combination of resources. A standard linear programming approximation of this problem includes one decision variable for each subset of products. We show that this linear program can be reduced to an equivalent one with a substantially smaller size. We give an algorithm to recover the optimal solution to the original linear program from the reduced linear program. The reduced linear program can dramatically improve the solution times for the original linear program. The online appendix, data files, and source code are available at https://doi.org/10.1287/opre.2017.1628 .