Siao-Leu Phouratsamay
email: siao-leu.phouratsamay@lip6.fr

Safia Kedad-Sidhoum
email: safia.kedad-sidhoum@lip6.fr

Fanny Pascual
email: fanny.pascual@lip6.fr

Two-level lot-sizing with inventory bounds

Keywords: Dynamic lot-sizing, inventory bounds, NP-hardness, dynamic programming

We study a two-level uncapacitated lot-sizing problem with inventory bounds that occurs in a supply chain composed of a supplier and a retailer. The first level with the demands is the retailer level and the second one is the supplier level. The aim is to minimize the cost of the supply chain so as to satisfy the demands when the quantity of item that can be held in inventory at each period is limited. The inventory bounds can be imposed at the retailer level, at the supplier level or at both levels. We propose a polynomial dynamic programming algorithm to solve this problem when the inventory bounds are set on the retailer level. When the inventory bounds are set on the supplier level, we show that the problem is NP-hard. We give a pseudo-polynomial algorithm which solves this problem when there are inventory bounds on both levels. In the case where demand lot-splitting is not allowed, i.e. each demand has to be satisfied by a single order, we prove that the uncapacitated lot-sizing problem with inventory bounds is strongly NP-hard. This implies that the two-level lot-sizing problems with inventory bounds are also strongly NP-hard when demand lot-splitting is considered.

Introduction

We consider a two-level supply chain with a supplier and a retailer. The retailer has to satisfy a demand for a single item over a finite planning horizon of discrete periods. In order to satisfy the demand, the retailer has to determine a replenishment plan over the horizon, i.e. when and how many units to order. In order to satisfy the retailer's replenishment plan, the supplier has to determine a production plan. Ordering units induce a fixed ordering cost and a unit ordering cost for both actors. Carrying units in the inventory induce a unit holding cost for both actors as well. Moreover, the quantity that can be held in inventory at each period can be limited, since inventory bounds can be imposed at the retailer level, at the supplier level or at both levels. The cost of the supply chain is given by the sum of the supplier and the retailer total costs. The two-level Uncapacitated Lot-Sizing (2ULS) problem with inventory bounds consists in determining the order and the inventory quantities at each period for both replenishment and production plans in order to satisfy the external demand while minimizing the total cost of the supply chain.

Literature review

For many practical applications, it is unreasonable to suppose that the inventory capacity is unlimited. In particular, the products that need temperature control or special storage facilities may have a limited storage capacity. This is for example the case in the pharmaceutical industry [2]. These constraints have led to the study of lot-sizing problems with inventory bounds.

The single level Uncapacitated Lot-Sizing problem with Inventory Bounds (ULS-IB) was first introduced by Love [START_REF] Love | Bounded production and inventory models with piecewise concave costs[END_REF]. He proves that the problem with piecewise concave ordering and holding costs and backlogging can be solved using an O(T 3 ) dynamic programming algorithm. Atamtürk and Küçükyavuz [2] study the ULS-IB 2ULS-IB S -NLS weakly NP-hard with demand time windows [START_REF] Jaruphongsa | Warehouse space capacity and delivery time window considerations in dynamic lot-sizing for a simple supply chain[END_REF] strongly NP-hard (Section 6) 2ULS-IB SR -NLS strongly NP-hard (Section 6)

This paper is organized as follows. A mathematical formulation for the single-item 2ULS problem with inventory bounds is provided in Section 2. Sections 3, 4 and 6 follow the results described in Tables 1 and2. In Section 5, we show that the 2ULS-IB SR problem is solvable using a pseudo-polynomial time algorithm.

Mathematical formulations

In this section, we describe the mathematical formulation of the 2ULS problem as well as the inventory bound constraints for the addressed problems.

Let T be the number of periods over the planning horizon. We denote by d t the demand at each period t for t ∈ {1, • • • , T}. The retailer's (resp. supplier's) costs are defined by a fixed ordering cost f R t (resp. f S t ), a unit ordering cost p R t (resp. p S t ) and a unit holding cost h R t (resp. h S t ) for t ∈ {1, • • • , T}. The retailer's (resp. supplier's) inventory bound at each period t is denoted by u R t (resp. u S t ) for t ∈ {1, • • • , T}. We denote by x R t (resp. x S t ) the quantity ordered by the retailer (resp. supplier) at period t, s R t (resp. s S t ) the retailer's (resp. supplier's) inventory level at the end of period t and y R t (resp. y S t ) the retailer's (resp. supplier's) setup variable, which is equal to 1 if an order occurs at period t at the retailer (resp. supplier) level and 0 otherwise. The 2ULS problem can be formulated as follows:

min T ∑ t=1 ( f S t y S t + p S t x S t + h S t s S t + f R t y R t + p R t x R t + h R t s R t ) (1)
s.t. s R t-1 + x R t = d t + s R t ∀t ∈ {1, . . . , T}, (2)
s S t-1 + x S t = x R t + s S t ∀t ∈ {1, . . . , T}, (3)
x R t ≤ M R t y R t ∀t ∈ {1, . . . , T}, (4)
x S t ≤ M S t y S t ∀t ∈ {1, . . . , T}, (5)
x S , x R , s S , s R ≥ 0 (6)

y S , y R ∈ {0, 1} T (7)
where

M R t = M S t = ∑ T i=t d i .
The supply chain total cost is given by (1). Constraints (2) (resp. ( 3)) are the inventory balance constraints at the retailer (resp. supplier) level. The supplier demand is the amount ordered at the retailer level at each period t. Constraints (4) and ( 5) force the setup variables to be equal to 1 if there is an order, i.e. if x R t > 0 or x S t > 0 respectively. The 2ULS problem can be viewed as a fixed charge network flow problem (see Figure 1) where the nodes represent the periods at each level. A source node is also considered in order to represent the total supplied quantity ∑ T i=1 d i . For each node, the vertical inflows are the ordering quantities and the horizontal outflows represent the inventory quantities. In addition, arcs representing the external demand at each period at the retailer level are considered. In the sequel, we will not represent the dummy node, and the arcs will be represented only if they are active (i.e. a vertical arc will be represented if the corresponding ordering quantity is positive, and a horizontal arc is represented if the corresponding inventory quantity is not null). In addition to this classical problem, we introduce inventory bounds constraints. The inventory bounds constraints for the 2ULS-IB R problem are given by:

s R t ≤ u R t ∀t ∈ {1, . . . , T}. (8)
The mathematical formulation can be strengthened by setting M R t to min(d t + u R t , ∑ T i=t d i ) in the constraint (4). Similarly, the inventory bounds constraints for the 2ULS-IB S problem are given by:

s S t ≤ u S t ∀t ∈ {1, . . . , T}. (9)
Similarly, parameter M S t can be replaced by min [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. The mathematical formulation of the 2ULS-IB SR problem is obtained by adding the constraints ( 8) and ( 9) to the mathematical formulation of the 2ULS problem.

(d t + u S t + u R t , ∑ T i=t d i ) in the constraint

The 2ULS-IB R problem

The 2ULS-IB R problem has been first studied by Hwang and Jung [START_REF] Hwang | Warehouse capacitated lot-sizing for a two-stage supply chain[END_REF]. We present structural properties of an optimal solution for the problem and propose an O(T 4 ) algorithm to solve it. Since the inventory bounds are only set at the retailer level, the superscript R will be omitted in the inventory bound parameter u R t that will be denoted by u t .

Zangwill [START_REF] Zangwill | A backlogging model and a multi-echelon model of a dynamic economic lot size production system-a network approach[END_REF] shows that there exists an optimal solution for the 2ULS problem that verifies the Zero Inventory Ordering (ZIO) property at each level, i.e. s i t-1 x i t = 0 for all t ∈ {1, . . . , T} and i ∈ {S, R}. As shown by [1,[START_REF] Toczyłowski | An o(t 2 ) algorithm for the lot-sizing problem with limited inventory levels[END_REF], the following assumption can be stated without loss of generality: Assumption 1. u t-1 ≤ u t + d t for all t ∈ {1, . . . , T}.

Dominance properties

In this section, we propose some dominance properties in order to determine an efficient solving approach such that there exists an optimal solution for the 2ULS-IB R problem that satisfies these properties.

We know that the ZIO property does not hold for the ULS-IB problem [START_REF] Love | Bounded production and inventory models with piecewise concave costs[END_REF][START_REF] Liu | Economic lot sizing problem with inventory bounds[END_REF]. Let us first show that for the 2ULS-IB R problem, the cost of the best solution in which the ZIO property is fulfilled at the retailer level may be arbitrarily large compared to the cost of an optimal solution in which the ZIO property is no required. Property 1. For the 2ULS-IB R problem, the cost of the best ZIO policy at the retailer level may be arbitrarily large compared to the cost of an optimal policy. Proof. Consider the following instance I:

T = 2, h S = p S = f R = h R = [0, 0], f S = [0, 1], p R = [0, 1], d = [0, B + 1] and u = [B, B],
where B is a large constant. The best solution satisfying the ZIO property at the retailer level is given by

x S = [d 2 , 0], x R = [0, d 2 ]
. The corresponding cost is B + 1 whereas the optimal non-ZIO solution is given by x S = [d 2 , 0], x R = [B, 1] inducing a cost equals to 1 (see Figure 2).

B+1 B+1 B+1 1 B+1 B 1 B 0 B+1 0 B+1
Best ZIO solution of cost B+1

Optimal (non-ZIO) solution of cost 1 Let us now give the definition of a block (Definition 3), previously introduced in [2, 1] for the single level case.

f S = [0, 1] h S = [0, 0] p S = [0, 0] f R = [0, 0] h R = [0, 0] p R = [0, 1] u = [B, B]
Definition 1 (Subplan). Let i and j be two periods such that 1 ≤ i ≤ j ≤ T. A subplan [i, j] is a partial solution at the retailer level of the 2ULS-IB R problem between the periods i and j defined by x R i , . . . , x R j .

Definition 2 (Regular subplan). Let i and j be two periods such that

1 ≤ i ≤ j ≤ T. A regular subplan [i, j] is a subplan [i, j] such that s R i-1 ∈ {0, u i-1 } and s R j ∈ {0, u j }.
Definition 3 (Block). Let i and j be two periods such that

1 ≤ i ≤ j ≤ T. Let α ∈ {0, u i-1 } and β ∈ {0, u j }. A block [i, j] α β is a regular subplan [i, j] where s R i-1 = α, s R j = β and 0 < s R t < u t for all t ∈ {i, . . . , j -1}.
In other words, a block [i, j] α β is a regular subplan [i, j] where the inventory quantities for each period between i and j are strictly positive but not equal to the inventory bound. A regular subplan is made of one or several blocks. Definition 4 (Order quantity). Let d tk = ∑ k i=t d i be the cumulative demand between periods t and k. The order quantity at the retailer level in a subplan [i, j] is given by X

ij = d ij -s R i-1 + s R j .
Observe that for a block

[i, j] α β , X ij = d ij -α + β.
Thereafter, we give some properties observed by an optimal solution for the 2ULS-IB R problem.

Theorem 1. Let P be the set of points that satisfy Constraints (2)-( 8) of the 2ULS-IB R problem. A point (y R , x R , s R , y S , x S , s S ) ∈ P is an extreme point if and only if:

1. there is at most one ordering period in every block [i, j] α β , for all

1 ≤ i ≤ j ≤ T, α ∈ {0, u i-1 }, β ∈ {0, u j }, 2.

the ZIO property holds at the supplier level.

This theorem follows from the properties related to the optimal flows in a fixed-charged network with concave costs [START_REF] Zangwill | Minimum concave cost flows in certain networks[END_REF]. As the 2ULS-IB R problem is a single source fixed-charged network with linear costs, Theorem 1 is a direct application of the characterization of extreme points in these networks. Property 2. An extreme point of P satisfies the following properties at the retailer level for all 1 ≤ i ≤ j ≤ T, α ∈ {0, u i-1 }, and β ∈ {0, u j }:

(i) If [i, j] 0
β is a block and if there is an ordering period in this block, then this ordering period is i.

(ii) If [i, j] α u j is a block and if there is an ordering period in this block, then this ordering period is j.

Proof. (i) If d i > 0, then period i is necessarily an ordering period since s R i-1 = 0. If d i = 0 and there is an ordering period in the block [i, j] 0 β , then we have s R i > 0 and period i is necessarily an ordering period since s R i-1 = 0.

(ii) Assume that the (unique

) ordering period is k in the block [i, j] α u j with i ≤ k ≤ j -1. From Assumption 1, we have u k ≤ u k+1 + d k+1 ≤ u k+2 + d k+2 + d k+1 ≤ • • • ≤ u j + d j + ∑ j-1 i=k+1 d i . Thus u k ≤ u j + d k+1,j .
There are two possible cases: Case 1:

u k = u j + d k+1,j . In this case, since s R j = u j , then s R k = u k which is not possible since [i, j] α u j is a block. Case 2: u j-1 < u j + d j .
In this case, it is not possible to have s R j = u j without having an additional ordering period in the block, which contradicts Theorem 1. So, the ordering period has to be at period j in a block [i, j] α u j .

Using Theorem 1 and Property 2, we propose a polynomial time algorithm to solve the 2ULS-IB R problem.

Recursion formula

In this section, we derive a polynomial backward dynamic programming algorithm to solve the 2ULS-IB R problem. The rationale of this algorithm is to compute a block decomposition of the retailer's replenishment plan such that the total cost of the supply chain is minimized using the dominance properties of the optimal solutions of the problem.

Let i, j be two periods such that 1 ≤ i ≤ j ≤ T. Let us consider a regular subplan [i, j] of a solution of the 2ULS-IB R problem. Notice that by definition [i, j] is not necessarily a block unless property 0 < s R k < u k for all k ∈ {i, . . . , j -1} holds. Assume that at period t, an order quantity Definition 4) is available at the supplier level, i.e. it is either ordered at period t or stored at period t -1 assuming the ZIO policy. The aim is to decompose the regular subplan [i, j] into blocks satisfying Property 2.

X ij = d ij -s R i-1 + s R j (see
An example is given in Figure 3. The graph represents subplans of a solution for an instance of the 2ULS-IB R problem where T = 4. At period t = 1, a quantity X 11 = d 1 + u 1 is available and at period t = 2, a quantity X 24 = d 24u 1 is available at the supplier level (it is also available at period 3). In this example, [2,[START_REF] Florian | Deterministic production planning: Algorithms and complexity[END_REF] The recursion formula will be defined in the following order given that [i, j] is an interval of periods: the cost of a block (φ

Computation of the cost of a block

Let φ αβ ijk be the cost of satisfying the demands of a block [i, j] α β with a single ordering at period k if it exists (Theorem 1), 1 ≤ i ≤ k ≤ j ≤ T. We will denote by φ αβ ij-the cost of the block [i, j] α β without an ordering period. Using Property 2(i), the cost φ 0β ijk is defined as follows:

φ 0β ijk =          f R i + p R i X ij + j ∑ n=i h R n (d n+1,j + β), if k = i and 0 < d ij + β ≤ u i 0, if i = j and d ij + β = 0 +∞, otherwise. If [i, j] u i-1 u j
is a block such that u i-1 = d ij + u j , then the demands of this block can be satisfied without setting any order between period i and j since s R i-1 = u i-1 . Otherwise, using Property 2(ii), a quantity X ij has to be ordered at period j. Moreover, we have to ensure that the inventory bounds constraints are not violated, and that the demands d i,j-1 can be covered by the inventory quantity at the end of period i -1, i.e. u i-1 > d i,j-1 . Thus, the cost φ u i-1 u j ijk of the block is given by:

φ u i-1 u j ijk =            ∑ j n=i h R n (u i-1 -d in + u j ), if u i-1 = d ij + u j f R k + p R k X ij + ∑ j-1 n=i h R n (u i-1 -d in ) + h R j u j , if k = j and d ij + u j > u i-1 > d i,j-1 +∞, otherwise. In a block [i, j] u i-1 0 , if u i-1 < d ij ,
then the quantity X ij can be ordered at any period k between i and j. In this case, we have to ensure that the inventory bounds constraints are not violated, that the inventory quantity u i-1 covers the demands before period k (u i-1 > d i,k-1 ), and that the demands after period k can be satisfied (u k ≥ d k+1,j ). The cost φ u i-1 0 ijk is then given by:

φ u i-1 0 ijk =          f R k + p R k X ij + ∑ k-1 n=i h R n (u i-1 -d in ) + ∑ j-1 n=k h R n d n+1,j , if d ij > u i-1 > d i,k-1 and u k ≥ d k+1,j ∑ j-1 n=i h R n (u i-1 -d n ), if u i-1 = d ij +∞, otherwise.

Computation of the cost of a regular subplan

Let G αβ tij be the optimal cost to cover the demands d ij of the regular subplan [i, j] where a quantity X ij is available at period t at the supplier level with 1 ≤ i ≤ j ≤ T and 1 ≤ t ≤ j, s R i-1 = α and s R j = β. Computing G αβ tij requires the computation of the costs of the blocks that compose the subplan [i, j]. Therefore, in order to compute G αβ tij efficiently, we first need to find a suitable decomposition of the subplan [i, j].

Let w αγβ tijk be the optimal cost of the regular subplan [i, j] where a quantity X ij is available at period t at the supplier level, k is a period of the first block of [i, j], and if there is an order in this first block, then this order occurs at period k. The aim is to find the last period l of the first block of the regular subplan [i, j] with a possible order at period k in an optimal solution. For sake of clarity, since the last period l of the first block is not known, we use the notation γ ∈ {0, 1} to represent the outgoing stock at the end of the first block. Parameter γ = 0 (resp. γ = 1) means that the outgoing stock at the end of the first block is null (resp. equal to the inventory bound). The index t, i, j, k, α, γ, β are such that 1

≤ i ≤ k < j ≤ T, 1 ≤ t ≤ k, s R i-1 = α, s R j = β and γ ∈ {0, 1}.
The cost w αγβ tijk is given by:

w αγβ tijk =      min k≤l<j {φ α0 ilk + G 0β k,l+1,j } + ∑ k-1 p=t h S p X ij , if γ = 0, min k≤l<j {φ αu l ilk + G u l β k,l+1,j } + ∑ k-1 p=t h S p X ij , if γ = 1. ( 10
)
In the case where γ = 1, the first term φ αu l ilk in Equation [START_REF] Liu | Economic lot sizing problem with inventory bounds[END_REF] represents the cost of satisfying the demands of the block [i, l] α u l with a possible order at period k. The second term G u l β k,l+1,j in Equation [START_REF] Liu | Economic lot sizing problem with inventory bounds[END_REF] represents the optimal cost for satisfying the demands of the regular subplan [l + 1, j] where s R l = u l and s R j = β and assuming that the quantity X l+1,j is available at period k at the supplier level. Finally, the last term ∑ k-1 p=t h S p X ij represents the cost of carrying X ij units from period t to period k at the supplier level. In the sequel, we define by l A representation of the cost w α1β tijk is depicted in Figure 4. There are X ij units available at period t at the supplier level. At the retailer level, [i, l] α u l is the first block of the regular subplan [i, j], where s R i-1 = α and s R j = β. A quantity X il is ordered at period k in this block. At the supplier level, a quantity X ij is stored from period t to period k and an amount X l+1,j is available at period k to satisfy the demands of the regular subplan [l + tijk where [i, j] is a regular subplan and an amount X ij is available at the supplier level at period t.

X ij X ij X l+1,j X il u l α β d i d k d l d l+1 d j φ αu l ilk k-1 p=t h S p X ij G u l β k,l+1,j
Let v αβ tij , with 1 ≤ i < j ≤ T and 1 ≤ t ≤ j, be the minimum cost of a regular subplan [i, j] composed of at least two blocks such that s R i-1 = α and s R j = β and assuming that a quantity X ij is available at period t at the supplier level, 1 ≤ t ≤ j. The cost v αβ tij is given by:

v αβ tij = min i≤k<j;γ∈{0,1} {w αγβ tijk }. (11)
From the definition of the cost v αβ tij , we can then compute the cost G αβ tij where the fixed ordering cost f S at the supplier level is not included. The cost G αβ tij is given by:

G αβ tij =    min { min t≤k≤j {φ αβ ijk + ∑ k-1 l=t h S l X ij }, v αβ tij }, if X ij > 0, φ αβ ij-, if X ij = 0. (12)
In Equation ( 12), the term min t≤k≤j {φ αβ ijk + ∑ k-1 l=t h S l X ij } represents the optimal cost of the regular subplan [i, j] when it is made of a single block, and v αβ tij is the optimal cost of [i, j] when it is composed of at least two blocks. If [i, j] α β is not a block or if k < i then the cost φ αβ ijk will be equal to +∞. Moreover, G αβ tij will be equal to +∞ if i > j or t > j.

Computation of the cost of the supply chain

Let C α ti be the optimal cost of the supply chain for satisfying the demands d iT of the regular subplan [i, T] where s R T = 0 and the first ordering period at the supplier level is larger than or equal to t, with 1 ≤ i ≤ T, 1 ≤ t ≤ T, α ∈ {0, u i-1 }. The total ordering quantity of the subplan is equal to X iT . The aim is to determine the ordering periods satisfying the ZIO property at the supplier level in order to satisfy the demands of the regular subplan [i, T].

If X iT = 0, then no order is required at the supplier level. The cost is then equal to the cost G α0 tiT of the subplan

[i, T] with s R i-1 = α: C α ti = G α0 tiT . ( 13
)
If X iT > 0, then the quantity X iT is completely or partially ordered at period t or at a subsequent period if no order occurs at period t at the supplier level. The cost C α ti is given by the following equation where 1(x) is a function which is equal to 0 if x = 0 and +∞ otherwise (see Figure 5).

C α ti = min {C α t+1,i , f S t + p S t X iT + G α0 tiT , (14)
min i≤l<T;γ∈{0,u l } {min( f S t + p S t X il , 1(X il )) + G αγ til + C γ t * +1,l+1 }},
where t * is the last ordering period at the retailer level in the regular subplan [i, l] (t * is determined and stored when the cost G αγ til is computed). The period t * + 1 is the earliest ordering period from which the supplier can order for satisfying the demands of the regular subplan [l + 1, T]. If there is no ordering period in the regular subplan [i, l], then we set t * = t. The first term in Equation ( 14) corresponds to the case where there is no order at period t at the supplier level. The second term in Equation ( 14) corresponds to the case where a quantity X iT is ordered at period t at the supplier level. Finally, the last term in Equation ( 14) represents the case where the quantity X iT is partially ordered at period t at the supplier level: a quantity X il > 0 is ordered at period t to satisfy the demands of the regular subplan [i, l] with i ≤ l < T. Because of the ZIO property at the supplier level, the supplier orders the quantity X l+1,T after period t * .

A representation of the last term of the cost C α ti is provided in Figure 5. In this figure, a quantity X il of units is ordered at period t at the supplier level for satisfying the demands of the regular subplan [i, l] where s R i-1 = α and s R l = γ ∈ {0, u l }.

X il 0 x R t * > 0 γ α β d i d t * d l d l+1 d T C γ t * +1,l+1 G αγ til min(f S t + p S t X il , 1(X il ))
Figure 5: Illustration of the cost C α ti where T] is a regular subplan and t is an ordering period at the supplier level.

Optimal cost.

The optimal cost of satisfying the demands of the regular subplan [1, T] is given by C 0 11 since s R 0 = 0 and the earliest order period at the supplier level is t = 1.

Complexity analysis

A pre-processing phase will consist of the computation of d 1j for all j ∈ {1, . . . , T} in O(T). Therefore, each d ij for all i, j ∈ {1, . . . , T} can be computed in constant time. Moreover, the holding costs required in the computation of each cost component is pre-computed and stored in O(T 2 ). Therefore, the cost φ αβ ijk can be computed and stored in O(T 3 ) for all i, j, k ∈ {1, . . . , T}. Besides, it takes O(T 4 ) time to compute and to store the costs G to O(T 4 ) by generalizing the result of Atamtürk and Küçükyavuz [2] for the 2ULS case. To this end, we first need to recall the observation of Atamtürk and Küçükyavuz [2] for the retailer level. We provide a detailed explanation of the observation in A.

Observation 1. For all 1 ≤ i ≤ k ≤ j ≤ T, α ∈ {0, u i-1 } and β ∈ {0, u j }, we have:

(i) if φ αβ ijk = +∞, then φ α β i-1,j,k = +∞ where α = 0 if α = 0 and α = u i-2 if α = u i-1 . (ii) if φ 0β ijk = +∞, then φ 0β i-1,j,k = +∞. (iii) if φ u i-1 β ijk = +∞, then: φ u i-2 β i-1,j,k =                      φ u i-1 β ijk + ∆ 1 , if u i-2 > d i-1,k-1 , u i-2 < u i-1 + d i-1 and d ij + β > u i-1 φ u i-1 β ijk + ∆ 2 , if u i-2 > d i-1,k-1 , u i-2 < u i-1 + d i-1 and d ij + β = u i-1 + ∞, otherwise where ∆ 1 = h R i-2 u i-2 + (p R k -∑ k-1 l=i-1 h R l )(u i-1 - u i-2 + d i-1 ) and ∆ 2 = f R k + ∆ 1 .
The observation below is deduced from Observation 1 and Assumption 1. It will be used to compute efficiently the cost w u i-1 γβ tijk . Observation 2. For fixed periods t, j, k such as

1 ≤ k ≤ j ≤ T and 1 ≤ t ≤ k, l u i-2 γβ t,i-1,j,k = l u i-1 γβ tijk for all 1 ≤ i ≤ k.
Proof. Let t, i, j, k be periods such as 1 ≤ i ≤ k ≤ j ≤ T and 1 ≤ t ≤ k. Let l be a period between k and j. Two cases have to be considered:

• Case 1: d il + β > u i-1 where β ∈ {0, u l }.
Let us show that for each period n ∈ {l + 1, . . . , k}, we have d in + β > u i-1 where β ∈ {0, u n }. Let n > l and β = u n (the proof for β = 0 is similar). We have

d in + u n = d i,n-1 + d n + u n ≥ d i,n-1 + u n-1 ≥ . . . ≥ d il + u l > u i-1
from Assumption 1. Thus, for fixed periods t, j, k and γ = 0 (the proof is similar for γ = 1), from Observation 1 and the previous remark, if u i-2 > d i-1,k-1 , u i-2 < u i-1 + d i-1 and there exists a period l between k and j such that d il > u i-1 , we have:

w u i-2 0β t,i-1,j,k = min k≤l<j {φ u i-2 0 i-1,l,k + G 0β k,l+1,j } + k-1 ∑ p=t h S p X i-1,j = min k≤l<j {φ u i-1 0 ilk + G 0β k,l+1,j } + k-1 ∑ p=t h S p X i-1,j + ∆ 1 (15) = w u i-1 0β tijk + k-1 ∑ p=t h S p (u i-1 -u i-1 + d i-1 ) + ∆ 1 (16)
Equation ( 15) comes from Observation 1 and the fact that ∆ 1 is independent of l. The ordering quantity X i-1,j of a regular subplan [i -1, j] consists of the ordering quantity X ij of a regular subplan [i, j] plus the quantity u i-1u i-2 + d i-1 which leads to Equation ( 16).

• Case 2:

d il + β = u i-1
where β ∈ {0, u l }. In that case, for all periods n < l, we cannot have d in + β > u i-1 otherwise we fall into the previous case. Moreover, for all periods n > l, since d il + β = u i-1 , the regular subplan [i, n] where s R i-1 = u i-1 and s R n ∈ {0, u n } cannot be a block. Then, similarly to the previous case, for fixed periods t, j, k and γ = 0, if

u i-2 > d i-1,k-1 , u i-2 < u i-1 + d i-1
and there exists a period l between k and j such that d il = u i-1 , we have:

w u i-2 0β t,i-1,j,k = w u i-1 0β tijk + k-1 ∑ p=t h S p (u i-1 -u i-1 + d i-1 ) + ∆ 2
A representation of this instance is given in Figure 6. The fixed ordering costs and the unit ordering costs of the supplier (resp. retailer) are indicated at the top (resp. bottom). At the supplier level, the quantities on the horizontal edges represent the inventory bounds.

Supplier

Retailer Observation 3. Note that if we order x S t = a t 2 at period t ∈ T 1 then the total ordering cost is equal to

f S 1 1 1 2S 2S 2S 2S p S 1- 1 a 1 1- 1 a 2 1- 1 a 3 1- 1 a 1 1- 1 a 2 1- 1 a 3 0 f R 2S 2S 2S 0 0 0 2S p R 0 0 0 0 0 0 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 a 1 a 1 a 2 a 2 a 3 a 3 0 0 0 0 0 0 S
f S t + p S t x S t = 1 + (1 -1/a t 2 )a t 2
which is exactly equal to x S t (in this case, the average cost of ordering one unit is equal to 1). If x S t < a t 2 at period t ∈ T 1 , then we have that the total ordering cost

f S t + p S t x S t = 1 + (1 -1/a t 2 )x S t = x S t + 1 -x S t /a t 2 > x S
t (in this case, the average cost of ordering one unit is larger than 1). From this observation, let us prove that there exists a solution for the 2ULS-IB S problem of cost at most S if and only if there exists a solution for the subset sum problem.

Assume that there exists a solution A of the subset sum problem. The following solution for the 2ULS-IB S problem is of cost at most S: for each element a i in the set A, the supplier orders a quantity a i at period t = 2i -1 and store it until period t + 1 (see Figure 7). The inventory bound is not exceeded since it is exactly equal to a i . From Observation 3 above, the cost of ordering a i units for each a i ∈ I at the supplier level is equal to a i . Since ∑ a i ∈I a i = S, the total cost at the supplier level is S. At period t = 2i, the retailer orders all the units and store them until period T. Since f R t = 0 for all t ∈ T 2 and h R t = p R t = 0 for all t ∈ {1, . . . , T}, the total cost at the retailer level is equal to 0. So, there exists a solution for the 2ULS-IB S problem of cost S. Assume that there exists a solution for the 2ULS-IB S problem with a cost of at most S. Since f S t = 2S for all t ∈ T 2 , the supplier has to order at period t ∈ T 1 , otherwise the cost will exceed S. Likewise, since f R t = 2S for all t ∈ T 1 , the retailer has to order at period t ∈ T 2 . In order to not exceed the inventory bounds, the supplier can store at most u S t = a t 2 units from period t to period t + 1. Thus, the quantity ordered by the supplier at period t ∈ T 1 is at most a t 2 . At period t ∈ T 2 , the retailer orders the units in the supplier's inventory and stores them until period T with a cost equal to 0. From Observation 3, if the supplier orders at period t, then x S t = a t 2 (this is the only way to order one unit with a cost of at most 1 so that the total cost is at most S). Thus, S = ∑ t∈T a t 2 where T is the set of periods where the supplier orders. This implies that there exists a solution to the subset sum problem.

The related lot-sizing problem with production capacity constraints instead of inventory bounds has been proved to be NP-hard [START_REF] Florian | Deterministic production planning: Algorithms and complexity[END_REF]. The instance parameter p S used in the proof of Theorem 2 is based on [START_REF] Florian | Deterministic production planning: Algorithms and complexity[END_REF]. Moreover, it is worth noticing the inventory bound at period t acts as a production capacity since the supplier cannot supply at t the ordered units.

The 2ULS-IB SR problem

We have proved that the 2ULS-IB S problem is NP-hard. By setting u R t = ∑ T t=1 d t , we can transform an instance of the 2ULS-IB S problem into an instance of the 2ULS-IB SR problem. Thus, the 2ULS-IB SR problem is at least as hard as the 2ULS-IB S problem. In this section, we describe a pseudo-polynomial dynamic programming algorithm to solve the 2ULS-IB SR problem. This proves that this problem is not strongly NP-hard.

Let s R t ∈ {0, 1, . . . , u R t } (resp. s S t ∈ {0, 1, . . . , u S t }) be the inventory quantity available at the end of period t at the retailer (resp. supplier) level. The principle of the algorithm is to consider all the possible values of the inventory quantity s R t (resp. s S ) at the retailer (resp. supplier) level. Notice that the ZIO property does not hold neither at the supplier nor at the retailer levels for the 2ULS-IB SR problem.

Let C i t (X) be the cost of ordering X units at level i ∈ {R, S} at period t, where the level R (resp. S) corresponds to the retailer (resp. supplier) level. The cost C i t (X) is given by:

C i t (X) = f i t + p i t X, if X > 0 0, otherwise.
We define V t (s R t-1 , s, s S t-1 , s) as the cost of satisfying the demand d t when:

s R t-1 (resp. s S t-1 ) units are stored at period t -1 and s (resp. s) units are stored at period t at the retailer (resp. supplier) level,

-X R = s + d t -s R t-1 (resp. X S = s + X R -s S t-1
) units are ordered at period t at the retailer (resp. supplier) level.

The cost V t (s R t-1 , s, s S t-1 , s) is defined by:

V t (s R t-1 , s, s S t-1 , s) = C R (X R ) + C S (X S ), if s ≤ u R t ,

Optimal cost

The optimal cost of satisfying the demands d 1T assuming that s R 0 = s S 0 = 0 is given by H 1 (0, 0). We initialize the recursion by setting H T+1 (s R t , s S t ) = 0 for all the values s R t-1 and s S i-1 ensuring feasibility.

Conclusion and future work

This paper considers two-level uncapacitated lot-sizing problems with inventory bounds, and provides a complexity analysis of these problems. We present an O(T 4 ) dynamic programming algorithm which solves the problem where the inventory bounds are set at the retailer level. When the inventory bounds are set at the supplier level, we prove that the problem is weakly NP-hard. We also present a pseudo-polynomial dynamic programming algorithm which ensures that this problem is not strongly NP-hard. Considering that lot-splitting is not allowed, we prove that the ULS problem with inventory bounds and the 2ULS problems where the inventory bounds are set either at the retailer level, or at the supplier level or at both of them are strongly NP-hard. It would be interesting for a future work to improve the running time of the algorithm solving the 2ULS-IB R problem. Moreover, the complexity of the 2ULS-IB S problem where the inventory bounds of the supplier are stationary is an open problem. Another interesting perspective is to consider that the supplier and the retailer share the same inventory facility. In this case, at each period, the inventory quantity of the supplier plus the one of the retailer cannot exceed a given inventory bound. The lot-sizing problems that have been studied is this paper consider a single item. It would also be interesting to study the case where there are several items. Finally, investigating efficient algorithms to solve the NP-hard 2ULS problems with inventory bounds is also a promising issue for practical applications. In particular, it would be interesting to consider the valid inequalities proposed by [3] for solving the two-level case. Since the fixed ordering cost is equal to b + 1 for all t ∈ T 2 ∪ {2m + 1, . . . , T}, we cannot order at these periods. Thus, all orders are set at period t ∈ T 1 . Since for each period t ∈ T 2 , d t = (mt/2)b, and since the inventory bound is mb, at most t 2 b units can be stored from period t ∈ T 2 to a period in T 1 . Since mb units have to be available at period 2m (otherwise the cost will be greater than b), then t 2 b units have to be stored from period t ∈ T 2 to period t + 1. So, we have to order b units at each period t ∈ T 1 for satisfying the demands d 2m+1,T (we cannot order all the units at period 2m -1 since p 2m-1 = 1 and the cost will be greater than b). Assuming the NLS constraint, each demand d t for all t ∈ {2m + 1, . . . , T} is satisfied by a single ordering period at t ∈ T 1 . So, there is a partition of the periods {2m + 1, . . . , T} into m sets (A 1 , . . . , A m ) such that ∑ i∈A j d i = b for all j ∈ {1, . . . , m}. Since each demand d t for all t ∈ {2m + 1, . . . , T} corresponds to an integer of (a 1 , . . . , a 3m ), this means that there exists a solution to the 3-Partition problem. Therefore, by Theorem 3, the 2ULS-IB S -NLS problem is also strongly NP-hard.

Proof of Corollary 3. The proof of this corollary is the same as the one of Corollary 2 for the 2ULS-IB S -NLS problem by adding any inventory bound at the retailer level (in an optimal solution no quantity will be stored at the retailer level).

Figure 1 :

 1 Figure 1: The 2ULS problem as a fixed charge network flow.

Figure 2 :

 2 Figure 2: Solutions for the instance I of the 2ULS-IB R problem.

Figure 3 :

 3 Figure 3: Subplans decomposition for an instance of the 2ULS-IB R problem where T = 4.

  αβ ijk ), the cost functions required to compute the cost of a regular subplan including the supplier's holding cost (w αγβ tijk , v αβ tij and G αβ tij ) and finally the cost of the supply chain (C α ti ).

  αγβ tijk the period achieving the minimum of the cost w αγβ tijk , i.e. l αγβ tijk = argmin w αγβ tijk .

Figure 4 :

 4 Figure 4: Illustration of the cost w α1β

  αβ tij and v αβ tij . Finally, the cost w αγβ tijk is computed in O(T 5 ), and then the time complexity of the dynamic programming algorithm based on the recursion formula (14) to compute C 0 11 is O(T 5 ). In what follows, we show how the time complexity of computing the cost w αγβ tijk can be improved from O(T 5 )

Figure 6 :

 6 Figure 6: Instance A of the 2ULS-IB S problem in the proof of Theorem 2 with n = 3, S = {a 1 , a 2 , a 3 }.

Figure 7 :

 7 Figure 7: Solution for the 2ULS-IB S problem in the proof of Theorem 2 with n = 3, S = {a 1 , a 2 , a 3 } and a 1 + a 3 = S.

Figure 9 :

 9 Figure 9: Solution for the ULS-IB-NLS problem in the proof of Theorem 3.

Figure 11 :

 11 Figure 11: Solution for the 2ULS-IB S -NLS problem in the proof of Corollary 2.

Table 2 :

 2 Complexity results without lot-splitting (NLS)

	Problem	Complexity
	ULS-NLS	strongly NP-hard (Section 6)
	2ULS-IB R -NLS	strongly NP-hard (Section 6)

  is a regular subplan composed of the blocks [2, 3] u 1 0 and[START_REF] Florian | Deterministic production planning: Algorithms and complexity[END_REF][START_REF] Florian | Deterministic production planning: Algorithms and complexity[END_REF] 0 0 .

	X11		X24
	Supplier	1		2	X24	3	X44	4
	X11				X23		X44
	Retailer	1	u1	2	u1 -d2	3		4
	d1	d2	d3	d4

  1, j]. The different terms of w

	α1β tijk are shown in Figure 4.
	X ij units
	are available
	Supplier	t	. . .	k	k+1
	Retailer		i . . .	k	. . .	l	l+1	. . .	j

  The period t * corresponds to the last ordering period in the regular subplan[i, l]. Since the ZIO property holds at the supplier level, we know that s S t * = 0. Then, the next likely candidate for an ordering period at the supplier is the period t * + 1 if it exists. The components in the definition of the cost C α ti are depicted in the figure.

	Supplier	t	. . .	t *	t * +1
	Retailer		i . . . t *	. . .	l	l+1	. . . T

  s ≤ u S t and s + s ≤ d tT +∞, otherwise. ) be the minimum cost of satisfying the demands d tT where s R t-1 (resp. s S t-1 ) units are stored at period t -1 at the retailer (resp. supplier) level. From the definition of the cost V t (s R

	Let H t (s R t-1 , s S t-1 t-1 , s, s S t-1 , s), we can compute the cost H t (s R t-1 , s S t-1 ) as follows:
	H t (s R t-1 , s S t-1 ) = min s∈S R t ,s∈S S t	{V t (s R t-1 , s, s S t-1 , s) + H t+1 (s, s)},
	where S R t = {max(0, s R t-1 -d t ), . . . , M R t }, with M R t = min(u R t , d tT ), and S S t = {max(0, s S t-1 -X R ), . . . , M S t }, with M S t = min(u S t , d tT ).

Acknowledgements This work was supported by FUI project RCSM "Risk, Credit Chain & Supply Chain Management", financed by Région Ile-de-France.

Contributions

In this paper, we study the complexity of single-item 2ULS problems with inventory bounds. We consider that either the supplier, the retailer, or both of them, have a limited inventory capacity. A polynomial dynamic programming algorithm is provided to solve the problem with inventory bounds at the retailer level. The problem is shown to be weakly NP-hard when the inventory bounds are imposed at the supplier level. A complexity analysis for this class of problem is also proposed under the no lot-splitting assumption where each demand has to be satisfied by a unique order. In the sequel, we will denote 2ULS-IB R (resp. 2ULS-IB S ), the problem where at each period, the inventory quantity at the retailer (resp. supplier) level cannot exceed the inventory bound. Finally, the 2ULS-IB SR problem is the problem where both the supplier and the retailer have a limited inventory capacity. The following tables summarize the complexity results for the variants of the 2ULS-IB problems considered: Table 1: Complexity results with lot-splitting Problem Complexity ULS-IB polynomial [2], [START_REF] Love | Bounded production and inventory models with piecewise concave costs[END_REF] 2ULS-IB R polynomial (Section 3) 2ULS-IB S polynomial with particular cost structure [START_REF] Jaruphongsa | Warehouse space capacity and delivery time window considerations in dynamic lot-sizing for a simple supply chain[END_REF] NP-hard (Section 4) 2ULS-IB SR NP-hard (Section 5)

or the assumption of Case 1 or the one of Case 2 are not satisfied, then we set w u i-2 0β

t,i-1,j,k = +∞. Therefore, for fixed periods t, j, k and 1 ≤ i ≤ k, we have

The cost w αγβ t,i-1,j,k can be computed from w αγβ tijk independently of period l by using Observation 1 and 2. For all 1 ≤ i ≤ T and given k, t, j, with i ≤ k < j ≤ T and 1 ≤ t ≤ k, for α ∈ {0, u i-1 }, γ ∈ {0, 1} and β ∈ {0, u j }, the cost w αγβ tijk can be done in O(T) time using the following equations:

Consequently, for fixed periods t, k, j, the cost w αγβ tijk with 1 ≤ i ≤ k can be computed in O(T) time. So, for all periods i, k, t, j such that 1 ≤ i ≤ k ≤ j ≤ T and 1 ≤ t ≤ k, the cost w αγβ tijk is computed in O(T 4 ) time. This implies that the algorithm which solves the 2ULS-IB R problem runs in O(T 4 ) time.

The 2ULS-IB S problem

Jaruphongsa et al. [START_REF] Jaruphongsa | Warehouse space capacity and delivery time window considerations in dynamic lot-sizing for a simple supply chain[END_REF] propose a polynomial time algorithm to solve the 2ULS-IB S problem with demand time window constraints and stationary inventory bounds. They consider that h S ≤ h R and that the fixed ordering cost and the unit ordering cost are decreasing. These specific costs make the problem solvable in polynomial time. In this section, we consider the 2ULS-IB S problem under a general cost structure and we prove that this problem is NP-hard.

Theorem 2. The 2ULS-IB S problem is NP-hard.

Proof. We prove that the 2ULS-IB S problem is NP-hard through a reduction from the subset sum problem, which is an NP-complete problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. An instance of the subset sum problem is given by an integer S and a set S of n integers (a 1 , . . . , a n ). The question is: does there exist a subset A ⊆ S such that ∑ a i ∈A a i = S?

We transform an instance of the subset sum problem into an instance of the 2ULS-IB S problem in the following way:

-T = 2n + 1. Let us denote by T 1 (resp. T 2 ) the set of odd (resp. even) periods in the set {1, . . . , 2n}.

-

to compute the optimal cost H 1 (0, 0). This bound constitutes the complexity of the dynamic programming algorithm. This is pseudo-polynomial, implying that the 2ULS-IB SR problem is not strongly NP-hard.

In the next section, we consider the 2ULS problems with inventory bounds assuming that the demand at the retailer level has to be covered by a single order.

Analysis of lot-sizing problems without lot-splitting

Jaruphongsa et al. [START_REF] Jaruphongsa | Warehouse space capacity and delivery time window considerations in dynamic lot-sizing for a simple supply chain[END_REF] introduce the problem where each demand must be satisfied by exactly one dispatch, i.e. the demand lot-splitting is not allowed at the retailer level. We called this constraint the No Lot-Splitting (NLS) constraint. In practice, this study is motivated by traceability requirements for the product where the management of the inventory and the transport can be improved if the demand is supplied from the supplier to the retailer by a single delivery. We note x R kt ≥ 0 the quantity of demand d t which is ordered at period k to satisfy a demand d t at the retailer level. We have

Definition 5 (NLS constraint). An ordering plan x R fulfills the NLS constraint if there does not exist two periods l and k with l < k ≤ t such that x R lt > 0 and x R kt > 0 for all periods t.

The 2ULS-IB R and the 2ULS-IB S problems with the NLS constraint are denoted by 2ULS-IB R -NLS and 2ULS-IB S -NLS respectively. Before studying the complexity of the latter problems, it is interesting to analyze the complexity of the single level problem with NLS constraint, that we denote by ULS-IB-NLS . The proofs of the following results are given in Appendix.

We consider T periods {1, . . . , T}. In the ULS-IB-NLS problem, ordering units at period t induces a fixed ordering cost f t and a unit ordering cost p t . Carrying units from period t to period t + 1 induces a holding cost h t . The total cost is given by the sum of the ordering and holding costs. The aim is to determine an ordering plan which satisfies the demands and which minimizes the total cost. We denote by x t the ordering quantity at period t, s t the inventory quantity at the end of period t and y t the binary (setup) variable which is equal to 1 if there is an order at period t and 0 otherwise. We say that the inventory bound is stationary if u t is constant throughout the planning horizon.

Appendix A

Proof of Observation 1. (i) If φ αβ ijk = +∞, then the regular subplan [i, j] with a single order at period k, s R i-1 = α and s R j = β is not a block. The violation(s) observed in the regular subplan [i, j] will also hold for the regular subplan

β is a block, and by Property 2(i) there is an ordering period at k = i. We consider the regular subplan [i -1, j] with an order at period k, s R i-2 = 0 and s R j = β. If d i-1 = 0, then the regular subplan [i -1, j] is not a block since s R i-2 = 0. If d i-1 > 0, then d i-1 could not be covered and thus the regular subplan

is a block with an ordering period k if it exists. We consider the regular subplan [i -1, j] with a single order at period k, s R i-2 = u i-2 and s R j = β. We want to determine if this regular subplan is a block.

We know that u i-2

and there must be an ordering period at k in the subplan

β . The retailer has to order a quantity u i-1

The inventory quantities between periods k and j remain unchanged in the block [i -1, j] u i-2 β . Since the demand d i-1 has to be covered by u i-2 , there are u i-1u i-2 + d i-1 less units in the inventory between periods i -1 and k -1. The cost φ

by considering these two cases: Case 1: Assume that a quantity X ij > 0 is ordered at period k in the block [i, j]

is given by: φ

Case 2: Assume that no ordering period occurs in the block [i, j] u i-1

β . Then, an additional fixed ordering cost f R k must be considered to compute the cost of the block [i -1, j] u i-2 β , which will be given by: φ

Appendix B

Proof of Theorem 3. We show that the 3-Partition problem, which is strongly NP-hard [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], can be reduced to the ULS-IB-NLS problem in polynomial time. Recall that an instance of the 3-Partition problem is given by an integer b and 3m integers (a 1 , . . . , a 3m ) such that ∑ 3m i=1 a i = mb and b/4 < a i < b/2 for all i ∈ {1, . . . , 3m}. The question is: does there exist a partition A 1 ∪ . . . ∪ A m of {1, . . . , 3m} such that ∑ i∈A j a i = b for all j ∈ {1, . . . , m}.

We transform an instance of the 3-Partition problem into an instance of the ULS-IB-NLS problem in the following way:

-T = 5m periods. Let us denote T 1 (resp. T 2 ) the set of odd (resp. even) periods in the set {1, . . . , 2m}.

-

, T}

h t = 0 for all t ∈ {1, . . . , T} -p t = 0 for all t ∈ T \{2m -1} and p 2m-1 = 1 -u t = mb for all t ∈ {1, . . . , T}

The instance is illustrated in Figure 8. The fixed ordering costs are indicated at the top of each period. The inventory bounds are represented on the horizontal edges. Let us show that there exists a solution to the ULS-IB-NLS problem of cost at most b if and only if there exists a solution to the 3-Partition problem.

Assume that there exists a solution (A 1 , . . . , A 3m ) of the 3-Partition problem. The cost of the following solution of the ULS-IB-NLS problem is b: at each period t ∈ T 1 , we order x t = ∑ i∈A (t+1)/2 a i + d t+1 = b + b m -t+1 2 units. Since p t = 0 for all t ∈ T 1 \{2m -1} and p 2m-1 = 1, it costs p 2m-1 x 2m-1 = p 2m-1 b = b to order these units. At each period t ∈ T 2 , the demand d t is satisfied and b units are stored which implies that there is exactly s t = t 2 b units in stock at the end of period t. At each period t ∈ T 1 , we store exactly a quantity s t-1 + x t = t-1 2 b + m -t-1 2 b = mb and the inventory bound u t is not exceeded. Each demand d t for all t < 2m is satisfied and there is mb units in stock at period 2m for satisfying the demands at period {2m + 1, . . . , T}. Since there is no holding cost, the cost of this solution is b. Note that this solution fulfills the NLS constraint since each demand is satisfied by a single order.

Assume now that there exists a solution to the ULS-IB-NLS problem of cost at most b (see Figure 9).

Proof of Corollary 1. We do a reduction from the ULS-IB-NLS problem, that is strongly NP-hard, as shown by Theorem 3. We transform an instance of the ULS-IB-NLS problem into the following instance of the 2ULS-IB R -NLS problem. The costs of the retailer are the ones of the ULS-IB-NLS problem, i.e. u R t = u t , f R t = f t , p R t = p t and h R t = h t for all t ∈ {1, . . . , T}. The supplier costs are given by f S t = h S t = p S t = 0 for all t ∈ {1, . . . , T}. The demands are the same as the ones of the ULS-IB-NLS problem. Since all the supplier's costs are 0, the cost of an optimal solution for the ULS-IB-NLS problem is equal to the optimal cost of its corresponding 2ULS-IB R -NLS instance (see Figure 10). By Theorem 3, the 2ULS-IB R -NLS problem is also strongly NP-hard.

Proof of Corollary 2. As in the proof of Corollary 1, we do a reduction from the ULS-IB-NLS problem, which is strongly NP-hard, as shown in Theorem 3. We transform an instance of the ULS-IB-NLS problem into the following instance of problem 2ULS-IB S -NLS . The supplier's costs are the ones of the ULS-IB-NLS problem, i.e. u S t = u t , f S t = f t , p S t = p t and h S t = h t for all t ∈ {1, . . . , T}. The retailer's costs are given by f R t = p R t = 0 for all t ∈ {1, . . . , T} and, for all t ∈ {1, . . . , T}, h R t = M, where M is a large number (we can fix M = ∑ T t=1 (h t + p t )). By this way, in an optimal solution of the 2ULS-IB S -NLS problem, no quantity will be stored at the retailer level. The demands are the same as the ones of the ULS-IB-NLS problem. Since f R t = p R t = 0, the cost of an optimal solution of the 2ULS-IB S -NLS problem is equal to the optimal cost of its corresponding ULS-IB-NLS problem. Figure 11 illustrates such a solution.