Search

Because of uncertainty in customer demand and lack of understanding in customer reactions to price changes, it is a challenge for many companies, such as manufacturers and retailers, to match supply and demand. Most of the models in the operations literature, however, have focused on the case in which the underlying customer demand information is known a priori, which is not true in many applications. In "Coordinating Pricing and Inventory Replenishment with Nonparametric Demand Learning," B. Chen, X. Chao, and H. Ahn develop a data-driven algorithm for pricing and inventory decisions that learns the demand and customer information from sales data on the fly, and they show that the profit generated from the algorithm converges to the clairvoyant optimal profit at the quickest possible rate. We consider a firm (e.g., retailer) selling a single nonperishable product over a finite-period planning horizon. Demand in each period is stochastic and price sensitive, and unsatisfied demands are backlogged. At the beginning of each period, the firm determines its selling price and inventory replenishment quantity with the objective of maximizing total profit, but it knows neither the average demand (as a function of price) nor the distribution of demand uncertainty a priori; hence, it has to make pricing and ordering decisions based on observed demand data. We propose a nonparametric, data-driven algorithm that learns about the demand on the fly and, concurrently, applies learned information to make replenishment and pricing decisions. The algorithm integrates learning and action in a sense that the firm actively experiments on pricing and inventory levels to collect demand information with minimum profit loss. Besides convergence of optimal policies, we show that the regret of the algorithm, defined as the average profit loss compared with that of the optimal solution had the firm known the underlying demand information, vanishes at the fastest possible rate as the planning horizon increases. [ABSTRACT FROM AUTHOR]

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" by Dimitris Bertsimas and Velibor V. Mišić, the authors 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. A fundamental problem faced by firms is that of product line design: given a set of candidate products that may be offered to a collection of customers, what subset of those products should be offered to maximize the profit that is realized when customers make purchases according to their preferences? In this paper, we consider the product line design problem when customers choose according to a first-choice rule and present a new mixed-integer optimization formulation of the problem. We theoretically analyze the strength of our formulation and show that it is stronger than alternative formulations that have been proposed in the literature, thus contributing to a unified understanding of the different formulations for this problem. We also present a novel solution approach for solving our formulation at scale, based on Benders decomposition, which exploits the surprising fact that Benders cuts for both the relaxation and the integer problem can be generated in a computationally efficient manner. We demonstrate the value of our formulation and Benders decomposition approach through two sets of experiments. In the first, we use synthetic instances to show that our formulation is computationally tractable and can be solved an order of magnitude faster for small- to medium-scale instances than the alternate, previously proposed formulations. In the second, we consider a previously studied product line design instance based on a real conjoint data set, involving over 3,000 candidate products and over 300 respondents. We show that this problem, which required a week of computation time to solve in prior work, is solved by our approach to full optimality in approximately 10 minutes. The e-companion is available at https://doi.org/10.1287/opre.2018.1825. [ABSTRACT FROM AUTHOR]

In Ban and Rudin's (2018) "The Big Data Newsvendor: Practical Insights from Machine Learning," the authors take an innovative machine-learning approach to a classic problem solved by almost every company, every day, for inventory management. By allowing companies to use large amounts of data to predict the correct answers to decisions directly, they avoid intermediate questions, such as "how many customers will we get tomorrow?" and instead can tell the company how much inventory to stock for these customers. This has implications for almost all other decision-making problems considered in operations research, which has traditionally considered data estimation separately from the decision optimization. Their proposed methods are shown to work both analytically and empirically with the latter explored in a hospital nurse staffing example in which the best one-step, feature-based newsvendor algorithm (the kernel-weights optimization method) is shown to beat the best-practice benchmark by 24% in the out-of-sample cost at a fraction of the speed. We investigate the data-driven newsvendor problem when one has n observations of p features related to the demand as well as historical demand data. Rather than a two-step process of first estimating a demand distribution then optimizing for the optimal order quantity, we propose solving the "big data" newsvendor problem via single-step machine-learning algorithms. Specifically, we propose algorithms based on the empirical risk minimization (ERM) principle, with and without regularization, and an algorithm based on kernel-weights optimization (KO). The ERM approaches, equivalent to high-dimensional quantile regression, can be solved by convex optimization problems and the KO approach by a sorting algorithm. We analytically justify the use of features by showing that their omission yields inconsistent decisions. We then derive finite-sample performance bounds on the out-of-sample costs of the feature-based algorithms, which quantify the effects of dimensionality and cost parameters. Our bounds, based on algorithmic stability theory, generalize known analyses for the newsvendor problem without feature information. Finally, we apply the feature-based algorithms for nurse staffing in a hospital emergency room using a data set from a large UK teaching hospital and find that (1) the best ERM and KO algorithms beat the best practice benchmark by 23% and 24%, respectively, in the out-of-sample cost, and (2) the best KO algorithm is faster than the best ERM algorithm by three orders of magnitude and the best practice benchmark by two orders of magnitude. The online appendices are available at https://doi.org/10.1287/opre.2018.1757. [ABSTRACT FROM AUTHOR]

