Solving the Stochastic Lot Sizing

Problem via Two Stage Stochastic

Programming and Re-optimization
Imran A. Khan
ID: iak26

Computational Optimization: Project Final Report

Saturday, December 15, 2018

Abstract
This paper describes a simplified resolution method for the stochastic Lot Sizing Problem when
it is formulated as a multi-stage stochastic program. From, theoretical results it is known that
multi-stage stochastic problems are highly difficult to solve, mainly due exponential grow of
scenario tree representation. A two stage stochastic formulation for the stochastic LSP with
uncertain demand is proposed, wherein the first stage decisions are those related to binary
decisions to produce or not during a certain period time, while second stage decisions are those
related to production quantities. The methodology is to solve an initial problem for the whole
time horizon and progressively solving similar smaller problems by fixing values of variables
for periods who have already gone. Two practical examples which follows this structure are
presented and used to conclude both for practical implementations and for theoretical purposes.

1|P age
Introduction
Production planning problems have been widely studied by engineers and mathematician from
an optimization point of view. The lot sizing problem is classic problem of this field, where the
main idea is to decide when and how much produce of a certain product according to a
framework which describes a finite planning horizon, some associated cost to starting
production, unitary production and holding. Also, it includes the condition to satisfy certain
demand at each period during the planning horizon. There are a lot of production markets which
lie under this kind of problem, even when it can be slightly modified according to specific
requirements of each particular industry.

Given that not always, indeed almost never, the demand can be anticipated, because the
industries are subject to market behaviour that is not stable at all impacting on that demands
mostly cannot be anticipated accurately. Thus, Shapiro et. al. [1] explain the importance of
stochastic modelling which takes into account the uncertainty in one or multiple parameters of
the model have been subject to study, and today, that kind of models are one the hot topics
because in general, it yields better representations of real life problems where the stochasticity
is a natural component of the system.

In particular, for the lot sizing problem, the stochasticity on the demand is a very common
approach studied, since there are multiple industries, namely the smallest ones, which lie on
environments wherein they have to deal with multiple factors that make the demand highly
complex to estimate, and even harder to find the exact amount of product of they need to
produce to satisfy demand requirements.

Therefore, the stochastic lot sizing problem is not a new model to explore, and indeed, further
sections will show multiple approaches developed to study the lot sizing problem with
stochastic demand and even more general approaches, namely stochastic costs and capacities.
However, it is known from Shapiro et. al. [1] that multi-stage stochastic programs are quite
difficult to solve, because of the curse of dimensionality. This paper aims to study a resolution
method, not yet implemented in the knowledge of the author, which tries to deal with the
exponential explosion of the size problem when the number of periods, composing the planning
horizon, grows up.

2|P age
Background
Even considering that the main objective of this paper is theorical, in terms to apply a resolution
method a different resolution method against the classical approaches made for this problem.
The structure of the decisions can be found at industrial levels.

Let consider a company which produces water bottles only, but with different sizes possibly.
The star product of the company are bottles of 600ml and consequently are the most important
product for the company. At the beginning of a year, the general manager claims to the 600ml
supervisor for a tentative planning of periods when he/she suggests that the bottles should be
manufactured, based on that the general manager decides the production of the remaining bottle
sizes.

The manager of 600ml bottles needs then to design a schedule for the general production
manager. However, it is known that demands for every period are not deterministic, thus he/she
will try to find one approach that could help in order to deliver a tentative production plan to
the general manager.

The structure of decisions arises because the production of different bottle sizes is carried out
in the production line. However, considering that 600ml bottles are the most representative
product for the company, there is a prioritization reserving the line for periods where it is
supposed as best moments to manufacture products to cover random demands. It is crucial to
generate this calendar, since the setup of the line, according to the bottle’s size takes long time
and is expensive.

As is natural, the calendar should be flexible, in order to adapt it to realizations of the random
demand, period by period. That is reason why the general manager asks for a general
production framework, where he only wants to set periods during which orders of 600ml bottles
will be released, the size of those orders is slight flexible and can be defined period by period
according of current inventory states and new information about coming future demands. One
important note is that there is no production capacity during a certain period, although it is a
quite hard assumption, it might be valid if the plant normally works during a subset of total
hours available during the period and just if it is needed, they can work extra hours to produce
some extra units needed to satisfy incoming demands.

Previous context leads a scheme such that the problem can be formulated as a two stage
stochastic program, wherein the first stage decisions are about to decide when the 600ml bottles

3|P age
will be produced, while the second stage decisions will be the amount of product manufactured
on a certain day settled by the first stage decisions, once the demand of the week (period) is
revealed.

