Solving Robust Inventory
Problems
by
f. s
Submitted in partial ful_llment of the
requirements for the degree
of Doctor of Philosophy
in the Graduate School of Arts and Sciences
COLUMBIA UNIVERSITY
2006
ABSTRACT
Solving Robust Inventory Problems
In this work we consider setting the optimal inventory control policies for a single
bu_er when demand is uncertain, in a robust framework. Unlike traditional inventory
models we do not assume that the demand is random with a known distribution.
Instead, demand can take values from a given uncertainty set. Our objective is to
_nd the policy that minimize the maximum cost that is attainable by the demand
vectors in our uncertainty set. We consider the problem for two di_erent types of
policies which are very common in practice and present a family of algorithms based
on decomposition that scale well to problems with hundreds of time periods. We also
present theoretical results on more general models.
Contents
1 Introduction 1
1.1 Literature review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Our model and contributions . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Generic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 The Static Problem 15
2.1 Prior work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Demand uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 The decision maker's problem . . . . . . . . . . . . . . . . . . . . . . 23
2.4 The adversarial problem under the risk budgets model . . . . . . . . 24
2.4.1 A special case . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.2 The adversarial problem as a mixed-integer program . . . . . 31
2.5 The adversarial problem in the bursty demand model . . . . . . . . . 33
2.6 Computational results for the static problem . . . . . . . . . . . . . . 34
i
3 The Basestock Problem 39
3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2 The decision maker's problem . . . . . . . . . . . . . . . . . . . . . . 44
3.3 The adversarial problem under the risk budgets model . . . . . . . . 48
3.3.1 Handling M. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.2 Handling B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.3 Handling F . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3.4 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3.5 The approximate adversarial algorithm . . . . . . . . . . . . . 60
3.3.6 Integral budgets case . . . . . . . . . . . . . . . . . . . . . . . 62
3.3.7 A bounding procedure for the risk budgets model . . . . . . . 63
3.4 The adversarial problem under the bursty demand model . . . . . . . 64
3.5 Experiments with the basestock model . . . . . . . . . . . . . . . . . 68
3.5.1 The risk budgets model . . . . . . . . . . . . . . . . . . . . . . 68
3.5.2 The bursty demand model . . . . . . . . . . . . . . . . . . . . 74
3.6 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.6.1 Polyhedral uncertainty sets . . . . . . . . . . . . . . . . . . . 80
3.6.2 Robust safety stocks . . . . . . . . . . . . . . . . . . . . . . . 81
3.6.3 Ambiguous uncertainty sets . . . . . . . . . . . . . . . . . . . 88
3.6.4 Model superposition . . . . . . . . . . . . . . . . . . . . . . . 91
3.6.5 More comprehensive supply-chain models . . . . . . . . . . . . 93
ii
3.7 Summary of the results . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4 The Dynamic Problem 95
4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.2 Characterization of optimal policies . . . . . . . . . . . . . . . . . . . 101
4.3 Risk budgets model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.3.1 A special case . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.4 Bursty demand model . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Appendices 109
A An alternative approach for solving PM 109
B NP-completeness proofs 116
B.1 Proof of Theorem 3.4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 116
B.2 Proof of Theorem 3.6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 119
C Algorithms for the discrete budgets model 121
C.1 Proof of Theorem 3.6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . 121
C.2 Proof of Theorem 3.6.5 . . . . . . . . . . . . . . . . . . . . . . . . . . 126
iii
List of Figures
2.1 Example with many steps . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1 % error in basestock vs. % error in cost . . . . . . . . . . . . . . . . . 74
3.2 E_ect of scaling peaks on optimum basestock . . . . . . . . . . . . . 79
iv
List of Tables
2.1 Solving the adversarial problem as a mixed-integer program . . . . . 32
2.2 Parameters for data generation . . . . . . . . . . . . . . . . . . . . . 35
2.3 Running time and number of iterations . . . . . . . . . . . . . . . . . 37
2.4 Running time and number of iterations for the budgets model . . . . 38
3.1 Performance of algorithm for risk budgets (T = 100). . . . . . . . . . 69
3.2 Error in the basestock produced by using early termination. . . . . . 69
3.3 Performance statistics { integral budgets . . . . . . . . . . . . . . . . 70
3.4 Ratio of adversarial time to total running time for the budgets model 71
3.5 Static vs Basestock Policies . . . . . . . . . . . . . . . . . . . . . . . 72
3.6 % increase in average cost of dynamic and static policies over the rolling
horizon basestock policy . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.7 Behavior of algorithm for bursty demand model under a constant basestock
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.8 Impact of window size on a 300-period model . . . . . . . . . . . . . 76
v
3.9 Impact of initial inventory . . . . . . . . . . . . . . . . . . . . . . . . 77
3.10 Variance vs Optimal Basestock . . . . . . . . . . . . . . . . . . . . . 79
vi
CHAPTER 1. INTRODUCTION 1
Chapter 1
Introduction
Designing an e_cient supply chain and operating it e_ciently is one of the most important
issues for a large number of modern organizations. For the past three decades,
increasing economic and competitive pressure has forced manufacturers to create better
ways to control every single step in their supply chain, from supplier contracts to
distribution channels. Due to recent uctuations in the economy, matching supply to
demand has become even more challenging. Nowadays, there is a growing need for
more robust supply chains that are responsive to the changes in market conditions.
This work was inspired by a project carried out with an industrial partner and it concerns
the optimal stock ordering policies for a bu_er in a supply chain in an uncertain
environment.
CHAPTER 1. INTRODUCTION 2
1.1 Literature review
The origins of Supply Chain/Inventory Management can be found as early as the
beginning of 20th century when Harris [H13] derived the Economic-Order-Quantity
formula that applies when the demand is assumed to be constant over time. Over
the few decades preceding his work numerous authors elaborated di_erent variations
of Harris' EOQ model. Although pioneers of the _eld were aware of the uncertainties
associated with the problem, the study of the problem in a stochastic setting was
only started in the 1950's, with the seminal papers by Arrow, Harris and Marschak
[AHM51] and Dworetzky, Kiefer and Wolfowitz [DKW52]. Since then, supply chain
optimization problems have been studied extensively under stochastic settings using
di_erent methodologies such as dynamic programming and stationary analysis. We
refer the reader to Zipkin [Z00] for a comprehensive discussion of various models in
supply chain/inventory management.
One of the most important advancements in supply chain management took place
when Clark and Scarf [CS60] proved the optimality of basestock policies for serial systems
using dynamic programming, a powerful technique that would later be used by
many other authors to derive structural results about optimal inventory control policies.
Subsequently, basestock policies became increasingly popular and were proved
to be optimal for many other inventory models. For further work on basestock policies
see Iglehart [I63a, I63b], Veinott [V66], Ehrhart [E84] and Muharremoglu and
CHAPTER 1. INTRODUCTION 3
Tsitsiklis [MT01]. While such a policy is not necessarily optimal, it may be preferable
over optimal policies since it is easy to implement and often performs very well. Due
to its simplicity it is widely used in practice and _nding optimal basestock levels itself
has drawn a lot of attention by both practitioners and researchers.
Traditional models for supply chain management are often criticized by practitioners
for their strong assumptions, among which is full knowledge of the underlying
demand distribution. In most real world applications, especially in industries with
short product life cycles, paucity of historical demand data makes it very hard to
determine a demand distribution that _ts the observed data. In such situations the
inventory controller should make decisions using partial information, such as inaccurate
forecasts, about future demand, and estimates for the error in these forecasts.
To the best of our knowledge the _rst work on distribution free supply chain
management problems is due to Scarf [S58] who considered a single period newsvendor
problem and determined the orders that maximize the minimum expected pro_t over
all possible demand distributions for given _rst and second moments. Later, Gallego
and Moon [GM93, MG94] provided concise derivations of his results and extended
it to other cases. Gallego, Ryan and Simchi-Levi [GRS01] considered the multiperiod
version of this problem with discrete demand distribution and proved the
optimality of basestock policies. Recently, Bertsimas and Thiele [BT04] and Ben-Tal
et. al. [BGNV05] studied some supply chain management problems with limited
demand information using the robust optimization framework. The central di_erence
CHAPTER 1. INTRODUCTION 4
of their work from previous work is that instead of assuming partial information about
the distribution of the demand, they assume that uncertain demand is explicitly
represented by a set that de_nes all possible demand values. In Chapter 2 we provide
a detailed discussion of their results. Also see [BGGN04] and [T05].
Robust Optimization is an increasingly accepted way to handle uncertainty. It
addresses parameter uncertainties in deterministic optimization problems. Unlike
Stochastic Programming it does not assume that the uncertain parameters are random
variables with known distributions, instead it represents uncertainty in parameters
using deterministic uncertainty sets in which all possible values of these parameters
reside. Typically, Robust Optimization adopts a min-max approach that guarantees
the feasibility of the obtained solution for all possible values of the uncertain
parameters in the given uncertainty sets.
Although the underlying ideas are older, the classical references for Robust Optimization
are Ben-Tal and Nemirovski [BN98, BN99, BN00] where they studied a
group of convex optimization problems with uncertain parameters and showed that
they can be formulated as conic programs which can be solved in polynomial time.
Since then, there has been a large amount of research dealing with various aspects of
Robust Optimization. For example, Bertsimas and Sim [BS03] proposed a new polyhedral
uncertainty set that guarantees feasibility with high probability for general
distributions for the uncertain parameters. They show that Linear Programs with
this uncertainty framework can be reformulated as Linear Programs with a small
CHAPTER 1. INTRODUCTION 5
number of additional variables. Also see [AZ05], where robustness is introduced in
the context of a combinatorial optimization problem.
Robust Optimization methodology was originally developed to deal with static
problems in which all of the decision variables are set prior to resolution of any uncertainty.
However, in most real life applications, the dynamic nature of the problems
allows decision makers to revise their decisions as more information about the uncertain
parameters becomes available. This is especially true for multi-period decision
making problems where static robust optimization models are unable to capture the
fact that the decision maker knows the values of uncertain parameters in the preceding
periods and can exploit this information when making his decisions. Recognizing
the need for incorporating the dynamic nature of the multi-period decision making
problems into Robust Optimization models, Ben-Tal et. al. [BGGN04], recently
proposed A_nely Adjustable Robust Counterpart models which feature the idea of
dynamically determining decision variables as a_ne functions of the portion of the
uncertain data that has been realized. By restricting the decisions to a_ne functions
of the past data they managed to produce tractable formulations for uncertain
Linear Programs. Ben-Tal et. al. [BGNV05] applied these ideas to a supply chain
management problem to get a polynomial time solvable formulation. We will review
this work more closely in Section 2.1.
Another _eld that deals with uncertainty in optimization problems is Adversarial
Queuing, which was _rst considered by Borodin et. al [BKRSW96]. They studied
CHAPTER 1. INTRODUCTION 6
packet routing over queuing networks when there is only limited information about
demand. Following an approach similar to Robust Optimization, they adopted a
worst case approach and proved some stability results that holds for all realizations
of the demand. They used a demand model that is _rst introduced by Cruz [C91] to
capture the burstiness of inputs in communication networks. Later, Andrews et. al.
[AAFKLL96] considered a similar problem with di_erent network protocols.
1.2 Our model and contributions
In this thesis we develop procedures for setting the stock ordering policies for a bu_er
in a supply chain subject to uncertainty in the demands. As mentioned before, our
work is motivated by experience with an industrial partner in the electronics industry
who faced the following di_culties: short product cycles, a complex supply chain
with multiple suppliers and long production leadtimes, a paucity of demand data
and a very competitive environment. The combination of these factors produced a
signi_cant exposure to risk, in the form of either excessive inventory or shortages. The
supply chain of our industrial partner consisted of a network with multiple bu_ers;
however, in this work we consider a system made up of a single bu_er.
We consider a bu_er evolving over a _nite time horizon. For t = 1; 2; : : : ; T,
the quantity xt denotes the inventory at the start of period t (possibly negative to
indicate a shortage) with x1 given. We also have a (per unit) inventory holding cost
CHAPTER 1. INTRODUCTION 7
ht, a backlogging cost bt, and a production cost ct. The dynamics during period t
work out as follows:
(a) First, one orders (produces, etc) a quantity ut _ 0, thereby increasing inventory
to xt + ut, and incurring a cost ctut,
(b) Next, the demand dt _ 0 at time t is realized, decreasing inventory to xt+1
:=
xt + ut dt,
(c) Finally, at the end of period t, we pay a cost of maxfhtxt+1;btxt+1g.
This model can be extended in a number of ways, for example by considering
capacities, setup costs, or termination conditions. These features can easily be added
to the algorithms described in this thesis.
We are interested in operating the bu_er so that the sum of all costs incurred
between time 1 and T is minimized. In order to devise a strategy to this e_ect,
we need to make precise steps (a) and (b). In what follows, we will refer to the
minimum-cost problem as the \basic inventory problem".
In general, we are given a set D (the uncertainty set). Each element of D is a
vector (d1; d2; : : : ; dT ) of demands that is available to an adversary. At time t, having
previously chosen demand values ^ di (1 _ i _ t 1), the adversary can choose any
demand value ^ dt such that there is some vector ( ^ d1; : : : ; ^ dt1; ^ dt; dt+1; : : : ; dT ) 2 D.
Given an uncertainty set D, we need a strategy to produce orders ut so as to minimize
the maximum cost that can arise from demands in D. To make this statement
CHAPTER 1. INTRODUCTION 8
precise, we need to specify how (a) is implemented. In other words, for each time t
we need to describe a decision rule, such that the decision maker observes the current
state of the system (e.g. the current inventory xt) and prior actions on the part of
the adversary, and chooses ut appropriately. A policy is the the sequence of such
decision rules and we denote the set of all available policies by _. Typical examples
of policies are the basestock policy in which our decision rule in each period is given
by the function maxf_t xtg for a given basestock level _t and the static policy in
which the decision maker determines the orders in advance independent of the state
of the system or actions of the adversary.
The main focus of this thesis concerns how to pick the optimal policy in the robust
setting, under various demand uncertainty sets D. In the succeeding three chapters we
consider the \basic inventory problem" for three di_erent variants of _. We propose
a generic methodology and using this methodology we develop algorithms to compute
the optimal stock ordering policies.
The inventory problem in the robust setting can be described as follows:
min
_2_
max
d2D
cost(_; d); (1.1)
where for _ 2 _ and d 2 D,
cost(_; d) =
XT
t=1
( ctut(_; d) + maxf htxt+1(_; d) ; btxt+1(_; d)g ) (1.2)
where ut(_; d) denotes the order that would be placed by policy _ at time t under
demands d1; d2; : : : ; dt1, and xt(_; d) would likewise denote the inventory at the start
CHAPTER 1. INTRODUCTION 9
of period t. Here, the quantity x1 (the initial inventory level) is an input and once
the demand variables (d1; d2; : : : ; dt1) 2 D and the policy _ have been chosen, ut
and xt are uniquely determined, for 1 _ t _ T. Notice that cost(_; d) is the cost
corresponding to policy _ and demand pattern d; and worst-case the cost arising
from applying policy _ is given by
max
d2D
cost(_; d): (1.3)
We call (1.3) the adversarial problem.
In Section 1.2.1 we discuss a generic algorithm for solving (1.1) for di_erent types
of policies and demand uncertainty sets (for di_erent sets _ and D). The algorithm
is based on a common approach, Benders' decomposition [B62], and extensive experimentation
shows it to be quite fast for the cases that are considered in this thesis.
Although we consider a speci_c inventory management problem, our methodology is
general and can be used to solve many other minmax type problems.
In Chapter 2, we limit our policy space to static policies. We assume that in each
period t, the order quantity is determined in advance and _xed regardless of the state
of the system, i.e. our decision rule is de_ned by a constant function of the state of the
system and the past actions by the adversary. We develop an algorithm to compute
the optimal static policy. We numerically prove the e_ciency of our algorithm by
testing it on many large examples.
The static policy does not allow the inventory controller to dynamically use the
CHAPTER 1. INTRODUCTION 10
information that becomes available as the uncertainty in the system is resolved. However,
this is unrealistic since in real world applications the decision maker can make
dynamic decisions. In Chapter 3 we consider the basestock policies as a tool to incorporate
the dynamic nature of the problem into our methodology. We construct our
policy space with constant basestock policies, i.e. policies such that for 1 _ t _ T and
for a real constant _, the order quantity in period t is equal to maxf_ xt; 0g where
xt denotes the inventory on-hand at the beginning of period t. Notice that when
using a basestock policy, the inventory controller determines an order-up-to level and
if the on-hand inventory is less that that level he places an order to push it back up
to its ideal level. Although basestock policies have their own limitations, the e_ect of
uncertainty on inventory levels (therefore inventory cost) is not as severe as under a
static policy because of the cap it places on inventory level. In Chapter 3 we present
a numerical comparison of optimal basestock policies with optimal static policies.
Part of the reason for our focus on basestock policies is that they have acquired
very wide use and can be shown to be optimal under stochastic inventory models.
Further, though basestock policies may not always be optimal, they are viewed as
producing easily implementable policies for practitioners. In Chapter 3 we propose
an algorithm to pick the optimal basestock level for an inventory bu_er under several
robust uncertainty models. Extensive experimentation shows that our algorithm
proves to be very e_cient.
At the other extreme we may consider making decisions dynamically. Instead of
CHAPTER 1. INTRODUCTION 11
determining the policy at the very beginning of the horizon, the inventory controller
can delay the ordering decision in each period t until the beginning of period t,
which makes it possible to use all of the information that becomes available by period
t. Naturally, such a policy performs very well under uncertainty since it gives the
inventory controller greater freedom to set the orders. We call this problem the
dynamic problem, and in Chapter 4 we give a characterization of the optimal policies
and show how to compute them.
1.2.1 Generic algorithm
Our generic algorithm, given next, maintains a working list ~D of demand patterns
{ each member of ~D is a demand vector (d1; d2; : : : ; dT ) 2 D. The algorithm also
maintains an upper bound U and a lower bound L on the value of problem (1.1).
This algorithm can be viewed as a form of Bender's decomposition. [B62]
Note that the decision maker's problem is of the same general form as the generic
problem (1.1) { however, the key di_erence is that while D is in general exponentially
large, at any point ~D has size equal to the number of iterations run so far. One
of the properties of Benders' decomposition is that, when successful, the number of
iterations until termination will be small. In experimental testing, this number turned
out quite small indeed, as we will see.
In fact, the decision maker's problem proves to be quite tractable: roughly speakC
HAPTER 1. INTRODUCTION 12
ing, it amounts to an easily solvable convex optimization problem. For example, in
the case of static policies the problem can be formulated as a linear program with
O(Tj~Dj) variables and constraints.
Algorithm 1.2.1 GENERIC ALGORITHM
Initialize: ~D = ;, L = 0 and U = +1.
1. Decision maker's problem. Let ~_ be the solution to the problem:
min_2_ maxd2 ~D cost(_; d).
Set L maxd2 ~D cost(~_; d).
2. Adversarial problem. Let _ d be the solution to the problem:
maxd2D cost(~_; d).
Set U min
n
U ; cost(~_; _ d)
o
.
3. Termination test. If U L is small enough, then EXIT.
4. Formulation update. Otherwise, add _ d to ~D and return to Step 1.
On the other hand, the adversarial problem is non-convex. In at least one case we
can show that it is NP-hard. The problem can be also modeled as a mixed-integer
program, but tackling this mixed-integer program directly turns out not to be the best
approach. Instead, we devise simple combinatorial algorithms that prove e_cient.
Benders' decomposition algorithms have long enjoyed popularity in many conC
HAPTER 1. INTRODUCTION 13
texts. In the case of stochastic programming with large number of scenarios, they
prove essential in that they e_ectively reduce a massively large continuous problem
into a number of much smaller independent problems. In the context of non-convex
optimization (such as the problem handled in this paper) the appeal of decomposition
is that it vastly reduces combinatorial complexity.
Benders' decomposition methods can be viewed as a special case of cutting-plane
methods. As is the case for cutting-plane methods for combinatorial optimization,
there is no adequate general theory to explain why Benders' decomposition, when
adequately implemented, tends to converge in few iterations. In the language of our
algorithm, part of an explanation would be that the demand patterns _ d added to ~D
in each execution of Step 4 above are \important" or \essential", as well as being
\extremal".
A _nal point regarding Algorithm 1.2.1 is that neither Step 1 nor Step 2 need be
carried out exactly, except in the last iteration (in order to prove optimality). When
either step is performed approximately, then we cannot update the corresponding
bound (U or L) as indicated in the blueprint above. However, for example, performing
Step 2 approximately can lead to faster iterations, and at an early stage
an approximate solution can su_ce since all we are trying to do, at that point, is
to quickly improve the approximation to the set D provided by the existing (and
much smaller) set ~D. Our implementations run the exact adversarial problem only
at certain iterations, as will be discussed in Chapter 3.
CHAPTER 1. INTRODUCTION 14
1.3 Notation
Notation 1.3.1 In what follows, for any time period t, and any value z, we write
Wt(z) = maxf htz ; btz g:
We will refer to the inventory holding/backlogging cost in any period as the inventory
cost.
CHAPTER 2. THE STATIC PROBLEM 15
Chapter 2
The Static Problem
In this chapter we consider the static robust inventory problem, which is de_ned by:
min
u_0
XT
t=1
ctut + K(u) (2.1)
where for u = (u1; u2; : : : ; uT ) _ 0,
K(u) = max
XT
t=1
Wt(xt+1) (2.2)
s.t. xt+1 = xt + ut dt; 1 _ t _ T;
(d1; d2; : : : ; dT ) 2 D:
Here (2.2) is the adversarial problem: given orders u, the adversary chooses demands
d so as to maximize the total inventory cost. We study problem (2.1) not only because
it is of interest on its own right, but because it serves as a proof-of-concept for our
basic algorithmic ideas. In addition, by running the static model at every period
CHAPTER 2. THE STATIC PROBLEM 16
in a rolling horizon fashion, we obtain a dynamic strategy, though of course not a
basestock strategy. Our algorithms are especially e_ective on the static problem,
solving instances with thousands of time periods in a few seconds, and consequently
extensions of the static problem should also prove e_ciently solvable.
2.1 Prior work
In recent work, Bertsimas and Thiele [BT04] studied robust supply chain optimization
problems. One particular contribution lies in how they model the demand uncertainty
set D. In their model there are, for each time period t, numbers 0 _ _t _ _t and t,
such that 0 _ 1 _ 2 _ : : : _ T and t _ t1 + 1 (for 1 < t _ T). A vector
of demands d is in D if and only if there exist numbers z1; z2; : : : ; zT , such that for
1 _ t _ T,
dt = _t + _tzt; (2.3)
zt 2 [1; 1]; (2.4)
Xt
j=1
jzjj _ t: (2.5)
Here, the quantity _j is the \mean" or \nominal" demand at time j, and the model allows
for an absolute deviation of up to _j units away from the mean. Constraints (2.5)
constitute non-trivial requirements on the ensemble of all deviations. The method in
[BT04] handles startup costs and production capacities, but it is assumed that costs
CHAPTER 2. THE STATIC PROBLEM 17
are stationary, e.g. there are constants h, b and c such that ht = h; bt = b, and ct = c
for all t. If we extend the model in [BT04] to the general case, the approach used in
[BT04] formulates our basic inventory problem as the following linear program:
C_ = min
XT
t=1
( ctut + yt ) (2.6)
s.t.
yt _ ht
0
@x1 +
Xt
j=1
(uj _j) + At
1
At = 1; : : : T; (2.7)
yt _ bt
0
@x1 +
Xt
j=1
(_j uj) + At
1
At = 1; : : : T; (2.8)
u _ 0;
where for t = 1; : : : T,
At = max
Xt
j=1
_j_t
j (2.9)
s.t.
Xt
j=1
_t
j _ t;
0 _ _t
j _ 1; 1 _ j _ t:
Thus, LP (2.9) computes the maximum cumulative deviation away from the mean
demands, by time t, that model (2.3)-(2.5) allows. If we denote by ^_t
j (1 _ j _ t) the
optimal solution to LP (2.9), then constraint (2.7) yields the inventory holding cost
that would be incurred at time t if the demands at time 1; 2; : : : ; t took values
_1 _1^_t
1 ; _2 _2^_t
2 ; : : : ; _t _t^_t
t ;
CHAPTER 2. THE STATIC PROBLEM 18
whereas constraint (2.8) yields the backlogging cost that would be incurred at time t
if the demands at time 1; 2; : : : ; t took values
_1 + _1^_t
1 ; _2 + ^_2_t
2 ; : : : ; _t + _t^_t
t ;
e.g. in each case the deviations maximize the respective cost (see the discussion
following equation (13) in [BT04]). Also, note that when computing At and At0 for
t 6= t0 we will in general obtain di_erent implied demands, e.g. ^_t
i 6= ^_t0
i for i _ t; t0.
Linear program (2.6) should be contrasted with the \true" min-max problem:
R_ = min
u_0
R(u) (2.10)
where for u = (u1; u2; : : : ; uT ) _ 0,
R(u) = max
d;z;x
XT
t=1
( ctut + maxf htxt+1 ; btxt+1g ) (2.11)
s.t.
xt+1 = xt + ut dt; 1 _ t _ T;
dt = _t + _tzt;
zt 2 [1; 1];
Xt
j=1
jzjj _ t; 1 _ t _ T:
We have that R_ _ C_ and the gap can be large. However, [BT04] empirically shows
that in the case of stationary costs (2.6) provides an e_ective approximation to (2.10).
This is signi_cant because (2.11) is a non-convex optimization problem.
CHAPTER 2. THE STATIC PROBLEM 19
In addition, again in the case of stationary costs, it is shown in [BT04] that LP
(2.6) is essentially equivalent to an inventory problem with known demands, and as
a result the solution to the LP amounts to a basestock policy with basestock _t =
_t + bh
b+h(AtAt1), with A0 = 0. In fact, LP (2.6) can be solved \greedily" (every yt
simultaneously minimized) in the stationary case. Although the non-stationary case
is not considered in [BT04], we can say that the results from the stationary case do
not directly apply.
Next we review the results in [BGNV05] in the context of our basic inventory
problem. There are three ingredients in their model. First, motivated by prior work
[GW74], and by ideas from Control Theory [GSc71], the authors propose an a_ne
control algorithm. Namely, the algorithm in [BGNV05] will construct for each period
1 _ t _ T parameters ^_j
t (0 _ j _ t 1) and impose the control law:
ut = ^_t
0 +
Xt1
i=1
^_t
idi; (2.12)
in addition to nonnegativity of the ut (this extends the methodology described in
[BGGN04]). When used at time t, the values dj in (2.12) are the past demands.
Using (2.12), the inventory holding/backlogging cost inequalities for time t become:
yt _ ht
0
@x1 +
Xt1
i=1
0
@
Xt
j=i+1
^_j
i 1
1
Adi dt +
Xt
j=1
^_j
0
1
At = 1; : : : T; (2.13)
yt _ bt
0
@x1 +
Xt1
i=1
0
@1
Xt
j=i+1
^_j
i
1
Adi + dt
Xt
j=1
^_j
0
1
At = 1; : : : T; (2.14)
In addition, [BGNV05] posits that the quantities yt can be approximated (or at least,
CHAPTER 2. THE STATIC PROBLEM 20
upper-bounded) by a_ne functions of the past demand; the algorithm sets parameters
^ _t
j (0 _ j _ t1) with yt =
Pt1
j=1
^ _t
jdj + ^ _t
0 . Inserting this expression into (2.13), and
rearranging, we obtain:
0 _ htx1 +
Xt1
i=1
0
@ht
0
@
Xt
j=i+1
^_j
i 1
1
A ^ _t
i
1
Adi htdt + ht
Xt
j=1
^_j
0 ^ _t
0; (2.15)
which can be abbreviated as
0 _
Xt
i=1
Pt
i (^_; ^ _) di + Pt
0(^_; ^ _); (2.16)
where each Pt
i (^_; ^ _) is an a_ne function of ^_ and ^ _ (and similarly with (2.14)). The
algorithm in [BGNV05] chooses the ^_ and ^ _ values so that (2.15) holds for each
demand in the uncertainty set. This set is given by dt 2 [_t _t ; _t + _t], where
0 _ _t _ _t are known parameters. Thus, (2.16) holds for each allowable demand if
and only if there exists values ^_t
i , 1 _ i _ t, such that
0 _
Xt
i=1
_
Pt
i (^_; ^ _) _i + ^_t
i _i
_
+ Pt
0(^_; ^ _); (2.17)
^_t
i _ Pt
i (^_; ^ _) _ ^_t
i ; 1 _ i _ t: (2.18)
Inequalities (2.17) and (2.18), which are linear in ^_; ^ _; ^_ make up the system that is
enforced in [BGNV05] (there is an additional set of variables, similar to the ^_, that is
used to handle the backlogging inequalities (2.14)). Notice, as was the case in [BT04],
that this approach is conservative in that we may have _t
i 6= _t0
i for some i and t 6= t0,
i.e. the demands implied by some inequality (2.17) for some t may be di_erent from
CHAPTER 2. THE STATIC PROBLEM 21
those arising from some other period t0. Thus, the underlying min-max problem (over
the uncertainty set dt 2 [_t _t ; _t + _t] for each t) is being approximated.
Partly in order to overcome this conservatism, [BGNV05] introduces its third
ingredient. Given that the orders and the holding/backlogging costs are represented
as a_ne functions of the demands, the total cost can be described as an a_ne function
of the demands; let us write the total cost as Q0 +
P
t Qtdt where each Qt = Qt(^_; ^ _)
is itself an a_ne function of ^_; ^ _. To further limit the adversary, [BGNV05] models:
cost = max
(
Q0 +
X
t
Qtdt : d 2 E
)
; where (2.19)
E = fd : (d _)0S(d _) _ g : (2.20)
Here, ' denotes transpose, S is a symmetric, positive-de_nite T _ T matrix of known
values, > 0 is given and _ is the vector of values _t. Thus, (2.20) states that the
demands cannot simultaneously take values \far" from their nominal values _t. As
shown in [BGNV05], the system (2.19), (2.20) is equivalent to the problem:
cost = minE; (2.21)
subject to: Q0 +
X
t
_tQt +
_
Q0 S1 Q
_1=2
E _ 0: (2.22)
In this inequality, Q is the vector with entries Qt.
In summary, the approach used in [BGNV05] to handle the robust basic inventory
model solves the optimization problem with variables E, ^_, ^ _ and ^_; with objective
CHAPTER 2. THE STATIC PROBLEM 22
(2.21), and constraints (2.22), (2.17) and (2.18) (and nonnegativity of the orders,