Assortment optimization has received significant attention in recent revenue management and combinatorial optimization literature. In "The Approximability of Assortment Optimization Under Ranking Preferences," A. Aouad, V. Farias, R. Levi, and D. Segev provide best-possible approximability bounds for this problem under an almost general model specification, where preferences are expressed as a distribution over rankings. This paper shows how this optimization problem relates to the computational task of detecting large independent sets in graphs, allowing the establishment of strong complexity lower bounds with respect to various problem parameters. These findings are complemented by a number of algorithms that attain essentially best-possible approximation factors, proving that the hardness results are tight up to lower-order terms. Surprisingly, their results imply that a simple and widely studied policy, known as revenue-ordered assortments, achieves the best possible performance guarantee with respect to prices. The main contribution of this paper is to provide best-possible approximability bounds for assortment planning under a general choice model, where customer choices are modeled through an arbitrary distribution over ranked lists of their preferred products, subsuming most random utility choice models of interest. From a technical perspective, we show how to relate this optimization problem to the computational task of detecting large independent sets in graphs, allowing us to argue that general ranking preferences are extremely hard to approximate with respect to various problem parameters. These findings are complemented by a number of approximation algorithms that attain essentially best-possible factors, proving that our hardness results are tight up to lower-order terms. Surprisingly, our results imply that a simple and widely studied policy, known as revenue-ordered assortments, achieves the best possible performance guarantee with respect to the price parameters. [ABSTRACT FROM AUTHOR]

We study the joint assortment planning and inventory management problem, where stock-out events elicit dynamic substitution effects, described by the multinomial logit (MNL) choice model. Special cases of this setting have been extensively studied in recent literature, notably the static assortment planning problem. Nevertheless, to our knowledge, the general formulation is not known to admit efficient algorithms with analytical performance guarantees before this work, and most of its computational aspects are still wide open. In this paper, we devise what is, to our knowledge, the first provably good approximation algorithm for dynamic assortment planning under the MNL model. We derive a constant-factor guarantee for a broad class of demand distributions that satisfy the increasing failure rate property. Our algorithm relies on a combination of greedy procedures, where stocking decisions are restricted to specific classes of products and the objective function takes modified forms. We demonstrate that our approach substantially outperforms state-of-the-art heuristic methods in terms of performance and speed, leading to an average revenue gain of 4% to 12% in computational experiments. In the course of establishing our main result, we develop new algorithmic ideas that may be of independent interest. These include weaker notions of submodularity and monotonicity, shown sufficient to obtain constant-factor worst-case guarantees, despite using noisy estimates of the objective function. [ABSTRACT FROM AUTHOR]

We study a class of problems with both binary selection decisions and associated continuous choices that result in stochastic rewards and costs. The rewards are received based on the decision maker's selection, and the costs depend both on the decisions and realizations of the stochastic variables. We consider a family of risk-based objective functions that contains the traditional risk-neutral expected-value objective as a special case. A combination of rounding and sample average approximation is used to produce solutions that are guaranteed to be close to the optimal solution with high probability. We also provide an empirical comparison of the performance of the algorithms on a set of randomly generated instances of a supply chain example problem. The computational results illustrate the theoretical claims in the paper that, for this problem, high-quality solutions can be found with small computational effort. [ABSTRACT FROM AUTHOR]

The presence of customer substitution poses substantial challenges to a firm's inventory management, particularly so when the firm has to manage a multiproduct portfolio with capacity restrictions. In this paper, we derive the optimal inventory policy for a capacity-constrained firm selling multiple partially substitutable products over a finite season in a market with stockout-based customer substitution. We also establish the sensitivity of the optimal policy with respect to changes in capacity and substitution preferences. In doing so, we disentangle the direct and indirect dynamics of substitution, and show the nonmonotonic and partially counterintuitive influence of capacity and substitution on the firm's optimal inventory policy. [ABSTRACT FROM AUTHOR]

We study capacitated assortment problems when customers choose under the multinomial logit model with nested consideration sets. In this choice model, there are multiple customer types, and a customer of a particular type is interested in purchasing only a particular subset of products. We use the term consideration set to refer to the subset of products that a customer of a particular type is interested in purchasing. The consideration sets of customers of different types are nested in the sense that the consideration set of one customer type is included in the consideration set of another. The choice process for customers of different types is governed by the same multinomial logit model except for the fact that customers of different types have different consideration sets. Each product, if offered to customers, occupies a certain amount of space. The sale of each product generates a certain amount of revenue. Given that customers choose from among the offered products according to the multinomial logit model with nested consideration sets, the goal of the assortment problem is to find a set of products to offer to maximize the expected revenue obtained from a customer, while making sure that the total space consumption of the offered products does not exceed a certain limit. We show that this assortment problem is NP-hard, even when there is no limit on the total space consumption of the offered products. Motivated by this complexity result, we give a fully polynomial time approximation scheme for the problem. [ABSTRACT FROM AUTHOR]