However, two stage stochastic programming is not the best approach, because for this kind of
model we would need demands of every period being revealed simultaneously. Thus, the best
approach is a multi-stage stochastic model like has been already proposed for stochastic lot
sizing problem. Nonetheless, this paper is going to introduce a procedure which uses the two-
stage approach as a tool to find, not optimal, but very good solutions of the multi-stage problem,
which is very well known to have an exponential exploitation for the number of variables and
constraints according to the number of stages of the model. In fact, supervisor of 600ml bottles
production line already hired a consultant who tried to implement and solve the multi-stage
model, but unsuccessfully due to the size of the problem, they got an exponential number of
variables and constraints, this problem became intractable for commercial solvers available by
these days. The supervisor then has hired developers of this proposal in order to get the best
possible solution shortly.

Theoretically, this paper will show how two stage stochastic problem is used to solve the multi-
stage problem, efficiency of solution is analysed in terms of costs and computational effort
regarding what it is needed to solve the whole version of multi-stage stochastic lot sizing
problem, where the structure of decisions is sequential, namely, at the beginning of time 1 it is
decided if product will be manufactured or not, then the demand is revealed and according of
the initial decision, a production order is released; then, the period 2 starts and again it is
decided if during that period 𝑎𝑎 will be produced, after it the demand is revealed and
immediately after, a production order is released, this decision process is repeated until the end
of the time horizon is got.

Finally, further details about proposal will be highlighted in order to show how the proposal
fits into the decision framework stablished for water bottles production company.

Literature Review
As it was already mentioned, Lot Sizing Problem is a classic operations research problem that
has been tackled from different point of views, including particular characteristics like
production capacities, minimum service levels, among others. A very complete review of LSP
is presented by Glock et. al [2]. The most classic paper on LSP is the seminal paper of Wagner

4|P age
and Whitin [3] where a formalization of concepts and an exact algorithm to solve the
deterministic uncapacitated LSP is presented, and to this day is the best algorithm known to
get the optimal solution of the problem.

As Birge & Louveaux introduces on [4] from late 70’s, early 80’s, scientific started concerning
to formulate and solve models which consider uncertainty, because they noticed that it helps to
find solutions which are, in some sense, more robust regarding the deterministic ones.
However, Leclere et. al. [5] introduces the concept of curse of dimensionality which is related
to the fact that each additional stage makes the size model in order of magnitude; then, the
model becomes intractable very quickly. This notion is also depicted by Shapiro et. al. [1]
through the scenario tree representation. Also, although researchers during formers days
presented the deterministic approximation for a stochastic program via scenario representation,
it was just proved until 2002 by Kleywegt et.al. [6] that this formulation makes the
deterministic problem converging to the stochastic version better and better when the number
of scenarios is increased.

Thanks to the previous introduction, the extension of LSP to its stochastic version is trivial to
formulate, however, that is not the case when the issue is to find the optimal solution of that
problem.

During the previous decade, there were developed some approaches to find optimal solutions
of the problem efficiently. Most important of them are

• Haugen et. al. [7] introduce a decomposition method called progressive hedging as a
metaheuristic sub-routine which accelerates the solution of the big size problem when
it is formulated using scenario tree representation
• Guan et. al. [8] depict a branch and cut algorithm where valid inequalities and
optimality cuts are added, besides of a separation heuristic technique which accelerates
the convergence to the optimal solution
• Brandimarte [9] presents a scenario tree formulation for multi-item LSP that is solved
by using multiple heuristics, good solutions are obtained efficiently
• Guan [10] studies deeply the structure of the stochastic LSP and proposes an algorithm
that solves the problem with backloggings in polynomial time
• Piperagkas et. al. [11] presents the most recent approach, in the knowledge of the
author, which uses metaheuristics to improve previous results solving LSP, in terms of
computational times.

5|P age
Moreover, it is important to highlight that even for a widely studied problem like the LSP,
Glock et. al [2] present a complete literature review of the problem and they show how there
are not so many models considering stochasticity, previous papers summarize accurately the
state of the art for multi-stage stochastic programs for LSP.

Finally, the review made did not catch two stage stochastic programs to tackle the stochastic
LSP, that makes interesting the proposal presented through this project.

Problem Statement
This paper will study the classic Lot Sizing Problem under uncertain demand assumptions. The
general framework of the problem is a company which must decide about when and how much
produce in order to satisfy certain demands. However, it is common that demand is not
accurately known in advance, because of not always the companies have fixed amount
production contracts. Indeed, it happens only in minority of the cases. As it was mentioned,
this problem has been classically tackled using Multi-stage Stochastic Programming, where the
decisions are made period by period according to realizations of the demand on previous
period, and also, considering the probability distribution for future demands. Hereafter, a
classical formulation for stochastic lot sizing problem is shown.

For readers who are not closely related with inventory and production management, some basic
features of lot sizing are listed:

• The length of the planning horizon is known

• The demands for each period during the planning horizon are known
• There are multiple costs associated to
o Machine setup (fixed costs)
o Unitary production costs (variable costs)
o Holding costs (products can be stored to satisfy demand of future periods)
o For stochastic version, stockout costs appears because the production and
inventory available at some time moment cannot be enough to satisfy demand
during that period.

6|P age
Uncertainty

