Abstracts of papers by William L. Cooper Preprints and Reprints of Full Papers Available Upon Request (billcoop@me.umn.edu).
D. Zhang and W. L. Cooper. Managing clearance sales in the presence of strategic customers. Production and Operations Management, 17(4), 416-431, 2008. [journal] We study the effect of strategic customer behavior on pricing and availability decisions of a firm selling a single product. The product is sold in two periods at two possibly different prices, and the seller may limit the availability of the product (that is, ration) in the second (clearance) period. Some customers are strategic and respond to the pricing and rationing decisions by timing their purchases. When capacity is non-constraining and the seller has pricing flexibility, we show that rationing in the clearance period cannot improve revenue. When capacity is non-constraining and prices are fixed, we describe cases where rationing can indeed improve revenue. For cases with fixed prices, we conduct a detailed analysis for both linear and multiplicative demand curves, and derive explicit expressions for the optimal rationing level. We find that the policy of doing the better of not restricting availability at the clearance price or not offering the product at all at the clearance price typically yields revenue near that of using an optimal rationing level for the given prices. Our analysis also suggests that, given inappropriate fixed prices, rationing --- while sometimes offering considerable benefit over allowing unrestricted availability in the clearance period --- may allow the seller to obtain only a small fraction of the revenue that could have been had using optimal prices and no rationing. We extend the analysis to cases where the capacity is constraining, and obtain similar results.
D. Zhang and W. L. Cooper. Pricing substitutable flights in airline revenue management. To appear in European Journal of Operational Research, 2008. [journal] We develop a Markov decision process formulation of a dynamic pricing problem for multiple substitutable flights between the same origin and destination, taking into account customer choice among the flights. The model is rendered computationally intractable for exact solution by its multi-dimensional state and action spaces, so we develop and analyze various bounds and heuristics. We first describe three related models, each based on some form of pooling, and introduce heuristics suggested by these models. We also develop separable bounds for the value function which are used to construct value- and policy-approximation heuristics. Extensive numerical experiments show the value- and policy-approximation approaches to work well across a wide range of problem parameters, and to outperform the pooling-based heuristics in most cases. The methods are applicable even for large problems, and are potentially useful for practical applications.
K. Amaruchkul, W. L. Cooper, and D. Gupta. Single-leg air-cargo revenue management. Transportation Science, 41(4), 457-469, 2007. [paper] We consider a cargo booking problem on a single-leg flight with the goal of maximizing expected contribution. Each piece of cargo is endowed with a random volume and a random weight whose precise values are not known until just before the flight's departure. We formulate the problem as a Markov decision process. Exact solution of the formulation is impractical, because of its high-dimensional state space; therefore, we develop six heuristics. The first four heuristics are based on different value-function approximations derived from two computationally-tractable MDPs, each with a one-dimensional state space. The remaining two heuristics are obtained from solving related methematical programming problems. We also compare the heuristics with the first-come-first-served policy. Simulation experiments suggest that the value-function approximation derived from separate "volume" and "weight" problems offers the best approach. Comparisons of the expected contribution under the heuristic to an upper bound show that the heuristic is typically close to optimal.
W. L. Cooper and T. Homem-de-Mello. Some decomposition methods for revenue management. Transportation Science, 41(3), 332-353, 2007. [paper] Working within a Markov decision process (MDP) framework, we study revenue management policies that combine aspects of mathematical programming approaches and pure MDP methods by decomposing the problem by time, state, or both. The "time decomposition" policies employ heuristics early in the booking horizon, and switch to a more-detailed decision rule closer to the time of departure. We present a family of formulations that yield such policies, and discuss versions of the formulation that have appeared in the literature. Subsequently, we describe sampling-based stochastic optimization methods for solving a particular case of the formulation. Numerical results for two-leg problems suggest that the policies perform well. By viewing the MDP as a large stochastic program, we derive some structural properties of two-leg problems. We show that these properties cannot, in general, be extended to larger networks. For such larger networks we also present a "state-space decomposition" approach that partitions the network problem into two-leg subproblems, each of which is solved. The solutions of these subproblems are then re-combined to obtain a booking policy for the network problem.
W. L. Cooper, T. Homem-de-Mello, and A. J. Kleywegt. Models of the spiral-down effect in revenue management. Operations Research, 54(5), 968-987, 2006. [paper; appendix] The spiral-down effect occurs when incorrect assumptions about customer behavior cause high-fare ticket sales, protection levels, and revenues to systematically decrease over time. If an airline decides how many seats to protect for sale at a high fare based on past high-fare sales, while neglecting to account for the fact that availability of low-fare tickets will reduce high-fare sales, then high-fare sales will decrease, resulting in lower future estimates of high-fare demand. This subsequently yields lower protection levels for high-fare tickets, greater availability of low-fare tickets, and even lower high-fare ticket sales. The pattern continues, resulting in a so-called spiral down. We develop a mathematical framework to analyze the process by which airlines forecast demand and optimize booking controls over a sequence of flights. Within the framework, we give conditions under which spiral down occurs.
W. L. Cooper and D. Gupta. Stochastic comparisons in airline revenue management. Manufacturing & Service Operations Management, 8(3), 221-234, 2006. [paper] Consider two markets of different sizes but similar costs and fare structure. All other things being equal, is an airline's expected revenue larger in the market with larger demand? If not, under what circumstances is it possible to compare expected revenues without carrying out a detailed analysis? In this article, we provide answers to these questions by studying the relationship between the optimal expected revenue and the demand distributions when the latter are comparable according to various stochastic orders. For the two-fare class problem with dependent demand we obtain three results. We show that airlines should prefer lesser positive dependence between fare classes when marginal demand distributions are the same. We also describe particular dependence structures under which stochastically larger marginal demand distributions improve optimal expected revenue. Finally, when the dependence between effective demands in the two fare classes arises due to ``sell-ups", we show that stochastically larger marginal demand distributions should be preferred. [Sell ups occur when some lower fare-class customers buy higher-fare tickets upon finding that the former tickets are sold out.] For a problem with an arbitrary number of fare classes and independent demands, we show that stochastically larger demand distributions should be preferred. Numerical examples demonstrating the effect of parameterized demand distributions (with appropriate stochastic ordering) and dependence structures are also presented.
D. Zhang and W. L. Cooper. Revenue management for parallel flights with customer-choice behavior. Operations Research, 53(3), 414-431, 2005. [paper] We consider the simultaneous seat inventory control of a set of parallel flights between a common origin and destination with dynamic customer choice among the flights. We formulate the problem as an extension to the classic multi-period, single-flight "block demand" revenue management model. The resulting Markov decision process is quite complex, owing to its multidimensional state space and the fact that the airline's inventory controls do affect the distribution of demand. Using stochastic comparisons, consumer choice models, and inventory-pooling ideas, we derive easily-computable upper and lower bounds for the value function of our model. We propose simulation-based techniques for solving the stochastic optimization problem and also describe heuristics based upon an extension of a well-known linear-programming formulation. We provide numerical examples.
S. Benjaafar, W. L. Cooper, and J.-S. Kim. On the benefits of pooling in production-inventory systems. Management Science, 51(4), 548-565, 2005. [paper] We study inventory pooling in systems with symmetric costs where supply leadtimes are endogenously generated by a finite-capacity production system. We investigate the sensitivity of the cost advantage of inventory pooling to various system parameters, including loading, service-levels, demand and production time variability, and structure of the production system. The analysis reveals differences in how various parameters affect the cost reduction from pooling, and suggests that these differences stem from the manner in which the parameters influence the induced correlation between leadtime demands of the demand streams. We compare these results with those obtained for pure inventory systems, where leadtimes are exogenous. We also compare inventory pooling with several forms of capacity pooling.
D. Gupta and W. L. Cooper. Stochastic comparisons in production yield management. Operations Research, 53(2), 377-384, 2005. [paper] Manufacturing firms routinely commit resources to increase yield rates through product- and process-improvement initiatives. Champions of such yield-improvement projects may assume that stochastically larger yield rates are beneficial. We show in this note that this need not hold, even when the contingent production lot sizes are chosen optimally. We employ stochastic comparison techniques to show that a yield rate that is smaller in the convex order ensures higher expected profit, and we provide a distribution-free bound on the size of increase in expected profit. We also identify properties of yield-rate distributions that do make stochastically larger yield rates beneficial.
W. L. Cooper, S. G. Henderson, and M. E. Lewis. Convergence of simulation-based policy iteration. Probability in the Engineering and Informational Sciences, 17(2), 213-234, 2003. [journal] Simulation-based policy iteration (SBPI) is a modification of the policy iteration algorithm for computing optimal policies for Markov decision processes. At each iteration, rather than solving the average evaluation equations, SBPI employs simulation to estimate a solution to these equations. For recurrent average-reward Markov decision processes with finite state and action spaces, we provide easily-verifiable conditions that ensure that simulation-based policy iteration almost-surely eventually never leaves the set of optimal decision rules. We analyze three simulation estimators for solutions to the average evaluation equations. Using our general results, we derive simple conditions on the simulation runlengths that guarantee the almost-sure convergence of the algorithm.
W. L. Cooper. Asymptotic behavior of an allocation policy for revenue management. Operations Research, 50(4), 720-727, 2002. [paper] Revenue management has become an important tool in the airline, hotel, and rental car industries. We describe asymptotic properties of revenue management policies derived from the solution of a deterministic optimization problem. Our primary results state that, within a stochastic and dynamic framework, solutions arising out of a single well-known linear program can be used to generate allocation policies for which the normalized revenue converges in distribution to a constant upper bound on the optimal value. We also show similar asymptotic results for expected revenues. In addition, we describe counterintuitive behavior that can occur when allocations are updated during the booking process (updating allocations can lead to lower expected revenue). These results add to the understanding of allocation policies, and help to make concrete the statement that simple policies from easy-to-solve formulations can be relatively effective, even when analyzed in the more-realistic stochastic and dynamic framework.
W. L. Cooper and R. L. Tweedie. Perfect simulation of an inventory model for perishable products. Stochastic Models, 18(2), 229-243, 2002. [journal] We study an inventory model for perishable products with a critical-number ordering policy under the assumption that demand for the product forms an i.i.d. sequence, so that the state of the system forms a Markov chain. Explicit calculation of the stationary distribution has proved impractical in cases where items have reasonably long lifetimes and for systems with large under-up-to levels. Using the recently-developed coupling-from-the-past method, we introduce a technique to estimate the stationary distribution of the Markov chain via perfect simulation. The Markov chain that results from the use of a critical-number policy is particularly amenable to these simulation techniques, despite not being ordered in its initial state, since the recursive equations satisfied by the Markov chain enable us to identify specific demand patterns where the backward coupling occurs.
W. L. Cooper. Pathwise properties and performance bounds for a perishable inventory system. Operations Research, 49(3), 455-466, 2001. [paper] We study a perishable inventory system under a fixed-critical-number order policy. By using an appropriate transformation of the state vector, we derive several key sample-path relations. We obtain bounds on the limiting distribution of the number of outdates in a period, and we derive families of upper and lower bounds for the long-run number of outdates per unit time. Analysis of the bounds on the expected number of outdates shows that at least one of the new lower bounds is always greater than or equal to previously published lower bounds, while the new upper bounds are sometimes lower than and sometimes higher than the existing upper bounds. In addition, using an expected cost criterion, we compare optimal policies and different choices of critical-number policies.
W. L. Cooper, V. Schmidt, and R. F. Serfozo. Skorohod-Loynes characterizations of queueing, fluid, and inventory processes. Queueing Systems, 37(1-3), 233-257, 2001. [journal] We consider queueing, fluid and inventory processes whose dynamics are determined by general point processes or random measures that represent inputs and outputs. The state of such a process (the queue length or inventory level) is regulated to stay in a finite or infinite interval - inputs or outputs are disregarded when they would lead to a state outside the interval. The sample paths of the process satisfy an integral equation; the paths have finite local variation and may have discontinuities. We establish the existence and uniqueness of the process based on a Skorohod equation. This leads to an explicit expression for the process on the doubly-infinite time axis. The expression is especially tractable when the process is stationary with stationary input-output measures. This representation is an extension of the classical Loynes representation of stationary waiting times in single-server queues with stationary inputs and services. We also describe several properties of stationary processes: Palm probabilities of the processes at jump times, Little laws for waiting times in the system, finiteness of moments and extensions to tandem and treelike networks.
W. L. Cooper. Negative binomial sums of random variables and discounted reward processes. Journal of Applied Probability, 35(3), 589-599, 1998. [journal] Given a sequence of random variables (rewards), the Haviv-Puterman differential equation relates the expected infinite-horizon lambda-discounted reward and the expected total reward up to a random time that is determined by an independent negative binomial random variable with parameters 2 and lambda. This paper provides an interpretation of this proven, but previously unexplained, result. Furthermore, the interpretation is formalized into a new proof, which then yields new results for the general case where the rewards are accumulated up to a time determined by an independent negative binomial random variable with parameters k and lambda.
S. Benjaafar, W. L. Cooper, and S. Mardan. Production-inventory systems with imperfect advance demand information and updating. 2006. We consider a supplier with finite production capacity and stochastic production times that produces a single product. Customers provide advance demand information (ADI) to the supplier by announcing orders ahead of their due dates. However, this information is not perfect, and customers may request an order be fulfilled prior to or later than the expected due date or they may decide to cancel. Hence, the demand leadtime (the time between when an order is announced and when it becomes due or is canceled) is random. Customers update the status of their orders, but the time between consecutive updates is random as well. We consider several schemes through which ADI is revealed and updated. For each, we formulate the production-control problem as a continuous-time Markov decision process and prove that there is an optimal (among all policies) state-dependent base-stock policy, where the base-stock levels depend upon the number of orders at various stages of update. In addition, we derive results on the sensitivity of the state-dependent base-stock levels to the number of orders in each stage of update. In a numerical study, we examine the benefit of ADI to both supplier and customers and study the effect of having full versus partial ADI. We also compare the performance of a class of simple heuristics to that of an optimal policy.