We address the multiproduct newsvendor problem under a general specification of customer choice behavior.We develop a methodology that yields upper bounds on the optimal value as well as feasible inventory solutions. The methodology is based on an approximate Jordan decomposition of the state transition matrix. Two specializations of the methodology are presented: one leads to a decomposition by customer into a sequence of assortment optimization problems and the second leads to a decomposition by product into a collection of independent newsvendor problems. We conduct computational experiments and find that the proposed methodology outperforms existing bounds. [ABSTRACT FROM AUTHOR]

We study a fundamental model of resource allocation in which a finite amount of service capacity must be allocated to a stream of jobs of different priorities arriving randomly over time. Jobs incur costs and may also cancel while waiting for service. To increase the rate of service, overtime capacity can be used at a cost. This model has application in healthcare scheduling, server applications, make-to-order manufacturing systems, general service systems and green computing. We present an online algorithm that minimizes the total cost due to waiting, cancellations and overtime capacity usage. We prove that our scheduling algorithm has cost at most twice of an optimal offline algorithm. This competitive ratio is the best possible for this class of problems. We also provide extensive numerical experiments to test the performance of our algorithm and its variants. [ABSTRACT FROM AUTHOR]

We study joint chance constraints where the distribution of the uncertain parameters is only known to belong to an ambiguity set characterized by the mean and support of the uncertainties and by an upper bound on their dispersion. This setting gives rise to pessimistic (optimistic) ambiguous chance constraints, which require the corresponding classical chance constraints to be satisfied for every (for at least one) distribution in the ambiguity set. We demonstrate that the pessimistic joint chance constraints are conic representable if (i) the constraint coefficients of the decisions are deterministic, (ii) the support set of the uncertain parameters is a cone, and (iii) the dispersion function is of first order, that is, it is positively homogeneous. We also show that pessimistic joint chance constrained programs become intractable as soon as any of the conditions (i), (ii) or (iii) is relaxed in the mildest possible way. We further prove that the optimistic joint chance constraints are conic representable if (i) holds, and that they become intractable if (i) is violated. We show in numerical experiments that our results allow us to solve large-scale project management and image reconstruction models to global optimality. [ABSTRACT FROM AUTHOR]

We study a firm's optimal strategy to adjust its capacity using demand information. The capacity adjustment is costly and often subject to managerial hurdles, which sometimes make it difficult to adjust capacity multiple times. To clearly analyze the impact of demand learning on the firm's decision, we study two scenarios. In the first scenario, the firm's capacity adjustment cost increases significantly with respect to the number of adjustments because of significant managerial hurdles, and resultantly the firm has a single opportunity to adjust capacity ( single adjustment scenario). In the second scenario, the capacity adjustment cost does not change with respect to the number of adjustments because of little managerial hurdles, and therefore the firm has multiple opportunities to adjust capacity ( multiple adjustment scenario). For both scenarios, we first formulate the problem as a stochastic dynamic program, and then characterize the firm's optimal policy: when to adjust and by how much. We show that the optimal decision on when and by how much to change the capacity is not monotone in the likelihood of high demand in the single adjustment scenario, while the optimal decision is monotone under mild conditions, and the optimal policy is a control band policy in the multiple adjustment scenario. The sharp contrast reflects the impact of demand learning on the firm's optimal capacity decision. Since computing and implementing the optimal policy is not tractable for general problems, we develop a data-driven heuristic for each scenario. In the single adjustment scenario, we show that a two-step heuristic, which explores demand for an appropriately chosen length of time and adjusts the capacity based on the observed demand is asymptotically optimal, and show the convergence rate. In the multiple adjustment scenario, we also show that a multistep heuristic under which the firm adjusts its capacity at a predetermined set of periods with an exponentially increasing gap between two consecutive decisions is asymptotically optimal and shows its convergence rate. We finally apply our heuristics to a numerical study and demonstrate the performance and robustness of the heuristics. The online appendix is available at . [ABSTRACT FROM AUTHOR]

Inventory models with lost sales and large lead times have traditionally been considered intractable due to the curse of dimensionality. Recently, Goldberg and coauthors laid the foundations for a new approach to solving these models, by proving that as the lead time grows large, a simple constant-order policy is asymptotically optimal. However, the bounds proven there require the lead time to be very large before the constant-order policy becomes effective, in contrast to the good numerical performance demonstrated by Zipkin even for small lead time values. In this work, we prove that for the infinite-horizon variant of the same lost sales problem, the optimality gap of the same constant-order policy actually converges exponentially fast to zero, with the optimality gap decaying to zero at least as fast as the exponential rate of convergence of the expected waiting time in a related single-server queue to its steady-state value. We also derive simple and explicit bounds for the optimality gap, and demonstrate good numerical performance across a wide range of parameter values for the special case of exponentially distributed demand. Our main proof technique combines convexity arguments with ideas from queueing theory. [ABSTRACT FROM AUTHOR]