(𝑫𝑫𝑡𝑡 )𝑡𝑡∈𝕋𝕋 is a stochastic process which represents the demand’s behaviour. Moreover, a scenario
demand is defined as follows

𝐃𝐃(⋅) ≔ {𝐃𝐃1 , 𝐃𝐃2 , … , 𝐃𝐃T }

Also, it is assumed white noise on the demand stochastic process such that:

• The random variable {𝐃𝐃1 , 𝐃𝐃2 , … , 𝐃𝐃T } are independent between them
• The demand probability distribution of random variables {𝐃𝐃1 , 𝐃𝐃2 , … , 𝐃𝐃T } can be
continuous or discrete, but for continuous cases, there always exists a sequence of discrete
� 1t , 𝐃𝐃
random variables 𝐃𝐃 � 2t , … , 𝐃𝐃
� nt , such that 𝐃𝐃
� nt converges in probability and distribution to

𝐃𝐃t 1. This makes possibly to depict the scenario representation for the problem, presented
by Shapiro et. al. [1], and consequently it can be tackled by solving the corresponding
deterministic approximation of the stochastic program.

Note: For random variables bold letters will be used

Parameters

ft fixed cost paid if the company decides to produce at time 𝑡𝑡

ct unitary cost to produce one unit at time period 𝑡𝑡

ht periodic (monthly) holding cost for inventory stocked at time 𝑡𝑡

𝑟𝑟𝑡𝑡 price of product bought to an external supplier at time period 𝑡𝑡, also can be seen as a stockout
cost or a penalization when the demand cannot be fulfilled by production and inventory
available at time 𝑡𝑡

Decision variables

𝐗𝐗 t is the amount of product manufactured at time 𝑡𝑡

1 if at time period t the plant will manufacture products

𝐘𝐘t = �
0 otherwise

𝐒𝐒t is the inventory stocked at the time period 𝑡𝑡

1
Proof available at https://www.probabilitycourse.com/chapter7/7_2_4_convergence_in_distribution.php

7|P age
𝐁𝐁t is the amount of product bought to an external supplier at time 𝑡𝑡 to satisfy demand not
covered by internal production

Mathematical model

Objective function

𝑇𝑇

min � 𝑓𝑓𝑡𝑡 𝐘𝐘t + ct 𝐗𝐗 t + ht 𝐒𝐒t + rt 𝐁𝐁t (1)

𝑡𝑡=1

Subject to

𝐒𝐒t = 𝐒𝐒t−1 + 𝐗𝐗 t + 𝐁𝐁t − 𝐃𝐃t , ∀ t ∈ 𝕋𝕋 (2)

𝐒𝐒0 = S� 0 (3)
𝐗𝐗 t ≤ M𝐘𝐘t , ∀ t ∈ 𝕋𝕋 (4)
Non anticipativity constraints (5)
𝐗𝐗 t , 𝐒𝐒t , 𝐁𝐁t ≥ 0, 𝐘𝐘t ∈ {0,1}, ∀t ∈ 𝕋𝕋 (6)

The problem is to minimize total costs by (1), first component computes total fixed costs paid
due to line setup, second component is the total variable cost, third component is the total
inventory holding cost and finally the fourth component computes total costs related to
stockout. Constraints (2) and (3) ensure the correct inventory flow period by period. Constraints
(4) guarantee the production only can be carried if the current period is selected like non-zero
production period. Constraints (5) are little bit complex, since they are analysed by using
measure theory, because they would say that variables 𝐗𝐗 t , 𝐒𝐒t , 𝐁𝐁t are measurable with respect to
the sigma-field 2 generated by variable 𝐘𝐘t , that is a technical property needed to guarantee
existence of probability distributions. In order to hold simpler notation, it is only said that non
anticipativity constraint indicates the fact that amount production decisions are made, just once
the demands are revealed and 𝐘𝐘t variables have been already fixed, further details about non-
anticipativity constraints will be given shortly when the deterministic equivalent formulation
is presented. Finally, constraints (6) are variables nature.

Previously, some basics of Sample Average Approximation theory was introduced, that yields
a way to approximate a stochastic program as a deterministic one, with multiple scenarios

2
Sigma-field of a set of random variables is the smallest sigma-algebra such that the set of random variables are
measurable

8|P age
sampled from the known probability distributions of the random variables. In that order of
ideas, the problem (1)-(6) can de approximated deterministically by the problem posed on [7].

However, given the structure of information proposed in background, a mathematical detailed

structure is depicted hereafter

Information’s structure

The structured as the information is revealed is assumed that at certain instant the decision
maker stablish the periods from t = 1, … , T in which the plant will be producing according to
the information about distributions of demand during the whole time horizon. Once the
decision about in which timeslots the company will produce, the demand reveals
simultaneously for every period. Then, a scenario demand 𝐃𝐃(⋅) is got not step by step but the
values of demand for each period is known just after the decisions 𝐘𝐘t have been made.

Non-anticipativity constraints

