Title: New approaches to inventory control: algorithms, asymptotics and robustness

Advisors: Dr. David A. Goldberg and Dr. Alexander Shapiro

Committee members: Dr. Shabbir Ahmed, Dr. Jim Dai (School of Operations Research and Information Engineering, Cornell University), and Dr. Alan Scheller-Wolf (Tepper School of Business, Carnegie Mellon University)

Date and time:  Monday, April 13 2015, 12:00PM

Location:  ISyE Main - Conference Rooms - Poole Board Room

Abstract:
 
The fundamental problem of managing an inventory over time in the presence of stochastic demand is one of the core problems of operations research. This thesis is motivated by the need (in both government and industry) to understand such complex inventory systems used to model many of society's most important problems. In particular, we investigate simple, efficient and robust inventory policies for several fundamental models commonly used in the study of stochastic inventory systems. Some of these policies have been already implemented in practice and we provide theoretic support for their practical utilization in industry. Furthermore, the results on the performance of these policies often yield a rule-of-thumb that is applicable in a variety of settings.
 
There are four main chapters in this thesis. In the second chapter, we study lost sales inventory model with positive lead time. Although such a model has been studied for over fifty years, the structure of the optimal policy remains poorly understood. Furthermore, it is notoriously difficult to solve the dynamic program especially when the lead time is large due to the curse of dimensionality. Recently, \cite{Goldberg12} proved that a simple constant-order policy (proposed earlier by \cite{Reiman04}) is asymptotically optimal as the lead time grows large.  However, the bound proven there is impractical. Numerical experiments of \cite{Zipkin08b} suggested the good performance of constant-order policies even for small lead times, and there remains a huge gap between the existing theoretical bound and the actual performance of constant-order policies. In this chapter, we significantly improve the bound. In particular, we prove that the same constant-order policy actually conver
 ges exponentially fast to optimality as the lead time grows. In addition, our bound is simple and explicit, demonstrating good performance of constant-order policies for realistic lead time values. Our results provide theoretical justification for the good performance of such simple policies, and open the window to making the results and methodology practical.
 
In the third chapter, we investigate dual-sourcing inventory systems, which arise naturally in many real-world supply chains (cf. \cite{Allon10}).  These systems are notoriously difficult to optimize due to the complex structure of the optimal solution and the curse of dimensionality. Recently, so-called Tailored Base-Surge (TBS) policies have been proposed as a heuristic for the dual-sourcing problem, and analyzed in \cite{Allon10} and \cite{Janakiraman14a}.  Under such a policy, a constant order is placed at the regular source in each period, while the order placed at the express source follows a simple order-up-to rule.  Numerical experiments by several authors have suggested that such policies perform well as the lead time difference between the two sources grows large, which is exactly the setting in which the curse of dimensionality leads to the problem becoming intractable.  However, providing a theoretical foundation for this phenomenon has remained a major open probl
 em. In this chapter, we provide such a theoretical foundation by proving that a simple TBS policy is indeed asymptotically optimal as the lead time of the regular source grows large, with the lead time of the express source held fixed. Interestingly, the simple TBS policy performs nearly optimally exactly when standard DP-based methodologies become intractable due to the aforementioned ``curse of dimensionality".  Furthermore, as the ``best" TBS policy can be computed by solving a convex program that does not depend on the lead time of the regular source, our results lead directly to very efficient algorithms (with complexity independent of the lead time of the regular source) with asymptotically optimal performance guarantees.  Perhaps most importantly, since many companies are already implementing such TBS policies (cf. \cite{Allon10}), our results provide strong theoretical support for the widespread use of TBS policies in practice.
 
In the fourth chapter, we explore the concept of time consistency in the context of distributionally robust inventory models with second moment constraints. Recently, several communities have observed that a subtle phenomena known as time inconsistency, which never happen in the classic (non-robust) setting, can arise in the framework of distributionally robust optimization. In particular, there have been two fundamentally different approaches taken in the literature regarding the specification of uncertainty in the underlying joint distribution, depending on whether the underlying optimization model is static or dynamic in nature. In a multistage static formulation, one specifies a family of joint distributions for demand over time, typically by fixing means, covariances, and supports (or some generalization thereof), and then solves an associated global minimax optimization problem. Such static formulations generally cannot be decomposed and solved by dynamic programming an
 d are generally referred to as time-inconsistent in the literature. Alternatively, in a multistage dynamic formulation, the underlying family of potential joint distributions must implicitly satisfy certain conditional independence properties, and thus allow for a resolution by dynamic programming. The existence of such a decomposition is generally referred to as the rectangularity property (cf. \cite{Iyengar05}, \cite{Nilim05}). In this chapter, we provide several illustrative examples showing that here the question of time consistency can be quite subtle and complement these observations by providing simple sufficient conditions for time consistency. We also prove that, although the multistage-dynamic formulation always has an optimal policy of base-stock form, there may be no such optimal policy for the multistage-static formulation. Interestingly, our results show that time consistency may hold even when rectangularity does not.
 
In the fifth chapter, we study distributionally robust inventory control with martingale demand. Many inventory models assume perfect knowledge of the demand distribution. However, exact knowledge of such distributions is rarely available in practice, and there has been a growing interest in developing inventory control policies which are robust to model misspecification. In the context of distributionally robust inventory control which was initiated in \cite{Scarf58}, one assumes that the joint distribution of future demand belongs to some set of joint distributions, and solves the min-max problem of computing the control policy which is optimal against a worst-case distribution belonging to this set. Although such models have been analyzed previously, the cost and policy implications of positing different dependency structures remains poorly understood (cf. \cite{Agrawal12}). In this chapter, we combine the framework of distributionally robust optimization with the theory o
 f martingales, and study a novel distributionally robust model in which the sequence of future demands is assumed to belong to a family of martingales. We explicitly compute the optimal policy and shed light on the interplay between the optimal policy and worst-case distribution. In particular, we show that at optimality, in each period the adversary always selects a demand distribution with two-point support, with one of these points equal to zero. Combined with the martingale property, this implies that at optimality, the worst-case demand distribution corresponds to the setting in which demand may become obsolete at a random time, a scenario of practical interest which has been studied previously in the literature (cf. \cite{Song96}). We also compare to the analogous setting in which demand is independent across periods (previously studied in \cite{Shapiro12}). Interestingly, we find the ratio of the optimal cost under the martingale and independent models to be exactly 1
 /2 in the perfectly symmetric case. Our results shed light on several intriguing phenomena regarding the impact of correlations on distributionally robust models, and provide a first step towards developing a conditional-expectation based theory of dynamic distributionally robust forecasting.