We consider optimization problems whose parameters are known only approximately, based on noisy samples. In large-scale applications, the number of samples one can collect is typically of the same order of (or even less than) the dimensionality of the problem. This so-called high-dimensional statistical regime has been the object of intense recent research in machine learning and statistics, primarily due to phenomena inherent to this regime, such as the fact that the noise one sees here often dwarfs the magnitude of the signal itself. While relevant in numerous important operations research and engineering optimization applications, this setup falls far outside the traditional scope of robust and stochastic optimization. We propose three algorithms to address this setting, combining ideas from statistics, machine learning, and robust optimization. Our algorithms are motivated by three natural optimization objectives: minimizing the number of grossly violated constraints; maximizing the number of exactly satisfied constraints; and, finally, developing algorithms whose running time scales with the intrinsic dimension of a problem, as opposed to its observed dimension-a mismatch that, as we discuss in detail, can be dire in settings where constraints are meant to describe preferences of behaviors. The key ingredients of our algorithms are dimensionality reduction techniques from machine learning, robust optimization, and concentration of measure tools from statistics. [ABSTRACT FROM AUTHOR]

We consider new online variants of supply chain management models, where in addition to production decisions, one also has to actively decide on which customers to serve. Specifically, customers arrive sequentially during a selection phase, and one has to decide whether to accept or reject each customer upon arrival. If a customer is rejected, then a lost-sales cost is incurred. Once the selection decisions are all made, one has to satisfy all the accepted customers with minimum possible production cost. The goal is to minimize the total cost of lost sales and production. A key feature of the model is that customers arrive in an online manner, and the decision maker does not require any information about future arrivals. We provide two novel algorithms for online customer selection problems, which are based on repeatedly solving offline subproblems that ignore previously made decisions. For many important settings, our algorithms achieve small constant competitive ratio guarantees. That is, for any sequence of arriving customers, the cost incurred by the online algorithm is within a fixed constant factor of the cost incurred by the respective optimal solution that has full knowledge upfront on the sequence of arriving customers. Finally, we provide a computational study on the performance of these algorithms when applied to the economic lot sizing and joint replenishment problems with online customer selection. [ABSTRACT FROM AUTHOR]

We propose a nonparametric data-driven algorithm called DDM for the management of stochastic periodic-review multiproduct inventory systems with a warehouse-capacity constraint. The demand distribution is not known a priori and the firm only has access to past sales data (often referred to as censored demand data). We measure performance of DDM through regret, the difference between the total expected cost of DDM and that of an oracle with access to the true demand distribution acting optimally. We characterize the rate of convergence guarantee of DDM. More specifically, we show that the average expected T -period cost incurred under DDM converges to the optimal cost at the rate of O(T-1/2). Our asymptotic analysis significantly generalizes approaches used in Huh and Rusmevichientong (2009) for the uncapacitated single-product inventory systems. We also discuss several extensions and conduct numerical experiments to demonstrate the effectiveness of our proposed algorithm. [ABSTRACT FROM AUTHOR]

Consider the newsvendor model, but under the assumption that the underlying demand distribution is not known as part of the input. Instead, the only information available is a random, independent sample drawn from the demand distribution. This paper analyzes the sample average approximation (SAA) approach for the data-driven newsvendor problem. We obtain a new analytical bound on the probability that the relative regret of the SAA solution exceeds a threshold. This bound is significantly tighter than existing bounds, and it matches the empirical accuracy of the SAA solution observed in extensive computational experiments. This bound reveals that the demand distribution's weighted mean spread affects the accuracy of the SAA heuristic. [ABSTRACT FROM AUTHOR]

We consider an online multi-item retailer with multiple fulfillment facilities and finite inventory. The challenge faced by the retailer is to construct a fulfillment policy to decide from which facility each of the items in the arriving order should be fulfilled, in a way that minimizes the expected total shipping costs of fulfilling customer orders over a finite horizon. Shipping costs are linear in the size of the package shipped as well as the distance from the facility to the customer. We approximate the stochastic control formulation, which is computationally intractable, with a deterministic linear program (DLP) whose size is polynomial in the size of the input. We then study the performance of two fulfillment heuristics derived from the solution of the DLP. The first heuristic implements the solution of the DLP as fulfillment probability for each item. Since fulfillment decision for each item is made independently of fulfillment decision of other items in the same order, this heuristic does not have a satisfactory performance. The second heuristic improves the first heuristic by allowing fulfillment consolidation across different items in the same order. We do this by modifying the DLP solution through a carefully constructed correlated rounding (or coupling) among the decision variables. We provide a theoretical upper bound on the asymptotic competitive ratio of both heuristics with respect to the optimal policy. Our numerical experiments show that the second heuristic performs very close to optimal for a wide range of problem parameters. [ABSTRACT FROM AUTHOR]