The problem follows a tree decision structure as the example in Figure 1 shows 3, each branch
of the tree is a possible scenario for the whole time horizon, for this case there are a total of 8
scenarios (branches)

Figure 1. Scenario tree. Nodes represent information states. Paths from the root to leaves represent scenarios. Numbers along
the arcs represent conditional probabilities of moving to the next node. Bold numbers represent numerical values of the
process.

3
Figures 1 and 2 taken from Shapiro et. al. [1], pages 73 and 74

9|P age
One way to represent this structure is by using what is known as mesh or comb representation,
Figure 2 shows this structure, where parents nodes are decoupled into the same number of
possible scenarios.

Figure 2. Sequence of decisions for scenarios from Figure 1. Horizontal dotted lines represent the equations of
nonanticipativity

In the original structure of the problem, a single decision is made at the beginning of the time
horizon, in the example of the Figure 1, at time 2 there are two possible decisions according to
the realization of random variables during the first stage of the problem, and so on. In the mesh
representation, it is assumed that at every period, there are as many variables as number of
scenarios exist. Then, at first time period, there are 8 variables, although it is known that just
one decision is allowed. Thus, the mesh representation includes what in Figure 2 is shown
using dotted lines, those dotted lines imply that decisions for those scenarios must be forced to
be equal between them, that what it is called non-anticipativity constraints.

In the proposed examples, for first period time the total 8 variables created are forced to be
equal between them, that is depicted in Figure 2, because all variables associated to the first
period are connected themselves. At period 2, there are two possible decisions, according to
tree representation, but in the mesh, there are 8 variables again, then there 2 subsets of 4
variables which are forced to be equal between them.

Notation used to represent these constraints is as follows

xt = 𝔼𝔼�xt |ε[t] �

This means that variables xt is measured with respect to the history of random process ε[t] up
to time t. Practically, the constraints would be

10 | P a g e
 x11 = x12 = ⋯ = x18

x12 = x22 = x23 = x24 , x25 = x26 = x27 = x28

Although this is a small example, it is to note how an exponential number of variables and
constraints arise from mesh representation and non-anticipativity constraints, this is the
problem of multi-stage stochastic program becoming problems with small number of stages
and scenarios intractable.

Scenario representation formulation for Multi-stage stochastic program

Explanation of non-anticipativity constraints and exponential grow for the size of the problem
allows to tackle the remaining of the paper with a better understanding of the model. Mesh
formulation for the stochastic lot sizing problem would be

Objective function

𝑇𝑇

min � � pk (ft ytk ct xtk + ht stk + rt btk) (7)

𝑡𝑡=1 k∈𝕂𝕂

Subject to

stk = st−1,k + xtk + btk − dtk , ∀ t ∈ 𝕋𝕋, k ∈ 𝕂𝕂 (8)

s0,k = 0 (9)
xtk ≤ Mytk, ∀ t ∈ 𝕋𝕋, k ∈ 𝕂𝕂 (10)
ytk = ytk′ xtk = xtk′ ∀ k, k′ ∈ 𝕂𝕂, t ∈ Λt (11)
yt ∈ {0,1} ∀ t ∈ 𝕋𝕋; xtk, stk, btk ≥ 0 ∀t ∈ 𝕋𝕋, k ∈ 𝕂𝕂 (12)

Where 𝕂𝕂 is the set containing either the whole set of possible realizations of demand (i.e. this
set is non-countable when random variables are continuous) or a subset of scenarios sampled
from the known probability distributions of each period demand. 𝑝𝑝𝑘𝑘 is then the corresponding
probability occurrence of the scenario 𝑘𝑘 ∈ 𝕂𝕂.

The problem follows the same structure already explained, key thing to note is the definition
of set Λt which basically contains for every t the dotted lines shown in Figure 2, in other words,
that set will define which variables need to be equal between them at each time period

11 | P a g e
Also, note that variables btk, stk do not need non-anticipativity constraints, and the reason for
that is because those variables do not depend of realization of demand, they can be settled after
the demand is revealed.

Methodology
In this section additional formulations and concepts needed to show how the algorithm works
are introduced. Moreover, a pseudocode for the proposed algorithm is presented in order to
allow the reader implementing the algorithm for general multi-stage stochastic problems and
not only for the SLP.

Simplistic two-stage formulation

Previously, it was mentioned that two-stage is a simplification of the model. Figure 3 shows
the key difference between multi-stage and two-stage structures

Figure 3. Multi-stage decision structure for SLP vs. two-stage representation

In the two-stage approach, decisions which set the order sizes are made after the uncertain is
revealed. Then, two-stage is a relaxation of the multi-stage model, because non-anticipativity
constraints over xt variables are relaxed

12 | P a g e
Scenario representation for two-stage stochastic approach

Objective function

𝑇𝑇

min � 𝑓𝑓𝑡𝑡 yt + � pk (ct xtk + ht stk + rt btk) (13)

𝑡𝑡=1 k∈𝕂𝕂

Subject to