In this paper, we show how any model with a general shelf-age-dependent holding cost and delay-dependent backlogging cost structure may be transformed into an equivalent model in which all expected inventory costs are level dependent. We develop our equivalency results, first, for periodic review models with full backlogging of stockouts. These equivalency results permit us to characterize the optimal procurement strategy in various settings and to adopt known algorithms to compute such strategies. For models in which all or part of stockouts are lost, we show that the addition of any shelfage and delay-dependent cost structure does not complicate the structure of the model beyond what is required under the simplest, i.e., linear, holding and backlogging costs. We proceed to show that our results carry over to continuous review models, with demands generated by compound renewal processes; the continuous review models with shelf-age and delay-dependent carrying and backlogging costs are shown to be equivalent to periodic review models with convex level-dependent inventory cost functions. [ABSTRACT FROM AUTHOR]

Given uncertain popularity of new products by location, fast fashion retailer Zara faces a trade-off. Large initial shipments to stores reduce lost sales in the critical first days of the product life cycle, but maintaining stock at the warehouse allows restocking flexibility once initial sales are observed. In collaboration with Zara, we develop and test a decision support system featuring a data-driven model of forecast updating and a dynamic optimization formulation for allocating limited stock by location over time. A controlled field experiment run worldwide with 34 articles during the 2012 season showed an increase in total average season sales by approximately 2% and a reduction in the number of unsold units at the end of the regular selling season by approximately 4%. [ABSTRACT FROM AUTHOR]

We consider the classic continuous-review Nstage serial inventory system with a homogeneous Poisson demand arrival process at the most downstream stage (Stage 1). Any shipment to each stage, regardless of its size, incurs a positive fixed setup cost and takes a positive constant lead time. The optimal policy for this system under the long-run average cost criterion is unknown. Finding a good worst-case performance guarantee remains an open problem. We tackle this problem by introducing a class of modified echelon (r, Q) policies that do not require Qi+1/Qi to be a positive integer: Stage i+1 ships to Stage i based on its observation of the echelon inventory position at Stage i; if it is at or below ri and Stage i+1 has positive on-hand inventory, then a shipment is sent to Stage i to raise its echelon inventory position to ri + Qi as close as possible. We construct a heuristic policy within this class of policies, which has the following features: First, it has provably primitive-dependent performance bounds. In a two-stage system, the performance of the heuristic policy is guaranteed to be within (1 + K1/K2) times the optimal cost, where K1 is the downstream fixed cost and K2 is the upstream fixed cost. We also provide an alternative performance bound, which depends on efficiently computable optimal (r, Q) solutions to N single-stage systems but tends to be tighter. Second, the heuristic is simple, it is efficiently computable and it performs well numerically; it is even likely to outperform the optimal integer-ratio echelon (r, Q) policies when K1 is dominated by K2. Third, the heuristic is asymptotically optimal when we take some dominant relationships between the setup or holding cost primitives at an upstream stage and its immediate downstream stage to the extreme, for example, when h2/h1 → 0, where h1 is the downstream holding cost parameter and h is the upstream holding cost parameter. [ABSTRACT FROM AUTHOR]

Motivated by the rising popularity of electronic appointment booking systems, we develop appointment scheduling models that take into account the patient preferences regarding when they would like to be seen. The service provider dynamically decides which appointment days to make available for the patients. Patients arriving with appointment requests may choose one of the days offered to them or leave without an appointment. Patients with scheduled appointments may cancel or not show up for the service. The service provider collects a "revenue" from each patient who shows up and incurs a "service cost" that depends on the number of scheduled appointments. The objective is to maximize the expected net "profit" per day. We begin by developing a static model that does not consider the current state of the scheduled appointments. We give a characterization of the optimal policy under the static model and bound its optimality gap. Building on the static model, we develop a dynamic model that considers the current state of the scheduled appointments, and we propose a heuristic solution procedure. In our computational experiments, we test the performance of our models under the patient preferences estimated through a discrete choice experiment that we conduct in a large community health center. Our computational experiments reveal that the policies we propose perform well under a variety of conditions. [ABSTRACT FROM AUTHOR]