stk = st−1,k + xtk + btk − dtk , ∀ t ∈ 𝕋𝕋, k ∈ 𝕂𝕂 (14)

s0,k = 0 (15)
xtk ≤ Myt , ∀ t ∈ 𝕋𝕋, k ∈ 𝕂𝕂 (16)
yt ∈ {0,1} ∀ t ∈ 𝕋𝕋; xtk, stk, btk ≥ 0 ∀t ∈ 𝕋𝕋, k ∈ 𝕂𝕂 (17)

Clearly, the information’s structure is enforced by considering 𝑦𝑦𝑡𝑡 not indexed by scenarios, and
the corresponding non-anticipativity constraints are embedded within the constraints (16). A
possible mesh representation for this problem can be obtained by indexing 𝑦𝑦𝑡𝑡 for every scenario
𝑘𝑘 and enforcing non-anticipativity constraints for those variables as in equation (11). This kind
of approach is exploited by algorithms like progressive hedging, proposed by Rockafellar &
Wets [12]

Algorithm description

The proposal of this model is to iteratively solve the two-stage stochastic problem starting by
(13)-(17) and period by period re-optimize it by adding the constraints enforcing binary
variables of the previous periods to be equal of the results of precedent iterations. Meanwhile,
the continuous variable for order size xt are not fixed. The algorithm will repeat the previous
steps iteratively until the final period is got. Thus, there will be a total of T two stage stochastic
programs solved. This proposal tries to recover the dynamics over the decisions’ structure,
because at a certain time period can be reconsidered the decision yt for future periods according
to previous realizations of the demand.

Algorithm 1 describes the iterative procedure to define production planning schedule

13 | P a g e
 Input: Fixed costs, variable cost, unitary inventory holding cost,
stockout cost, length of time planning horizon, demand probability
distribution for each period
Output: A scheduling production planning for stochastic lot sizing
problem
Preprocessing:
Generate random variables based on demand probability distribution for
the deterministic representation of the model
Initialize:
Solve the two-stage stochastic program (13)-(17) and store 𝑦𝑦�1
Begin:
FOR t=1 to T
Generate scenario demands for periods 𝑡𝑡 + 1 to 𝑇𝑇
Generate the realization (single real value) of the demand
for period 𝑡𝑡
Create the two stage stochastic program (13)-(17) for periods
From 𝑡𝑡 to 𝑇𝑇
Fix the value of 𝑦𝑦𝑡𝑡 = 𝑦𝑦�𝑡𝑡 , where 𝑦𝑦�𝑡𝑡 comes from previous
iterations of the algorithm
Store value of 𝑥𝑥𝑡𝑡𝑡𝑡 which is equal for every 𝑘𝑘 ∈ 𝕂𝕂 because
for period 𝑡𝑡 was created just a single realization of the demand
Fix values of 𝑦𝑦𝑡𝑡+1 (except for 𝑡𝑡 = 𝑇𝑇) and 𝑥𝑥𝑡𝑡
END FOR

Algorithm 1.Two-stage and re-optimization algorithm to solve the SLP

Expected value of the designed algorithm

Since at every period t a realization of demand is chosen, the algorithm needs to be

implemented similarly to implementation of Monte Carlo simulation, at the end of n
simulations, it is possible to compute the average expected cost when Algorithm 1 is used to
approximate the solution of the multi-stage model.

Curse of dimensionality and potential of the approach

The two-stage stochastic formulation is a relaxation very weak in most of cases for multi-stage
stochastic programs. However, by applying methodology proposed in this paper, that relaxation
is useful to generate much more better solutions for the SLP. The curse of dimensionality and
potential of the proposal is depicted by the following example.

Let consider a case where the planning horizon is for 6 periods (months). At every time period,
the demand can take infinite number of values, because of the domain of continuous random
variables. However, in this example it is assumed that for every period 200 of sample are
generated to represent the behaviour of that random variable. Following the tree representation
of multi-stage stochastic problems, this model would have at least 2006 variables (total number
of scenarios), 64,000,000,000,000 variables. Clearly, a problem with this size is intractable for

14 | P a g e
current exact solution methods. On the other hand, the two-stage stochastic approach, can be
represented just by 200 ∗ 6 number of variables (scenarios). This number of variables, in
multiple cases, can be solved efficiently by free and commercial solvers. Proposal of Algorithm
1 is then to solve small size problems multiple times, instead to struggle the solver with a huge
unsolvable problem.

Results and discussion

The objectives of this section are manifold:

• An artificial example is created in order to compare the solution of the multi-stage

stochastic implementation versus the solution obtained by implementing Algorithm
XX.
• Comparing the potential number of variables and constraints for a for a possible real
life case study when a multi-stage stochastic model is implemented against the number
of variables and constraints for the proposed methodology
• An artificial case study is created to arise insights for future enhancements for this
technique and possible work extensions, also some conclusions are derived based on
this case study.

Section is divided in two: first part refers to a small instance which allows to compare solution
got by applying methods already mentioned, and the second part shows an artificial case study
useful to describe potential and limitations of the methodology proposed