In this paper we introduce the knapsack problem for perishable inventories concerning the optimal dynamic allocation of a collection of products to a limited knapsack. The motivation for designing such a problem comes from retail revenue management, where different products often have an associated lifetime during which they can only be sold, and the managers can regularly select some products to be allocated to a limited promotion space that is expected to attract more customers than the standard shelves. Another motivation comes from scheduling of requests in modern multiserver data centers so that quality-of-service requirements given by completion deadlines are satisfied. Using the Lagrangian approach we derive an optimal index policy for the Whittle relaxation of the problem in which the knapsack capacity is used only on average. Assuming a certain structure of the optimal policy for the single-inventory control, we prove indexability and derive an efficient, linear-time algorithm for computing the index values. To the best of our knowledge, our paper is the first to provide indexability analysis of a restless bandit with bi-dimensional state (lifetime and inventory level). We illustrate that these index values are numerically close to the true index values when such a structure is not present. We test two index-based heuristics for the original, nonrelaxed problem: (1) a conventional index rule, which prescribes to order the products according to their current index values and promotes as many products as fit in the knapsack, and (2) a recently proposed index-knapsack heuristic, which employs the index values as a proxy for the price of promotion and proposes to solve a deterministic knapsack problem to select the products. By a systematic computational study we show that the performance of both heuristics is nearly optimal, and that the index-knapsack heuristic outperforms the conventional index rule. [ABSTRACT FROM AUTHOR]

We study fixed-dimensional stochastic dynamic programs in a discrete setting over a finite horizon. Under the primary assumption that the cost-to-go functions are discrete L턮-convex, we propose a pseudo-polynomial time approximation scheme that solves this problem to within an arbitrary prespecified additive error of ε > 0. The proposed approximation algorithm is a generalization of the explicit-enumeration algorithm and offers us full control in the trade-off between accuracy and running time. The main technique we develop for obtaining our scheme is approximation of a fixed-dimensional L턮-convex function on a bounded rectangular set, using only a selected number of points in its domain. Furthermore, we prove that the approximation function preserves L턮-convexity. Finally, to apply the approximate functions in a dynamic program, we bound the error propagation of the approximation. Our approximation scheme is illustrated on a well-known problem in inventory theory, the single-product problem with lost sales and lead times. We demonstrate the practical value of our scheme by implementing our approximation scheme and the explicit-enumeration algorithm on instances of this inventory problem. [ABSTRACT FROM AUTHOR]

In this paper, we study an online make-to-order variant of the classical joint replenishment problem (JRP) that has been studied extensively over the years and plays a fundamental role in broader planning issues, such as the management of supply chains. In contrast to the traditional approaches of the stochastic inventory theory, we study the problem using competitive analysis against a worst-case adversary. Our main result is a 3-competitive deterministic algorithm for the online version of the JRP. We also prove a lower bound of approximately 2.64 on the competitiveness of any deterministic online algorithm for the problem. Our algorithm is based on a novel primal-dual approach using a new linear programming relaxation of the offline JRP model. The primal-dual approach that we propose departs from previous primal-dual and online algorithms in rather significant ways. We believe that this approach can extend the range of problems to which online and primal-dual algorithms can be applied and analyzed. [ABSTRACT FROM AUTHOR]

In this paper we investigate a stochastic appointment-scheduling problem in an outpatient clinic with a single doctor. The number of patients and their sequence of arrivals are fixed, and the scheduling problem is to determine an appointment time for each patient. The service durations of the patients are stochastic, and only the mean and covariance estimates are known. We do not assume any exact distributional form of the service durations, and we solve for distributionally robust schedules that minimize the expectation of the weighted sum of patients' waiting time and the doctor's overtime. We formulate this scheduling problem as a convex conic optimization problem with a tractable semidefinite relaxation. Our model can be extended to handle additional support constraints of the service durations. Using the primal--dual optimality conditions, we prove several interesting structural properties of the optimal schedules. We develop an efficient semidefinite relaxation of the conic program and show that we can still obtain near-optimal solutions on benchmark instances in the existing literature. We apply our approach to develop a practical appointment schedule at an eye clinic that can significantly improve the efficiency of the appointment system in the clinic, compared to an existing schedule. [ABSTRACT FROM AUTHOR]

We develop new algorithmic approaches to compute provably near-optimal policies for multiperiod stochastic lot-sizing inventory models with positive lead times, general demand distributions, and dynamic forecast updates. The policies that are developed have worst-case performance guarantees of 3 and typically perform very close to optimal in extensive computational experiments. The newly proposed algorithms employ a novel randomized decision rule. We believe that these new algorithmic and performance analysis techniques could be used in designing provably near-optimal randomized algorithms for other stochastic inventory control models and more generally in other multistage stochastic control problems. [ABSTRACT FROM AUTHOR]

We consider Markov decision processes with unknown transition probabilities and unknown single-period expected cost functions, and we study a method for estimating these quantities from historical or simulated data. The method requires knowledge of the system equations that govern state transitions as well as the single-period cost functions (but not the single-period expected cost functions). The estimation procedure is based upon taking expectations with respect to the empirical distribution functions of such data. Once the estimates are in place, the method computes a policy by solving the obtained "empirical" Markov decision process as if the estimates were correct. For MDPs that satisfy some conditions, we provide explicit, easily computed expressions for the probability that the procedure will produce a policy whose true expected cost is within any specified absolute distance of the actual optimal expected cost of the true Markov decision process. We also provide expressions for the number of historical or simulated data values that is sufficient for the procedure to produce a policy whose true expected cost is, with a prescribed probability, within a prescribed absolute distance of the actual optimal expected cost of the true Markov decision process. We apply our results to multiperiod inventory models. In addition, we provide a specialized analysis of such inventory models that also yields relative, rather than absolute, accuracy guarantees. We make comparisons with related results that have recently appeared, and we provide numerical examples. [ABSTRACT FROM AUTHOR]