Small instance

Let assume a problem where just 3 scenarios are supposed to occur at every period of time,
demand can be low (20), medium (40) or high (100). The structure of decisions is as follows:
At the very beginning, the production planer decides if he/she wants to release a production
order with its respective size. Then, the demand revels and a second decision moment comes
up, according to the demand of previous period the decision can be different (that’s the reason
why exist 𝑦𝑦2,𝐿𝐿 , 𝑦𝑦2,𝑀𝑀 , 𝑦𝑦2,𝐻𝐻 in figure XX). Same structure decision holds for the remaining periods
1
(4 in total). Then the total number of possible scenarios is 34 = 81 which are equiprobable 81

Fixed, variable and holding cost were randomly generated based on real life considerations as
for example: stockout cost > variable production cost

15 | P a g e
Figure 4. 81 scenarios instance for comparing MSSP vs TSSP+re-optimization

Multi-stage model

The formulation for the multi-stage stochastic problem follows the structure of equations (7)-
(12), for clarification, non-anticipativity constraints are shown for this tree when the mesh
representation is induced

𝑦𝑦1,𝑘𝑘 = 𝑦𝑦1,𝑘𝑘′, ∀ 𝑘𝑘, 𝑘𝑘 ′ ∈ 𝕂𝕂

𝑦𝑦2,(𝑘𝑘+(𝑛𝑛−1)∗27) = 𝑦𝑦2,(𝑘𝑘′+(𝑛𝑛−1)∗27) , ∀ 𝑘𝑘, 𝑘𝑘 ′ = {1, … ,27}, 𝑛𝑛 = {1,2,3}

𝑦𝑦3,(𝑘𝑘+(𝑛𝑛−1)∗9) = 𝑦𝑦3,(𝑘𝑘′+(𝑛𝑛−1)∗9) , ∀ 𝑘𝑘, 𝑘𝑘 ′ = {1, … ,9}, 𝑛𝑛 = {1, … ,9}

𝑦𝑦4,(𝑘𝑘+(𝑛𝑛−1)∗3) = 𝑦𝑦4,(𝑘𝑘′+(𝑛𝑛−1)∗3) , ∀ 𝑘𝑘, 𝑘𝑘 ′ = {1,2,3}, 𝑛𝑛 = {1, … ,27}

𝑥𝑥1,𝑘𝑘 = 𝑥𝑥1,𝑘𝑘′, ∀ 𝑘𝑘, 𝑘𝑘 ′ ∈ 𝕂𝕂

𝑥𝑥2,(𝑘𝑘+(𝑛𝑛−1)∗27) = 𝑥𝑥2,(𝑘𝑘′+(𝑛𝑛−1)∗27) , ∀ 𝑘𝑘, 𝑘𝑘 ′ = {1, … ,27}, 𝑛𝑛 = {1,2,3}

𝑥𝑥3,(𝑘𝑘+(𝑛𝑛−1)∗9) = 𝑥𝑥3,(𝑘𝑘′+(𝑛𝑛−1)∗9) , ∀ 𝑘𝑘, 𝑘𝑘 ′ = {1, … ,9}, 𝑛𝑛 = {1, … ,9}

𝑥𝑥4,(𝑘𝑘+(𝑛𝑛−1)∗3) = 𝑥𝑥4,(𝑘𝑘′+(𝑛𝑛−1)∗3) , ∀ 𝑘𝑘, 𝑘𝑘 ′ = {1,2,3}, 𝑛𝑛 = {1, … ,27}

For example, for period 1, there are 81 𝑦𝑦 variables, but it is needed to enforce all of them being
equal, because of the structure of decision presented in figure XX, for period 2 it is possible to
have 3 different values for 𝑦𝑦, according whether the demand of period 1 was low, medium or
high, this also considers what was mentioned on previous section (figure 1) when it goes deep
into the tree. Similar to 𝑦𝑦 variables, non-anticipativity constraints are also enforced for 𝑥𝑥
variables.

Two-stage approximation at time t

16 | P a g e
On the other hand, the problem which is solved at time t′ (iteration t′ of the algorithm) is the
following

Objective function

min � 𝑓𝑓𝑡𝑡 𝑦𝑦𝑡𝑡 + � 𝑝𝑝𝑘𝑘 (𝑐𝑐𝑡𝑡 𝑥𝑥𝑡𝑡𝑡𝑡 + ℎ𝑡𝑡 𝑠𝑠𝑡𝑡𝑡𝑡 + 𝑟𝑟𝑡𝑡 𝑏𝑏𝑡𝑡𝑡𝑡 )
𝑡𝑡=𝑡𝑡′ 𝑘𝑘∈𝕂𝕂

Subject to

𝑠𝑠𝑡𝑡𝑡𝑡 = 𝑠𝑠̅𝑡𝑡−1,𝑘𝑘 + 𝑥𝑥𝑡𝑡𝑡𝑡 − 𝑑𝑑𝑡𝑡𝑡𝑡 + 𝑏𝑏𝑡𝑡𝑡𝑡 , ∀ 𝑡𝑡 = 𝑡𝑡′, 𝑘𝑘 ∈ 𝕂𝕂

𝑠𝑠𝑡𝑡𝑡𝑡 = 𝑠𝑠𝑡𝑡−1,𝑘𝑘 + 𝑥𝑥𝑡𝑡𝑡𝑡 − 𝑑𝑑𝑡𝑡𝑡𝑡 + 𝑏𝑏𝑡𝑡𝑡𝑡 , ∀ 𝑡𝑡 = {𝑡𝑡 ′ + 1, … ,4}, 𝑘𝑘 ∈ 𝕂𝕂

𝑦𝑦𝑡𝑡′ = 𝑦𝑦�𝑡𝑡′

𝑥𝑥𝑡𝑡𝑡𝑡 ≤ 𝑀𝑀𝑦𝑦𝑡𝑡 , ∀ 𝑡𝑡 = {𝑡𝑡′, … , 𝑇𝑇}, 𝑘𝑘 ∈ 𝕂𝕂

𝑦𝑦𝑡𝑡 ∈ {0,1}, ∀ 𝑡𝑡 ∈ 𝕋𝕋,

𝑥𝑥𝑡𝑡𝑡𝑡 , 𝑠𝑠𝑡𝑡𝑡𝑡 , 𝑏𝑏𝑡𝑡𝑡𝑡 ≥ 0, ∀ 𝑡𝑡 ∈ 𝕋𝕋, 𝑘𝑘 ∈ 𝕂𝕂

This problem is exactly as described into the Algorithm XX and it is called TSSA (Two-Stage
Stochastic Approximation)

Comparative scheme between solutions for both models

Table 1 summarizes most important insights obtained form solving the small instance by
proposed algorithm and by solving the mesh formulation for multi-stage stochastic problems

Case study

Recalling over the idea introduced in background section about a company producing water
bottles where the most important product are bottles of 600ml, parameters were created
artificially, since there are no real data available.

Following structure respect assumptions that can be found in real life cases

• The planning horizon is taken as 12 months

• Random demands created from a uniform continuous distribution, but the mean of this
uniform distribution was also generated randomly based on on standard normal
distribution multiplied by 20 and adding 100 units. After that, the mean was multiplied
by 0.65 and 1.35 to create the extreme values of the uniform distribution

17 | P a g e
 This approach finally leads demands between 50 and 160 in average (for each period)
• Fixed setup cost is $10
• Fixed holding cost is $1 per unit
• Variable cost randomly generated between 1 and 4 for each time period
• Stockout costs are 1.5 times variable costs

Proposed algorithm: TSSA+Re-

Multistage stochastic problem solution
optimization
Expected cost after running 1000
simulations during 10 different times
Expected long term cost $906.41
$942.09 (3.9% more than the exact solution
via MSSP)
The solution (when and how much to
produce) cannot be read directly as in
Solution at the end sets exactly when and multistage problem. In this case the solution
how much it is needed to produce according of each simulation needs to be analysed by
to the realization of demand during grouping those simulations which suggest
previous periods producing during the same periods, that
would help to classify scenarios which yield
similar solutions
This problem is extremely hard to solve
when the number of scenarios is large
(common case because generally the For this small problem, there is no big
number of scenarios is just a sample from a difference between solving through both
continuous distribution and Kleywegt et. al. methods (in terms of computational effort),
[6] show that the number of scenarios the advantage of this algorithm is for large
needed for a good convergence of number of scenarios and stages
deterministic into stochastic version is
large)
Table 1. Comparative solutions between multi-stage stochastic programming and TSSP+re-optimization

18 | P a g e
Solution via Algorithm 1

After running the algorithm proposed in this paper for 1,000 simulations, the boxplot in Figure
5. Boxplot for expected cost simulation - water bottles company case study was obtained

Figure 5. Boxplot for expected cost simulation - water bottles company case study

Running the simple two stage program (without re-optimization) the solution was $2,492

After using re-optimization the mean of the runs was $2,809.

Then, the optimal solution lies between these two values, because the classic TSSP gives a lower bound
according to Shapiro et. al. [1], and the proposed resolution method leads an upper bound.

It is important to say that for future research would be helpful to include a risk measure, since in some
case the optimal value went up $3,200 (15% above the average)

19 | P a g e
Conclusions and future research
This paper has shown a short review for uncapacitated Stochastic Lot Sizing Problem which is
a very known problem in Operations Research field. Classical limitations to handle and solve
this problem is about the problem size (also called Curse of Dimensionality).