We consider the problem of appointment scheduling with discrete random durations but under the more realistic assumption that the duration probability distributions are not known and only a set of independent samples is available, e.g., historical data. For a given sequence of appointments (jobs, tasks), the goal is to determine the planned starting time of each appointment such that the expected total underage and overage costs due to the mismatch between allocated and realized durations is minimized. We use the convexity and subdifferential of the objective function of the appointment scheduling problem to determine bounds on the number of independent samples required to obtain a provably near-optimal solution with high probability. [ABSTRACT FROM AUTHOR]

The article provides examples of works focused on the structure of the optimal policy as a function of the initial inventory level. It addresses the case of convex revenues and holding costs where if order costs are convex, the generalized base stock policy is optimal with the stock level after ordering an increasing function of the initial stock level and the optimal amount ordered is a decreasing function of the initial stock level. It provides contributions including new hardness results for finding the maximum expected profit for different nonlinear newsvendor problem (NNV) models, fully polynomial time approximation schemes (FPTASs) for NNV models when the profit-to-cost ration is bounded away from zero and general conditions that guarantee the existence of FPTAS.

Using the well-known product-limit form of the Kaplan-Meier estimator from statistics, we propose a new class of nonparametric adaptive data-driven policies for stochastic inventory control problems. We focus on the distribution-free newsvendor model with censored demands. The assumption is that the demand distribution is not known and there are only sales data available. We study the theoretical performance of the new policies and show that for discrete demand distributions they converge almost surely to the set of optimal solutions. Computational experiments suggest that the new policies converge for general demand distributions, not necessarily discrete, and demonstrate that they are significantly more robust than previously known policies. As a by-product of the theoretical analysis, we obtain new results on the asymptotic consistency of the Kaplan-Meier estimator for discrete random variables that extend existing work in statistics. To the best of our knowledge, this is the first application of the Kaplan-Meier estimator within an adaptive optimization algorithm, in particular, the first application to stochastic inventory control models. We believe that this work will lead to additional applications in other domains. [ABSTRACT FROM AUTHOR]

We develop multidimensional balancing algorithms to compute provably near-optimal capacity-expansion policies. Our approach is computationally efficient and guaranteed to produce a policy with total expected cost of no more than twice that of an optimal policy. We overcome the curse of dimensionality by introducing novel cost-separation schemes to separate the lost-sales cost of the system into exact monotonic subparts. This is the first approximation technique for multimachine, multiproduct systems facing stochastic, nonstationary, and correlated demands. To show the generality of this separation technique, we apply it to the capacity-expansion problem under two different production planning models: monotone production and revenue-maximizing production. We make the assumptions of minimal inventory and lost sales. [ABSTRACT FROM AUTHOR]

We consider an assortment optimization problem where a retailer chooses an assortment of products that maximizes the profit subject to a capacity constraint. The demand is represented by a multinomial logit choice model. We consider both the static and dynamic optimization problems. In the static problem, we assume that the parameters of the logit model are known in advance; we then develop a simple algorithm for computing a profit-maximizing assortment based on the geometry of lines in the plane and derive structural properties of the optimal assortment. For the dynamic problem, the parameters of the logit model are unknown and must be estimated from data. By exploiting the structural properties found for the static problem, we develop an adaptive policy that learns the unknown parameters from past data and at the same time optimizes the profit. Numerical experiments based on sales data from an online retailer indicate that our policy performs well. [ABSTRACT FROM AUTHOR]

Motivated by emerging applications in workforce management, we consider a class of revenue management problems in systems with reusable resources. The corresponding applications are modeled using the well-studied loss network systems. We use an extremely simple linear program (LP) that provides an upper bound on the best achievable expected long-run revenue rate. The optimal solution of the LP is used to devise a conceptually simple control policy that we call the class selection policy (CSP). Moreover, the LP is used to analyze the performance of the CSP and show that it admits uniform performance guarantees. In particular, for the model with a single resource and uniform resource requirements, we prove that the CSP is guaranteed to have an expected long-run revenue rate that is at least half of the best achievable. Furthermore, as the capacity of the system grows to infinity, the CSP is asymptotically optimal, regardless of any other parameter of the problem. Finally, our techniques can be used to analyze the performance of the well-known class of trunk-reservation policies. [ABSTRACT FROM AUTHOR]