Let consider again the problem mentioned in section methodology where the number of
variables for multi-stage stochastic program is 64,000,000,000,000, while for the
corresponding two-stage stochastic approximation is 1,200. Current large scale optimization
techniques cannot handle problem with that astronomic number of variables. On the other hand,
let assume that problem with 1,200 can be solve reasonably quick e.g. one minute. If we have
6 periods, the total time to run a simulation would be 6 minutes and if the simulation is executed
1,000 times; the total needed time to give an approximated solution for the huge SLP would be
around 4 days. Although 4 days still seems like a long time period, if the planning horizon is
for example 6 months, 4 days are reasonable to get a good quality solution.

Computational experiments have shown that solution produced by proposed Algorithm 1 is an

upper bound for the optimal solution of the uncapacitated SLP. Although there is no
mathematical proof for this fact so far, that result is very intuitive because decisions about
periods when the company decides to manufacture the product, are not considering the entire
history of demand realizations, they can just consider a subset of the whole history demand,
which is given by the unique sample demanded generated at every step of the algorithm.
Indeed, this is the reason to run the algorithm for a large number of times, that allows to
consider 𝐃𝐃(⋅) ≔ {𝐃𝐃1 , 𝐃𝐃2 , … , 𝐃𝐃T } multiple number of scenarios as described in section
Uncertainty.

On the other hand, one weakness about the solution found by implementing the proposed
algorithm comes from the fact that order sizes cannot be directly read from the simulations
made, because order sizes generated by the algorithm are adjusted for every sample generated
during the simulation. However, for situations like water bottles company presented, the
Algorithm 1 is even representing the problem in a better way. This assertion is justified because
at the very beginning of the planning horizon, the periods when the products are going to be
manufactured (tentatively) can be obtained by running multiple simulations as it was made for
results shown above. After that, when the periods of the planning horizon start coming, one by
one, the algorithm can be executed once again by adding the history of demand realization at
every period, even further, new constraints can be added or changes in the distribution of

20 | P a g e
demand for future periods can be included. This becomes the solution procedure in a flexible
methodology in terms of practical implementations.

Recalling Figure 5, a very important study which should be made on future research is about
handling risk, the boxplot in the figure shows how by implementing the algorithm, the total
expected cost can vary sharply above the average, leading important loses when the worsts
scenarios reveal. Then, for highly risk averse managers, the methodology proposed in this
paper could not be useful.

Moreover, for study cases where the production planning schedule needs to be fixed completely
at the beginning of the planning horizon, again this methodology is not completely useful, but
still can be adapted. The extension needed for the algorithm, as a future research, is about
classifying the scenarios once the simulation is done. Ideally, it would be possible to analyse
and group those scenarios which yield similar solutions, this can help to define a policy for the
order size according to scenario features.

The last, and possibly the most important, conclusion is that this methodology deserves to be
studied in detail to adapt it for generic multi-stage stochastic problems. It was already
mentioned that two-stage stochastic programming is always a valid relaxation for multi-stage
stochastic problems. Then, a better comprehension about tightness of bounds and number of
simulations would be highly important to stablish ‘TSSP + re-optimization’ as a methodology
to solve large scale problems, which in general are known for being unsolvable.

21 | P a g e
References

[1] A. Shapiro, D. Dentcheva and A. Ruszczyński, Lectures on stochastic programming: modeling

and theory, Society for Industrial and Applied Mathematics, 2009.

[2] C. H. Glock, E. H. Grosse and J. M. Ries, "The lot sizing problem: A tertiary study," International
Journal of Production Economics, pp. 39-51, 2014.

[3] H. M. Wagner and T. M. Whitin, "Dynamic version of the economic lot size model," Management
science, pp. 89-96, 1958.

[4] J. Birge and F. Louveaux, Introduction to stochastic programming, Springer Science & Business
Media., 2011.

[5] V. Leclere, F. Pacaud and T. Rigaut, "CERMICS Lab," 14 03 2017. [Online]. Available:
http://cermics.enpc.fr/~delara/TEACHING/VL_MPRO_DP.pdf.

[6] A. J. Kleywegt, A. Shapiro and T. Homem-de-Mello, "The sample average approximation method
for stochastic discrete optimization," SIAM Journal on Optimization, pp. 479-502, 2002.

[7] K. K. Haugen, A. Løkketangen and D. L. Woodruff, "Progressive hedging as a meta-heuristic

applied to stochastic lot-sizing," European Journal of Operational Research, pp. 116-122, 2001.

[8] Y. Guan, S. Ahmed, G. L. Nemhauser and A. J. Miller, "A branch-and-cut algorithm for the
stochastic uncapacitated lot-sizing problem," Mathematical Programming, pp. 55-84, 2006.

[9] P. Brandimarte, "Multi-item capacitated lot-sizing with demand uncertainty.," International

Journal of Production Research, pp. 2997-3022, 2006.

[10] Y. Guan, "Stochastic lot-sizing with backlogging," Journal of Global Optimization, pp. 651-678,
2011.

[11] G. S. Piperagkas, I. Konstantaras, K. Skouri and K. E. Parsopoulos, "Solving the stochastic

dynamic lot-sizing problem through nature-inspired heuristics," Computers & Operations
Research, pp. 1555-1565, 2012.

22 | P a g e