We study a two-echelon supply chain with one warehouse and N (nonidentical) retailers facing stochastic demand. An easy-to-implement inventory policy, the so-called power-of-two (POT) policy, is proposed to manage inventory for the system. To maintain a certain service level, safety stocks are kept at the warehouse and each retailer outlet to buffer random demand. Our analysis highlights the important role of the warehouse safety stock level, which, in addition to the length of the warehouse order interval, significantly affects the lengths of the retailers' order intervals. By combining the length of the warehouse order interval with the warehouse safety stock level, we introduce a plane partition method and develop a polynomial time algorithm to find a POT policy for arbitrary target service levels. The long-run average cost of the proposed POT policy is guaranteed to be no more than 1.26 times the optimal POT policy cost. We also show that our proposed policy can be computed in O(N³) [ABSTRACT FROM AUTHOR]

We consider the one-warehouse multiple retailer inventory model with a submodular joint setup cost function. The objective of this model is to determine an inventory replenishment policy that minimizes the long-run average system cost over an infinite time horizon. Although the optimal policy for this problem is still unknown, a class of easy-to-implement power-of-two policies are 98% effective. This paper focuses on how the cost, under an optimal power-of-two policy, should be allocated to the retailers. This question generates an interesting cooperative game. We prove that this cooperative game has a nonempty core. The key to our result is a strong duality theorem for the one-warehouse multiple retailer problem under power-of-two policies. [ABSTRACT FROM AUTHOR]

We consider the notoriously difficult discrete-time inventory model with stochastic demands, a constant lead time, and lost sales. We show that the effective state space is a relatively manageable compact set. Then, we test various plausible heuristics. We find that several perform reasonably well, although none is perfect. However, the standard base-stock policy (a direct analogue of the optimal policy for a backlog system) performs badly. We also show that the optimal cost is increasing in the lead time. [ABSTRACT FROM AUTHOR]

We develop the first algorithmic approach to compute provably good ordering policies for a multiperiod, capacitated, stochastic inventory system facing stochastic nonstationary and correlated demands that evolve over time. Our approach is computationally efficient and guaranteed to produce a policy with total expected cost no more than twice that of an optimal policy. As part of our computational approach, we propose a novel scheme to account for backlogging costs in a capacitated, multiperiod environment. Our cost-accounting scheme, called the forced marginal backlogging cost-accounting scheme, is significantly different from the period-by-period accounting approach to backlogging costs used in dynamic programming; it captures the long-term impact of a decision on system performance in the presence of capacity constraints. In the likely event that the per-unit order costs are large compared to the holding and backlogging costs, a transformation of cost parameters yields a significantly improved guarantee. We also introduce new semi myopic policies based on our new cost-accounting scheme to derive bounds on the optimal base-stock levels. We show that these bounds can be used to effectively improve any policy. Finally, empirical evidence is presented that indicates that the typical performance of this approach is significantly stronger than these worst-case guarantees. [ABSTRACT FROM AUTHOR]

Traditional stochastic inventory models assume full knowledge of the demand probability distribution. However, in practice, it is often difficult to completely characterize the demand distribution, especially in fast-changing markets. In this paper, we study the newsvendor problem with partial information about the demand distribution (e.g., mean, variance, symmetry, unimodality). In particular, we derive the order quantities that minimize the newsvendor's maximum regret of not acting optimally. Most of our solutions are tractable, which makes them attractive for practical application. Our analysis also generates insights into the choice of the demand distribution as an input to the newsvendor model. In particular, the distributions that maximize the entropy perform well under the regret criterion. Our approach can be extended to a variety of problems that require a robust but not conservative solution. [ABSTRACT FROM AUTHOR]

We compare two inventory systems, one in which excess demand is lost and the other in which excess demand is backordered. Both systems are reviewed periodically. They experience the same sequence of identically and independently distributed random demands. Holding and shortage costs are considered. The holding cost parameter is identical; however, the cost of a lost sale could be different from the per-period cost of backlogging a unit sale. When these costs are equal, we prove that the optimal expected cost for managing the system with lost sales is lower. When the cost of a lost sale is greater, we establish a relationship between these parameters that ensures that the reverse inequality is true. These results are useful for designing inventory systems. We also introduce a new stochastic comparison technique in this paper. [ABSTRACT FROM AUTHOR]

We consider a finite-horizon, periodic-review inventory model with demand forecasting updates following the martingale model of forecast evolution (MMFE). The optimal policy is a state-dependent base-stock policy, which, however, is computationally intractable to obtain. We develop tractable bounds on the optimal base-stock levels and use them to devise a general class of heuristic solutions. Through this analysis, we identify a necessary and sufficient condition for the myopic policy to be optimal. Finally, to assess the effectiveness of the heuristic policies, we develop upper bounds on their value loss relative to optimal cost. These solution bounds and cost error bounds also work for general dynamic inventory models with nonstationary and autocorrelated demands. Numerical results are presented to illustrate the results. [ABSTRACT FROM AUTHOR]