1 Introduction

Supply chain problems consist in determining when and how much to produce in a production site in order to satisfy certain demands considering that the places in which production occurs and the places in which these products are required can be in different localities. In such problems the transportation decision consists in determining the amount to transport in each time period. As a consequence, the production of goods and their transportation to the retailers is a common problem faced by many industries and is an essential feature of a supply chain.

The one-warehouse multi-retailer problem (OWMR) is one such example. It considers a single production site that replenishes multiple retailers over a finite time horizon. Each retailer has a time varying deterministic demand for each period in the time horizon and there is no capacity limitation over the amount manufactured by the production site and the amount transported to the retailers.

In recent years, most of the literature dealing with the OWMR has concentrated on the development of approximation algorithms for the problem. Some examples are Levi et al. (2006, 2008) and Stauffer et al. (2011). One of the few exceptions has been Solyali and Süral (2012), in which the authors compared both theoretically and experimentally MIP formulations for the problem and they could solve to optimality problems with up to 150 retailers and 30 time periods. They considered two situations: the first in which there is no initial stock available at the beginning of the planning horizon and the second in which initial stock is available. Our work complements their study in the sense that we show how even larger instances can be solved more effectively using a standard mixed-integer programming (MIP) solver through reformulation. As larger formulations become less effective as soon as we increase the size of the problems, we look for alternative approaches that may provide an effective way to tackle the problem computationally.

Some problems studied in the literature can be considered as special cases of the OWMR, such as the uncapacitated two-level lot-sizing and the joint replenishment problem. The uncapacitated two-level lot-sizing, studied in Melo and Wolsey (2010), is a polynomial solvable special case of the OWMR in which only one retailer is present. The uncapacitated two-level lot-sizing also has an alternative extension denoted two-echelon lot-sizing problem in series with intermediate demands, see Zhang et al. (2012), in which demands are present at the retailer and also at the production site. The authors proposed inequalities describing a partial description of the convex hull of solutions which could also be obtained as special cases of the simple dicut inequalities studied in Rardin and Wolsey (1993). These inequalities can alternatively be obtained from the projection of the multicommodity formulation into the original space of variables. The joint replenishment problem, see Arkin et al. (1989) and  Robinson et al. (2009), is an NP-Hard special case of the OWMR in which storage is not allowed at the production site.

Some extensions of the one-warehouse multi-retailer problem, or problems that can be considered as such, are also treated in the literature. An obvious extension of the problem is the multi-item version, studied in Federgruen and Tzur (1999). The OWMR also appears as subproblems of certain multi-production site problems as the ones considered in Melo and Wolsey (2012), Park (2005) and Sambasivan and Yahya (2005). It also appears as a subproblem in the topic of integration of production and routing decisions, see Adulyasak et al. (2015) for a recent review.

The remainder of this document is organized as follows. In Sect.  2, we give a formal description of the one-warehouse multi-retailer problem, present a standard formulation for the problem and show an equivalent problem. In Sect.  3, the formulations available in the literature for the OWMR are described. In Sect.  4, we present some formulations that were not yet applied specifically to the OWMR, although certain of them were already applied to extensions of the problem. A theoretical analysis of the linear relaxation bounds provided by the different formulations is devised in Sect. 5. In Sect. 6, we report on computational experiments that were carried out to measure the performance of the different approaches. Some final remarks are drawn in Sect. 7.

2 The one-warehouse multi-retailer problem

In this section we formally introduce the one-warehouse multi-retailer problem and describe a standard MIP formulation for the problem. We also show how the OWMR can be seen as a multi-item uncapacitated two-level lot-sizing with joint setup costs at level zero.

In the one-warehouse multi-retailer problem there is one production site which replenishes multiple (NC) retailers over a finite time horizon of NT periods. Each retailer has a time varying deterministic demand \(d^c_t\) for each period t in the time horizon, and in addition we define \(d^c_{kl}= \sum _{t=k}^l d^c_t\). The amount produced by the production site and the amount transported from the production site to the retailers are unlimited. Production at a given period t incurs a fixed cost (\(f^{0}_t\)) plus an additional cost per unit produced (\(\tilde{p}^{0}_t\)). Transportation from the production site to a retailer incurs a fixed transportation cost (\(f^{c}_t\)) plus a per unit transportation cost (\(\tilde{p}^{c}_t\)). Storage is allowed at a cost both at the production site (\(h^0_t\)) and at the retailers (\(h^{c}_t\)). In this work, we assume there are no initial and final stocks. Also, we consider nonnegative costs and demands.

Consider variables \(x^{0}_t\) to be the amount produced at the production site in period t, \(x^{c}_t\) to be the amount transported from the production site to retailer c in period t, \(s^{0}_t\) to be the amount in stock at the production site at the end of period t, \(s^{c}_t\) to be the amount in stock at retailer c at the end of period t, \(y_t\) to be equal to 1 if production occurs at the production site in period t and to be 0 otherwise, and \(Y^{c}_t\) to be equal to 1 if transportation occurs between the production site and retailer c in period t and to be 0 otherwise. A standard formulation for the problem is given by

$$\begin{aligned} (OWMR) \, \,&\min \sum _{t=1}^{NT} \left( h^{0}_t s^{0}_t+ \tilde{p}^{0}_t x^{0}_t + f^{0}_t y_t\right) + \sum _{c=1}^{NC}\sum _{t=1}^{NT} \left( h^{c}_t s^{c}_t + \tilde{p}^{c}_tx^{c}_t + f^{c}_tY^{c}_t\right) \end{aligned}$$
(1)
$$\begin{aligned}&s^{0}_{t-1}+x^{0}_t= \sum _{c=1}^{NC}x^{c}_t + s^{0}_t, \ \ \ \forall \ 1\le t \le NT, \end{aligned}$$
(2)
$$\begin{aligned}&s^{c}_{t-1}+ x^{c}_t= d^{c}_t + s^{c}_t, \ \ \ \forall \ 1\le c \le NC, \ 1 \le t\le NT, \end{aligned}$$
(3)
$$\begin{aligned}&x^{0}_t \le M y_t, \ \ \ \forall \ 1\le t \le NT, \end{aligned}$$
(4)
$$\begin{aligned}&x^{c}_t \le M Y^{c}_t, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le NT, \end{aligned}$$
(5)
$$\begin{aligned}&s,x \in {\mathbb {R}}^{(NC+1) \times NT}_+, \end{aligned}$$
(6)
$$\begin{aligned}&y \in \{0,1\}^{NT},\ Y \in \{0,1\}^{ NC\times NT}. \end{aligned}$$
(7)

The objective function minimizes the total cost which includes variable and fixed setup production costs at the production site, variable and fixed transportation costs to the retailers, and storage costs at the production site and at the retailers. Constraints (2) are balance constraints for the production site. Constraints (3) are balance constraints for the retailers. Constraints (4) and (5) are setup constraints respectively for the production site and for the retailers. Constraints (6) and (7) are nonnegativity and integrality constraints on the variables.

Observation 1

As with other production planning problems (see Pochet and Wolsey 2006) the stock variables can be removed from the objective function and an equivalent one can be obtained as \(\sum _{t=1}^{NT} (p^{0}_t x^{0}_t + f^{0}_t y_t) + \sum _{t=1}^{NT} \sum _{c=1}^{NC} ( p^{c}_tx^{c}_t + f^{c}_tY^{c}_t) + K\).

Observe that from constraints (2) we get \(s^0_t = \sum _{k=t+1}^{NT}(\sum _{c=1}^{NC} x^{c}_k - x^0_k)\) and from constraints (3) we obtain \( s^{c}_t = \sum _{k=t+1}^{NT} (d^c_k - x^{c}_k)\). The new objective function can therefore be obtained by simply performing substitutions and algebraic manipulations in order to eliminate variables \(s^0\) and \(s^{c}\) from the original objective function. The new coefficients are \(p^0_t = \tilde{p}^0_t - \sum _{k=1}^{t-1} h^0_k\) and \(p^{c}_t = \tilde{p}^{c}_t + \sum _{k=1}^{t-1}(h^0_k-h^1_k)\), and the constant is \(K=\sum _{t=1}^{NT}d^c_t\sum _{k=1}^{t-1}h_k\).

The one-warehouse multi-retailer problem can be represented by a fixed charge network flow problem, as illustrated in Fig.  1 for a case with two retailers and four time periods. In the figure, each square node (0, t) represents the period t at the production site while circle nodes (c, t), \(1 \le c \le NC\), represent the period t at retailer c.

Fig. 1
figure 1

Network flow representation for the OWMR

Full size image

Observation 2

According to the property of extreme flows in a network (see Zangwill 1969), there exists an optimal solution such that: (a) if there is a positive entering stock at the production site/retailer in the beginning of period t, the flow arriving as production/transportation at t is equal to zero; (b) if there is positive transportation from the production site to a retailer c in period s it is used to satisfy demand from period s to period t, with \(s \le t \le NT\).

This well-known property is key in the validity of the shortest path reformulation available in the literature which will be presented in Sect. 3.3.

2.1 An equivalent problem: multi-item uncapacitated two-level lot-sizing with joint setup costs at level zero

Note that the one-warehouse multi-retailer problem is equivalent to a multi-item uncapacitated production in series two-level lot-sizing with joint setup costs at level zero. Define variables \(x^{0c}_t\) to be the amount produced for retailer (or item) c at the production site (or at level zero) in period t, and \(s^{0c}_t\) to be the stock for retailer (or item) c at the production site (or at level zero) at the end of period t. This equivalent problem can be formulated as

$$\begin{aligned} (OWMR') \, \,&\min \sum _{t=1}^{NT} \left( p^{0}_t x^{0}_t + f^{0}_t y_t\right) + \sum _{c=1}^{NC}\sum _{t=1}^{NT} \left( p^{c}_tx^{c}_t + f^{c}_tY^{c}_t\right) \end{aligned}$$
(8)
$$\begin{aligned}&s^{0c}_{t-1}+x^{0c}_t= x^{c}_t + s^{0c}_t, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le NT, \end{aligned}$$
(9)
$$\begin{aligned}&s^{c}_{t-1}+ x^{c}_t= d^{c}_t + s^{c}_t, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le NT, \end{aligned}$$
(10)
$$\begin{aligned}&x^{0c}_t \le M y_t, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le NT, \end{aligned}$$
(11)
$$\begin{aligned}&x^{c}_t \le M Y^{c}_t, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le NT, \end{aligned}$$
(12)
$$\begin{aligned}&\sum _{c=1}^{NC}x^{0c}_t = x^{0}_t, \ \ \ \forall \ 1\le t \le NT, \end{aligned}$$
(13)
$$\begin{aligned}&s^0,s,x^0,x \in {\mathbb {R}}^{NC \times NT}_+, \end{aligned}$$
(14)
$$\begin{aligned}&y \in \{0,1\}^{NT},\ Y \in \{0,1\}^{ NC\times NT}. \end{aligned}$$
(15)

Note that OWMR’ can also be seen as an extended formulation for OWMR.

Observation 3

The feasible region of \(OWMR'\) can be written as

$$\begin{aligned} X^{OWMR'}=\bigcap _{c=1}^{NC} X^{2LS_c}, \end{aligned}$$

in which \(X^{2LS_c}\) is the set of feasible solutions of the uncapacitated two-level lot-sizing (\(2LS_c\)) related to retailer c, and the sets are only linked by the y variables.

$$\begin{aligned} (2LS_c) \, \,&s^{0c}_{t-1}+x^{0c}_t= x^{c}_t + s^{0c}_t, \ \ \ \forall \ 1\le t \le NT , \end{aligned}$$
(16)
$$\begin{aligned}&s^{c}_{t-1}+ x^{c}_t= d^{c}_t + s^{c}_t, \ \ \ \forall \ 1\le t \le NT, \end{aligned}$$
(17)
$$\begin{aligned}&x^{0c}_t \le M y_t, \ \ \ \forall \ 1\le t \le NT, \end{aligned}$$
(18)
$$\begin{aligned}&x^{c}_t \le M Y^{c}_t \ \ \ \forall \ 1\le t \le NT, \end{aligned}$$
(19)
$$\begin{aligned}&s^0,s,x^0,x \in {\mathbb {R}}^{NT}_+, \end{aligned}$$
(20)
$$\begin{aligned}&y \in \{0,1\}^{NT},\ Y^{c} \in \{0,1\}^{NT}. \end{aligned}$$
(21)

3 Formulations previously considered for the OWMR

An approach that has been applied very successfully to several production planning problems, including the one-warehouse multi-retailer problem, is the use of extended formulations. In this section, we describe the formulations studied in Solyali and Süral (2012), which are the strengthened echelon stock formulation and the two best performing formulations for the problem, namely the transportation and the shortest path formulations.

3.1 Strengthened echelon stock formulation

A strengthened echelon stock (SES) formulation was presented by Solyali and Süral (2012) in which facility location reformulations are introduced for two relaxed uncapacitated lot-sizing sets. Consider the relaxed set obtained via the aggregation of all retailers, i.e. summing up constraints (2) with (3) for every retailer \(c = 1,\ldots , NC\), namely:

$$\begin{aligned}&\sum _{c=0}^{NC} s^{c}_{t-1} + x^0_t = \sum _{c=1}^{NC}d^c_t + \sum _{c=0}^{NC} s^{c}_{t}, \ \ \ \forall \ 1\le t \le NT, \end{aligned}$$
(22)
$$\begin{aligned}&x^0_t \le M y_t, \ \ \ \forall \ 1\le t \le NT. \end{aligned}$$
(23)

In this way, the formulation is obtained with reformulations for the set implied by (22) and (23) and for the one formed by (3) and (5).

Consider variables \(w^0_{kt}\) to be the amount produced at the warehouse in period k to satisfy demand of period t and \(w^c_{kt}\), for \(1 \le c \le NC\), to be the amount transported to retailer c in period k to satisfy its demand of period t. The strengthened echelon stock formulation can be described as

$$\begin{aligned} (SES) \, \,&\min \sum _{t=1}^{NT} \left( {p}^{0}_t x^{0}_t + f^{0}_t y_t\right) + \sum _{c=1}^{NC}\sum _{t=1}^{NT} \left( {p}^{c}_tx^{c}_t + f^{c}_tY^{c}_t\right) \end{aligned}$$
(24)
$$\begin{aligned}&\sum _{k=1}^t w^0_{kt}= \sum _{c=1}^{NC}d^{c}_t, \ \ \ \forall \ 1 \le t\le NT, \end{aligned}$$
(25)
$$\begin{aligned}&\sum _{r=1}^{t} \sum _{k=r}^{NT} w^{0}_{rk} \ge \sum _{c=1}^{NC}\sum _{r=1}^{t} \sum _{k=r}^{NT} w^{c}_{rk}, \ \ \ \forall \ 1\le t \le NT, \end{aligned}$$
(26)
$$\begin{aligned}&\sum _{k=1}^t w^c_{kt}= d^{c}_t, \ \ \ \forall \ 1\le c \le NC, \ 1 \le t\le NT, \end{aligned}$$
(27)
$$\begin{aligned}&w^{0}_{kt} \le \sum _{c=1}^{NC} d^c_t y_k, \ \ \ \forall \ 1\le k \le t \le NT, \end{aligned}$$
(28)
$$\begin{aligned}&w^{c}_{kt} \le d^c_t Y^{c}_k, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le t \le NT, \end{aligned}$$
(29)
$$\begin{aligned}&x^c_t = \sum _{k=t}^{NT} w^{c}_{tk}, \ \ \ \forall \ 0\le c \le NC,\ 1\le t \le NT, \end{aligned}$$
(30)
$$\begin{aligned}&w \in {\mathbb {R}}^{(NC+1) \times NT \times NT}_+, \end{aligned}$$
(31)
$$\begin{aligned}&y \in \{0,1\}^{NT},\ Y \in \{0,1\}^{ NC\times NT}. \end{aligned}$$
(32)

The objective function (24) minimizes the total cost, since it is equivalent to (1) when summed up with a constant K as stated in Observation 1. Constraints (25) state that all the demands must be produced at the warehouse. Constraints (26) enforce the amount produced at the warehouse until a given period to be greater or equal than the amount transported to the retailers until that period. Constraints (27) guarantee that the demand of a retailer for a given period should be transported from the warehouse at most in that period. Constraints (28) and (29) set the binary variables to one in case production and/or transportation occurs. Constraints (30) link the facility location variables to the original ones. Constraints (31) and (32) are nonnegativity and integrality constraints on the variables. This formulation has \(O(NC \times NT^2)\) variables and \(O(NC \times NT^2)\) constraints.

3.2 Transportation formulation

Consider variables \(\lambda ^c_{skt}\) to be the amount produced at the production site in period s and transported to retailer c in period k to satisfy its demand of period t. Levi et al. (2008) formulated the OWMR with a transportation formulation as

$$\begin{aligned} (TR) \, \,&\min \sum _{t=1}^{NT} \left( p^{0}_t x^{0}_t + f^{0}_t y_t\right) + \sum _{c=1}^{NC}\sum _{t=1}^{NT} \left( p^{c}_tx^{c}_t + f^{c}_tY^{c}_t\right) \end{aligned}$$
(33)
$$\begin{aligned}&\sum _{s=1}^{t}\sum _{k=s}^{t} \lambda ^c_{skt} = d^c_t, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le NT, \end{aligned}$$
(34)
$$\begin{aligned}&\sum _{k=s}^{t} \lambda ^c_{skt} \le y_s d^c_t, \ \ \ \forall \ 1\le c \le NC,\ 1\le s \le t \le NT, \end{aligned}$$
(35)
$$\begin{aligned}&\sum _{s=1}^{k}\lambda ^c_{skt} \le Y^{c}_k d^c_t, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le t \le NT, \end{aligned}$$
(36)
$$\begin{aligned}&\sum _{c=1}^{NC}\sum _{k=s}^{NT}\sum _{t=k}^{NT} \lambda ^c_{skt} = x^{0}_s, \ \ \ \forall \ 1\le s \le NT, \end{aligned}$$
(37)
$$\begin{aligned}&\sum _{s=1}^k\sum _{t=k}^{NT} \lambda ^c_{skt} = x^{c}_k, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le NT, \end{aligned}$$
(38)
$$\begin{aligned}&\lambda \in {\mathbb {R}}_+^{NC \times NT\times NT\times NT},\end{aligned}$$
(39)
$$\begin{aligned}&\ y \in \{0,1\}^{NT},\ Y \in [0,1]^{NC\times NT}. \end{aligned}$$
(40)

The objective function (33) plus a constant K is equivalent to (1). Constraints (34) ensure each of the demands is satisfied. Constraints (35) and (36) set the binary variables to one in case production and/or transportation occur. Constraints (37) and (38) link the transportation variables to the original ones. Observe that the Y variables are not constrained to be integer since it was shown in Solyali and Süral (2012) that there exist solutions in which they assume integer values when the y variables are integral, and [0, 1] denotes the set of real values between zero and one. This formulation has \(O(NC \times NT^3)\) variables and \(O(NC \times NT^2)\) constraints, disconsidering the nonnegativity restrictions.

3.3 Shortest path formulation

The shortest path formulation was presented in Solyali and Süral (2012) and it relies on the properties of the extreme optimal solutions described in Observation 2. Consider variables \(\phi ^c_{srt}\) to be the fraction of \(d^c_{rt}\) manufactured by the production site in s and sent to retailer c in period r to satisfy its demands from period r to t. The formulation can thus be described as

$$\begin{aligned} (SP) \, \,&\min \sum _{t=1}^{NT} \left( p^{0}_t x^{0}_t + f^{0}_t y_t\right) + \sum _{c=1}^{NC}\sum _{t=1}^{NT} \left( p^{c}_tx^{c}_t + f^{c}_tY^{c}_t\right) \end{aligned}$$
(41)
$$\begin{aligned}&\sum _{t=1}^{NT}\phi ^c_{11t}= 1, \ \ \ \forall \ 1\le c \le NC, \end{aligned}$$
(42)
$$\begin{aligned}&\sum _{r=1}^{t-1}\sum _{s=r}^{t-1} \phi ^c_{rs,t-1} - \sum _{r=1}^{t}\sum _{s=t}^{NT} \phi ^c_{rts} = 0, \ \ \ \forall \ 1\le c \le NC,\ 2\le t \le NT, \end{aligned}$$
(43)
$$\begin{aligned}&\sum _{r=s: d^c_{rt}>0}^{t} \phi ^c_{srt} \le y_s, \ \ \ \forall \ 1\le c \le NC,\ 1\le s \le t \le NT, \end{aligned}$$
(44)
$$\begin{aligned}&\sum _{s=1: d^c_{rt}>0}^{r} \phi ^c_{srt} \le Y^{c}_r, \ \ \ \forall \ 1\le c \le NC,\ 1\le r \le t \le NT, \end{aligned}$$
(45)
$$\begin{aligned}&\sum _{c=1}^{NC}\sum _{r=s}^{NT}\sum _{t=r}^{NT} d^c_{rt}\phi ^c_{srt} = x^{0}_s, \ \ \ \forall \ 1\le s \le NT, \end{aligned}$$
(46)
$$\begin{aligned}&\sum _{s=1}^r\sum _{t=r}^{NT} d^c_{rt}\phi ^c_{srt} = x^{c}_r, \ \ \ \forall \ 1\le c \le NC,\ 1\le r \le NT, \end{aligned}$$
(47)
$$\begin{aligned}&\phi \in [0,1]^{NC \times NT\times NT\times NT}, \end{aligned}$$
(48)
$$\begin{aligned}&\ y \in \{0,1\}^{NT},\ Y \in [0,1]^{NC\times NT}. \end{aligned}$$
(49)

The objective function (41) plus a constant K is equivalent to (1). Constraints (42) and (43) are shortest path related restrictions. Constraints (44) and (45) set the binary variables to one in case production/transportation occurs. Constraints (46) and (47) link the shortest path variables to the original ones. Observe that the Y variables are not constrained to be integer since it was shown in Solyali and Süral (2012) that they assume integer values when the y variables are integral. Similar to the transportation formulation, SP has \(O(NC \times NT^3)\) variables and \(O(NC \times NT^2)\) constraints, disconsidering the nonnegativity restrictions.

4 Formulations newly introduced for the OWMR

In this section, we present several formulations that were not yet applied specifically to the one-warehouse multi-retailer problem, although certain of them have already been considered when dealing to a more general extension of the OWMR in Melo and Wolsey (2012). We describe a Wagner–Whitin based formulation, a two-level lot-sizing Wagner–Whitin based formulation, a multicommodity formulation and a two-level lot-sizing dynamic programming based formulation.

4.1 Wagner–Whitin based formulation

The Wagner–Whitin based formulation was applied to a generalization of the OWMR in Melo and Wolsey (2010) and is obtained by adding (l, S)-inequalities for certain relaxations of the original problem. The formulation can be described as

$$\begin{aligned} (ESWW) \, \,&\min \sum _{t=1}^{NT} \left( p^{0}_t x^{0}_t + f^{0}_t y_t\right) + \sum _{c=1}^{NC}\sum _{t=1}^{NT} \left( p^{c}_tx^{c}_t + f^{c}_tY^{c}_t\right) \nonumber \\&(2)-(7) \end{aligned}$$
(50)
$$\begin{aligned}&\sum _{c=0}^{NC} s^{c}_{t-1} + \sum _{k=t}^l \sum _{c=1}^{NC} d^c_{kl} y_k \ge \sum _{c=1}^{NC} d^c_{tl}, \ \ \ \forall \ 1\le t \le l \le NT, \end{aligned}$$
(51)
$$\begin{aligned}&s^{c}_{t-1} + \sum _{k=t}^l d^c_{kl} Y^c_k \ge d^c_{tl}, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le l \le NT. \end{aligned}$$
(52)

In this formulation, inequalities (51) are Wagner–Whitin (l, S)-inequalities for the relaxed uncapacitated lot-sizing set implied by (22) and (23). Inequalities (52) are Wagner–Whitin (l, S)-inequalities for each of the retailers, i.e. the sets implied by constraints (3) and (5). This formulation has \(O(NC\times NT)\) variables and \(O(NC \times NT^2)\) constraints.

4.2 Two-level lot-sizing Wagner–Whitin based formulation

The two-level lot-sizing Wagner–Whitin based formulation is obtained by adding Wagner–Whitin (l, S)-inequalities for certain relaxations of \(OWMR'\) together with a family of dicut inequalities and, as far as we know, it was not yet used for any variation of the OWMR. The formulation can be described as

$$\begin{aligned} (2LSWW) \, \,&\min \sum _{t=1}^{NT} \left( p^{0}_t x^{0}_t + f^{0}_t y_t \right) + \sum _{c=1}^{NC}\sum _{t=1}^{NT} \left( p^{c}_tx^{c}_t + f^{c}_tY^{c}_t \right) \nonumber \\&(9)-(15) \end{aligned}$$
(53)
$$\begin{aligned}&s^{0c}_{t-1} + s^{c}_{t-1} + \sum _{k=t}^l d^c_{kl} y_k \ge d^c_{tl}, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le l \le NT, \end{aligned}$$
(54)
$$\begin{aligned}&s^{c}_{t-1} + \sum _{k=t}^l d^c_{kl} Y^c_k \ge d^c_{tl}, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le l \le NT, \end{aligned}$$
(55)
$$\begin{aligned}&s^{0c}_{t-1} + s^{c}_{t-1} + \sum _{k=t}^j d^c_{kl} y_k + \sum _{k=j+1}^l d^c_{kl} Y^c_k \ge d^c_{tl}, \quad \forall \ 1\le c \le NC,\ 1\le t \le j < l \le NT. \end{aligned}$$
(56)

Inequalities (54) are Wagner–Whitin (l, S)-inequalities for the relaxed set obtained by summing up constraints (9) and (10), namely

$$\begin{aligned}&\displaystyle s^{0c}_{t-1} + s^{c}_{t-1} + x^{0c}_t = d^c_{t} + s^{0c}_t + s^{c}_t, \ \ \ \forall \ 1 \le t \le NT,\end{aligned}$$
(57)
$$\begin{aligned}&\displaystyle x^{0}_t \le M y_t, \ \ \ \forall \ 1\le t \le NT. \end{aligned}$$
(58)

Inequalities (55), similarly to (52), are Wagner–Whitin (l, S)-inequalities for each of the retailers. Inequalities (56) are simple dicut inequalities that generalize the (l, S)-inequalities for each two-level lot-sizing problem by considering production variables at both levels. They can be alternatively seen as special cases of the two-echelon inequalities of Zhang et al. (2012). This formulation has \(O(NC\times NT)\) variables and \(O(NC \times NT^3)\) constraints.

4.3 Multicommodity formulation

In a multicommodity formulation each demand \(d^{c}_t\) for the pair c, t is viewed as a distinct commodity. Consider variables \(w^{0c}_{kt}\) to be the amount produced at the production site in period k to satisfy demand of retailer c in period t, \(w^{1c}_{kt}\) to be the amount transported from the production site to retailer c in period k to satisfy demand of period t, \(\sigma ^{0c}_{kt}\) to be the amount stocked at the production site at the end of period k to satisfy demand of retailer c in period t, and \(\sigma ^{1c}_{kt}\) to be the amount stocked at retailer c at the end of period k to satisfy demand of period t. The multicommodity formulation can be described as

$$\begin{aligned} (MC) \, \,&\min \sum _{t=1}^{NT} \left( p^{0}_t x^{0}_t + f^{0}_t y_t \right) + \sum _{c=1}^{NC}\sum _{t=1}^{NT} \left( p^{c}_tx^{c}_t + f^{c}_tY^{c}_t \right) \end{aligned}$$
(59)
$$\begin{aligned}&\sigma ^{0c}_{k-1,t} + w^{0c}_{kt} = w^{1c}_{kt} + \sigma ^{0c}_{kt}, \ \ \ \forall \ 1\le c \le NC,\ 1\le k\le t \le NT, \end{aligned}$$
(60)
$$\begin{aligned}&\sigma ^{1c}_{k-1,t} + w^{1c}_{kt} = \delta _{kt}d^c_t + (1- \delta _{kt})\sigma ^{1c}_{k,t}, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le t \le NT, \end{aligned}$$
(61)
$$\begin{aligned}&w^{0c}_{kt} \le y_k d^c_t, \ \ \ \forall \ 1\le c \le NC, \ 1\le k \le t \le NT, \end{aligned}$$
(62)
$$\begin{aligned}&w^{1c}_{kt} \le Y^{c}_k d^c_t, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le t \le NT, \end{aligned}$$
(63)
$$\begin{aligned}&\sum _{c=1}^{NC}\sum _{t=k}^{NT} w^{0c}_{kt} = x^{0}_k, \ \ \ \forall \ 1\le k \le NT, \end{aligned}$$
(64)
$$\begin{aligned}&\sum _{t=k}^{NT} w^{1c}_{kt} = x^{c}_k, \ \ \ \forall \ 1\le c \le NC, \ 1 \le k \le NT, \end{aligned}$$
(65)
$$\begin{aligned}&w^{0}, w^{1},\sigma ^0,\sigma ^1 \in {\mathbb {R}}_+^{NC \times NT\times NT} , \end{aligned}$$
(66)
$$\begin{aligned}&\ y \in \{0,1\}^{NT},\ Y \in [0,1]^{NC\times NT}, \end{aligned}$$
(67)

where \(\delta _{kt}\) is equal to one if \(k=t\) and zero otherwise. The objective function (59) plus a constant K is equivalent to (1). Constraints (60) are balance constraints for each commodity at the production site. Constraints (61) are balance constraints for each commodity at the retailers. Constraints (62) and (63) set the binary variables to one in case production/transportation occurs. Constraints (64) and (65) link the multicommodity variables to the original ones. This formulation has \(O(NC\times NT^2)\) variables and \(O(NC \times NT^2)\) constraints.

The result presented in Proposition 1 is similar to the one obtained in Solyali and Süral (2012) for the transportation formulation.

Proposition 1

If the y variables are fixed, there exists an optimal solution in which the Y variables assume integer values.

Proof

Let \(\overline{y} \in \{0,1\}^{NT}\) be the y variables in an integer feasible solution. Given fixed \(\overline{y}\), the production cost can be included in the transportation cost in a way that the ‘new’ transportation cost to retailer c in period k can be calculated as \(p^{c}_{k} = \min _{1 \le k' \le k}\{ p^0_{k'} \ | \ \overline{y}_{k'} = 1 \} + p^{c}_k\). The remaining problem to solve is given by

$$\begin{aligned} (FIX) \, \,&\min \sum _{c=1}^{NC}\sum _{t=1}^{NT} \left( p^{c}_tx^{c}_t + f^{c}_tY^{c}_t\right) \\&\sigma ^{1c}_{k-1,t} + w^{1c}_{kt} = \delta _{kt}d^c_t + (1-\delta _{kt})\sigma ^{1c}_{k,t}, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le t \le NT, \\&w^{1c}_{kt} \le Y^{c}_k d^c_t, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le t \le NT, \\&\sum _{t=k}^{NT} w^{1c}_{kt} = x^{c}_k, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le NT, \\&w^{1} \in {\mathbb {R}}_+^{NC \times NT\times NT} , \\&Y \in [0,1]^{NC\times NT}, \end{aligned}$$

in which some \(w^{1c}_t\) would have to be fixed to 0 in case the production could not have occurred before period t. Observe that the only constraints linking the different retailers, i.e. the setup constraints for the Y variables, is irrelevant in this model. In this way, (FIX) is composed simply of multicommodity reformulations for c uncapacitated lot-sizing problems. It is known (see Pochet and Wolsey 2006) that, for each of these problems, the projection of the multicommodity formulation into the original space gives the convex hull of the solutions of the problem. Therefore, the Y variables assume integer values. \(\square \)

4.4 Two-level lot-sizing dynamic programming based formulation

The dynamic programming based formulation consists in using a strong formulation describing the convex hull of solutions for the two-level lot-sizing problem, and it was applied to a generalization of the one-warehouse multi-retailer problem in Melo and Wolsey (2010).

We remark that this formulation has shortest path characteristics as it was obtained from a dynamic programming algorithm. Consider variables \(\upsilon ^c_{ujt}\) to be equal to one if production takes place at the warehouse in period u and the amount produced is \(d^c_{jt}\). Also, define \(\omega ^c_{pjt}\) to be equal to one if transportation of \(d^c_{jt}\) happens to retailer c in period j using items from a production batch \(d^c_{pq}\) at the warehouse in period u with [j, t] a subinterval of the interval [p, q] and \( u \le p \le j \le t \le q\). The formulation can be described as

$$\begin{aligned} (DDP) \, \,&\min \sum _{t=1}^{NT} \left( p^{0}_t x^{0}_t + f^{0}_t y_t\right) + \sum _{c=1}^{NC}\sum _{t=1}^{NT} \left( p^{c}_tx^{c}_t + f^{c}_tY^{c}_t\right) \end{aligned}$$
(68)
$$\begin{aligned}&\sum _{k=1}^{NT}\sum _{j=k}^{NT}\upsilon ^{c}_{kj,NT} =1, \ \ \ \forall \ 1\le c \le NC, \end{aligned}$$
(69)
$$\begin{aligned}&\sum _{k=1}^{t} \sum _{j=k}^{t} \upsilon ^{c}_{kjt} - \sum _{k=1}^{t+1}\sum _{j=t+1}^{NT}\upsilon ^{c}_{k,t+1,j} = 0, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le NT-1, \end{aligned}$$
(70)
$$\begin{aligned}&\sum _{k=t}^{l}\omega ^{c}_{tkl} - \sum _{k=l+1}^{NT}\omega ^{c}_{t,l+1,k} - \sum _{k=1}^{t}\upsilon ^{c}_{ktl} = 0, \ \ \ \forall \ 1\le c \le NC ,\ 1 \le t \le l \le NT , \end{aligned}$$
(71)
$$\begin{aligned}&\sum _{k=t}^{NT}\sum _{j=k}^{NT} \upsilon ^{c}_{tkj} \le y_{t}, \ \ \ \forall \ 1\le c \le NC,\ 1\le t \le NT, \end{aligned}$$
(72)
$$\begin{aligned}&\sum _{\gamma =1}^{k}\sum _{t= k}^{NT} \omega ^{c}_{\gamma k t} \le Y^{c}_{k}, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le NT, \end{aligned}$$
(73)
$$\begin{aligned}&\sum _{c=1}^{NC} \sum _{k=t}^{NT}\sum _{j=k}^{NT}\upsilon ^{c}_{tkj}d^{c}_{kj} = x^{0}_{t}, \ \ \ \forall \ 1\le t \le NT, \end{aligned}$$
(74)
$$\begin{aligned}&\sum _{\gamma =1}^{k}\sum _{t= k}^{NT} \omega ^{c}_{\gamma k t}d^{c}_{kt} = x^{c}_{k}, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le NT, \end{aligned}$$
(75)
$$\begin{aligned}&\upsilon ^{c}_{ljk}, \ \omega ^{c}_{ljk} \in {\mathbb {R}}_+, \ \ \ \forall \ 1\le c \le NC, \ 1 \le l \le j \le k \le T , \end{aligned}$$
(76)
$$\begin{aligned}&x \in {\mathbb {R}}^{(1+NC)NT}_+,\ y \in \{0,1\}^{NT}, \ Y \in [0,1]^{NC\times NT}. \end{aligned}$$
(77)

The objective function (68) plus a constant K is equivalent to (1). Constraints (69) and (70) are shortest path related restrictions to the warehouse. Constraints (71) link the shortest path related restrictions to the retailers with those corresponding to the warehouse. Constraints (72) and (73) are setup enforcing constraints. Constraints (74) and (75) link the new variables to those of the two-level lot-sizing problem. Constraints (76) and (77) are nonnegativity and integrality constraints on the variables. This formulation has \(O(NC\times NT^3)\) variables and \(O(NC \times NT^2)\) constraints, disconsidering the nonnegativity restrictions.

5 A theoretical analysis of the linear relaxation bounds

In this section we make a theoretical study of the linear relaxation bounds provided by the formulations described in Sects.  3 and 4. Define \(P^{ESWW}\), \(P^{SES}\), \(P^{2LSWW}\), \(P^{MC}\), \(P^{TR}\), \(P^{SP}\) and \(P^{DDP}\) to be the polyhedra defined by the respective formulations, and let \(z_{LP(ESWW)}\), \(z_{LP(SES)}\), \(z_{LP(2LSWW)}\), \(z_{LP(MC)}\), \(z_{LP(TR)}\), \(z_{LP(SP)}\) and \(z_{LP(DDP)}\) denote their linear relaxation bounds. In addition, consider \(P'^{FORM} = proj_{(x,y,Y)}FORM\), with FORM being any valid extended formulation for the problem, to be the projection of the polyhedron \(P^{FORM}\) into the space of the original variables and define \(P'^{SES}\), \(P'^{2LSWW}\), \(P'^{MC}\), \(P'^{TR}\), \(P'^{SP}\) and \(P'^{DDP}\). Certain results regarding the linear relaxation bounds of SES, TR and SP were proved in Solyali and Süral (2012) and are stated next as Propositions 2 and 3.

Proposition 2

(Solyali and Süral (2012)) \(z_{LP(SES)} \le z_{LP(TR)}\).

Proposition 3

(Solyali and Süral (2012)) \(z_{LP(TR)} \le z_{LP(SP)}\).

Proposition 4

\(z_{LP(ESWW)} \le z_{LP(SES)}.\)

Proof

The proof consists in showing that SES provides stronger reformulations than ESWW for two relaxed uncapacitated lot-sizing sets, the first one implied by (22) and (23) and the second by (3) and (5). The result follows from the fact that SES uses a facility location reformulation, (25) and (28), which gives the convex hull of (22) and (23), and another facility location reformulation, (27) and (29), providing also the convex hull of (3) and (5). On the other hand, the addition of Wagner–Whitin inequalities in ESWW only provides an approximation of the convex hull of these sets, i.e. (51) strengthen (22) and (23) while (52) strengthen (3) and (5). In this manner, \(P'^{SES} \subseteq P^{ESWW}\) and therefore \(z_{LP(ESWW)} \le z_{LP(SES)}\). \(\square \)

Example 1

Define an instance with parameters: \(NC=1\), \(NT=4\), \(d=(0,10,10,10)\), \(f^0=(5,3,5,3)\), \(p^0=(2,4,2,1)\), \(f=(0,0,0,0)\) and \(p=(0,0,0,0)\).

Observation 4

SES dominates ESWW.

A strict dominance can be seen in Example 1, for which \(z_{LP(ESWW)}=56.0004 < z_{LP(SES)}=58.0\).

Proposition 5

\(z_{LP(ESWW)} \le z_{LP(2LSWW)}.\)

Proof

The proof is very concise and consists in showing that inequalities (51) of ESWW can be obtained as a linear combination of inequalities (54) of 2LSWW and are therefore weaker, as the other inequalities, (52) and (55), are already equivalent. Observe that inequalities (54) can be summed up over c in order to get

$$\begin{aligned} \sum _{c=1}^{NC}s^{0c}_{t-1} + \sum _{c=1}^{NC}s^{c}_{t-1} + \sum _{k=t}^l \sum _{c=1}^{NC} d^c_{kl} y_k \ge \sum _{c=1}^{NC} d^c_{tl}, \ \ \ \forall \ 1\le t \le l \le NT. \end{aligned}$$
(78)

As \(s^0_t = \sum _{c=1}^{NT} s^{0c}_t\), one can obtain (51) by simple substitution and thus \(P'^{2LSWW} \subseteq P^{ESWW}\), implying \(z_{LP(ESWW)} \le z_{LP(2LSWW)}\). \(\square \)

Example 2

Define an instance with parameters: \(NC=2\), \(NT=5\), \(d={\left( \begin{matrix} 30 &{}\,\,\, 30 &{}\,\,\, 0 &{}\,\,\, 0 &{}\,\,\, 10 \\ 0 &{}\,\,\, 0 &{}\,\,\, 0 &{}\,\,\, 0 &{}\,\,\, 30 \end{matrix} \right) }\), \(f^0=(100,100,100,100,100)\), \(p^0=(4,3,2,1,0)\), \(f={\left( \begin{matrix} 100 &{}\,\,\, 100 &{}\,\,\, 100 &{}\,\,\, 100 &{}\,\,\, 100 \\ 0 &{}\,\,\, 0 &{}\,\,\, 0 &{}\,\,\, 0 &{}\,\,\, 0 \end{matrix} \right) }\) and \(p={\left( \begin{matrix} 4 &{}\,\,\, 3 &{}\,\,\, 2 &{}\,\,\, 1 &{}\,\,\, 0 \\ 4 &{}\,\,\, 3 &{}\,\,\, 2 &{}\,\,\, 1 &{}\,\,\, 0 \end{matrix} \right) }\).

Observation 5

2LSWW dominates ESWW.

A strict dominance can be seen in Example 2, for which \(z_{LP(ESWW)}=835.0 < z_{LP(2LSWW)}=860.0\).

Observation 6

There is no dominance when comparing SES and 2LSWW.

This can be observed from the solutions obtained for the instances in Examples 1 and 2. When considering Example 1, \(z_{LP(2LSWW)} = 56.004 < z_{LP(SES)}= 58.0 \). On the other hand, for Example 2 \(z_{LP(SES)}=835.0 < z_{LP(2LSWW)}=860.0\).

Proposition 6

\(z_{LP(2LSWW)} \le z_{LP(MC)}.\)

Proof

This result follows from the simple fact that inequalities (54), (55) and (56) of 2LSWW are simple specific cases of the two-echelon inequalities described in Zhang et al. (2012) for the two-echelon lot-sizing in case there are no intermediate demands, i.e. demands related to level zero, in whose work it was shown that such inequalities can be obtained from the projection of the multicommodity formulation. This implies that \(P'^{MC} \subseteq P^{2LSWW}\) and therefore \(z_{LP(2LSWW)}\le z_{LP(MC)}\). \(\square \)

The next result shows that it is possible to use a multicommodity formulation which is one order of magnitude smaller than that of the transportation formulation and yet get a linear relaxation bound that is as strong as the one obtained by the later.

Proposition 7

\(z_{LP(MC)} = z_{LP(TR)}.\)

Proof

The proof consists in showing that a feasible solution to the linear relaxation of TR can be converted into a solution to the linear relaxation of MC and the converse also holds. Let \((x,y,Y,w^{0},w^{1}) \in P^{MC}\) and \((x,y,Y,\lambda ) \in P^{TR}\), where the link between \(\lambda \) and w in TR is given by

$$\begin{aligned} w^{0c}_{st} = \sum _{k=s}^t \lambda ^c_{skt}, \end{aligned}$$
(79)
$$\begin{aligned} w^{1c}_{kt} = \sum _{s=1}^k \lambda ^c_{skt}. \end{aligned}$$
(80)

First we want to demonstrate that if \((\hat{x}^{0},\hat{x}^{1},\hat{y},\hat{Y},\hat{\lambda }) \in P^{TR}\) then \((\hat{x}^{0},\hat{x}^{1},\hat{y},\hat{Y},\hat{w}^{0},\hat{w}^{1}) \in P^{MC}\). Using (79) and (80), nonnegativity of \(\lambda \) imply nonnegativity of \(w^{0}\) and \(w^{1}\) and constraints (62), (63), (64) and (65) follow by substitution. It suffices to show that constraints (60) and (61) are satisfied. Note that we can eliminate the stock variables \(\sigma ^{0}\) and \(\sigma ^{1}\) and rewrite (60) and (61) respectively as

$$\begin{aligned}&\displaystyle \sum \nolimits _{j=1}^k w^{0c}_{jt} \ge \sum \nolimits _{j=1}^k w^{1c}_{jt}, \ \ \ \forall \ 1\le c \le NC,\ 1\le k \le t \le NT, \end{aligned}$$
(81)
$$\begin{aligned}&\displaystyle \sum \nolimits _{k=1}^t w^{1c}_{kt} = d^c_t, \ \ \ \forall \ 1\le c \le NC, \ 1\le t \le NT. \end{aligned}$$
(82)

Constraints (34) imply

$$\begin{aligned} \sum _{s=1}^k \hat{w}^{0c}_{st} = \sum _{s=1}^{k} \sum _{j=s}^{t} \hat{\lambda }^c_{sjt} \ge \sum _{m=1}^{k}\sum _{l=m}^{k} \hat{\lambda }^c_{mlt} = \sum _{l=1}^{k}\sum _{m=1}^{l} \hat{\lambda }^c_{mlt} = \sum _{l=1}^{k} \hat{w}^{1c}_{lt}, \end{aligned}$$
(83)

where the inequality holds due to the nonnegativity of the variables, and

$$\begin{aligned} \sum _{k=1}^t \hat{w}^{1c}_{kt} = \sum _{k=1}^{t} \sum _{s=1}^{k} \hat{\lambda }^c_{skt} = \sum _{s=1}^{t} \sum _{k=s}^{t} \hat{\lambda }^c_{skt} = d^c_t. \end{aligned}$$
(84)

Thus, we have that (83) and (84) respectively imply (81) and (82).

The next step consitsts in showing that if \((\hat{x}^{0},\hat{x}^{1},\hat{y},\hat{Y},\hat{w}^{0},\hat{w}^{1}) \in P^{MC}\), then there exists \(\hat{\lambda }\) such that \((\hat{x}^{0},\hat{x}^{1},\hat{y},\hat{Y},\hat{\lambda }) \in P^{TR}\). Observe that for each demand \(d^c_t\), variables \(w^{0c}_{kt}\), \(w^{1c}_{kt}\), \(\sigma ^{0c}_{kt}\) and \(\sigma ^{1c}_{kt}\) related to commodity (c, t) describe a feasible flow of \(d^c_t\) units arriving in node (c, t). Note also that \(\sum _{k=1}^t \hat{w}^{1c}_{kt} = d^c_t\). In what follows we restrain our attention to the variables \(w^{0}\), \(w^{1}\), since \(\sigma ^{0}\) and \(\sigma ^{1}\) can be determined using the values of the former. According to the well-known flow decomposition theorem of Ford and Fulkerson (1962) any feasible flow on a network can be decomposed into paths and cycles. In our specific directed network structure there are no directed cycles, what implies the feasible flow determined by \(\hat{w}^{0c}\), \(\hat{w}^{1c}\) can be decomposed into paths \(\hat{\lambda }^c\) according to the flow decomposition theorem, as exemplified in Fig. 2. Such a decomposition can be done by using a flow decomposition algorithm in a way that (79) and (80) are satisfied. By direct substitution using (79) and (80), the constraints (35), (36), (37) and (38) are satisfied. It suffices to show that (34) is also satisfied. We have

$$\begin{aligned} \sum _{k=1}^{t} \hat{w}^{1c}_{kt} = d^c_{t}, \end{aligned}$$

and by substitution

$$\begin{aligned} \sum _{s=1}^{t}\sum _{k=s}^{t} \hat{\lambda }^c_{skt} = \sum _{k=1}^{t} \hat{w}^{1c}_{kt} = d^c_{t}. \end{aligned}$$

\(\square \)

Fig. 2
figure 2

Flow decomposition example. a Flow represented by \(w^0\) and \(w^1\). b Flow decomposed into paths \(\lambda \)

Full size image

Proposition 8

\(z_{LP(SP)} \le z_{LP(DDP)}.\)

Proof

The proof consists in showing that both SP and DDP are in fact composed of reformulations for a two-level lot-sizing for each retailer and as DDP gives the convex hull for each of these sets it provides a better bound as noted in Observation 3. Define both formulations as extended formulations of OWMR’, i.e. (9)–(15). In order to perform such an adaptation, the changes in SP and DDP will be the substitution in SP of (46) by

$$\begin{aligned} \sum _{c=1}^{NC}\sum _{r=s}^{NT}\sum _{t=r}^{NT} d^c_{rt}\phi ^c_{srt} = x^{0c}_s, \ \ \ \forall \ 1 \le c \le NC, \ 1\le s \le NT \end{aligned}$$
(85)

and the replacement in DDP of (74) by

$$\begin{aligned} \sum _{c=1}^{NC} \sum _{k=t}^{NT}\sum _{j=k}^{NT}\upsilon ^{c}_{tkj}d^{c}_{kj} = x^{0c}_{t}, \ \ \ \forall \ 1 \le c \le NC, \ 1\le t \le NT. \end{aligned}$$
(86)

Constraints (13) should also be added to both formulations. Denote SP’ and DDP’ the mentioned formulations after the changes just described. Note that both SP’ and DDP’ give a reformulation for each of the two-level lot-sizing problems related to a single retailer, and they are simply linked by the y variables. We remark that \(z_{LP(SP')}=z_{LP(SP)}\) and \(z_{LP(DDP')}=z_{LP(DDP)}\) as the original variables are simply determined by the other SP and DDP constraints. It is known from Melo and Wolsey (2010) that DDP’ provides the convex hull of solutions for each of these two-level lot-sizing sets and therefore \(z_{LP(SP)}\le z_{LP(DDP)}.\)

\(\square \)

Corollaries 9 and 10 follow from Propositions 2 to 8.

Corollary 9

\(z_{LP(ESWW)} \le z_{LP(SES)} \le z_{LP(MC)} = z_{LP(TR)} \le z_{LP(SP)} \le z_{LP(DDP)}.\)

Corollary 10

\(z_{LP(ESWW)} \le z_{LP(2LSWW)} \le z_{LP(MC)} = z_{LP(TR)} \le z_{LP(SP)} \le z_{LP(DDP)}.\)

6 Computational experiments

In this section we report on some computational experiments which were carried out to analyze the behavior of the formulations presented in Sects. 3 and 4. All experiments were performed on a machine running under Xubuntu x86_64 GNU/Linux, with an Intel Core i7-4770S 3.10 GHz processor, 8Gb of RAM memory using FICO Xpress 7.9. For all executions a time limit of 1800 seconds was imposed.

6.1 Instances

Two instance sets were generated, the first one composed of those with invariable transportation costs and the second with variable transportation costs. In order to generate the instances with invariable transportation costs, we selected a subset of the different parameters used in Solyali and Süral (2012) and the costs, which are all time invariant, were generated as in the referenced paper. Fixed production costs were generated in the interval \(q^{0}\in [1500,4500]\), fixed transportation costs were generated in the interval \(q^{1c} \in [5, 100]\), storage cost at the production site is \(h^{0}=0.5\), storage costs at retailer c were generated in the interval \(h^{c} \in [0.5, 1.0]\). Production cost is \(p^{0}=0\) and transportation costs are \(p^{c}=0\) for every c. Observe that it is reasonable to assume that the costs are time invariant and besides that, instances with this sort of cost were among the most challenging ones in Solyali and Süral (2012). Demands were generated in the interval \(d^{c}_t \in [5,100]\). With exception of the storage costs all the parameters are integer valued. The number of retailers were generated as \(NC \in \{ 50,100,150,200 \}\), while the number of periods as \(NT \in \{ 30,45,60 \}\). Five instances were generated for each possible combination (NC, NT). Observe that the instances considered here are at least as large as the larger ones considered in Solyali and Süral (2012) regarding the number of periods, in which instances were created with \(NC \in \{ 50,100,150 \}\) and \(NT \in \{ 15,30 \}\).

In a real situation, it is not unusual that varying transportation costs may be incurred when shipping to retailers located at different locations. Therefore, we generated a second set of instances with variable transportation costs in order to verify the behavior of the solver under this circumstance. All data was generated as explained in the previous paragraph with the exception of the transportation cost, which can assume values \( p^{c} \in [1.5,2.5]\) for each retailer.

6.2 Tested approaches

The following approaches were considered in our computational experiments:

  • ESWW: Wagner–Whitin based formulation;

  • SES: strengthened echelon stock formulation;

  • 2LSWW: two-level lot-sizing Wagner–Whitin based formulation;

  • p2LSWW: partial two-level lot-sizing Wagner–Whitin based formulation, which will be described next;

  • MC: multicommodity formulation;

  • TR: transportation formulation;

  • SP: shortest path formulation;

  • DDP: two-level lot-sizing dynamic programming based formulation.

The partial two-level lot-sizing Wagner–Whitin based formulation (p2LSWW) consists in limiting the amount of inequalities to be inserted into the original formulation in a heuristic way. Considering time invariant costs, values \(K^1_c\), \(K^2_c\) and \(K^2_c\) are heuristically calculated for each retailer c as shown in equations (87), (88) and (89) based on the problem’s cost structure in order to define the maximum size of the intervals for which inequalities (54), (55) and (56) will be inserted into the formulation.

$$\begin{aligned} K^1_c= & {} \max \left\{ 5 \ , \ {\mathop {\hbox {arg min}}\limits _{k \in \{ 1\ldots NT\}}} \frac{\sum _{c=1}^{NC} d^c_{1,NT}}{NT} \times k \times h^0 \ge f^0 \right\} , \end{aligned}$$
(87)
$$\begin{aligned} K^2_c= & {} \max \left\{ 5 \ , \ {\mathop {\hbox {arg min}}\limits _{k \in \{ 1\ldots NT\}}} \frac{d^c_{1,NT}}{NT} \times k \times h^c \ge f^c \right\} , \end{aligned}$$
(88)
$$\begin{aligned} K^3_c= & {} \min \{K^1_c \ , \ K^2_c \}. \end{aligned}$$
(89)

6.3 Results for instances with invariable transportation costs

A summary of the results for the instances with invariable transportation costs is presented in Tables  1 and 2 regarding, respectively, linear relaxation bounds and integer solution results.

Table 1 Linear relaxation bounds for the instances with invariable transportation costs
Full size table
Table 2 Integer solution results for the instances with invariable transportation costs
Full size table

In Table 1, the first two columns give respectively the number of retailers and the number of time periods for each set of instances. The other columns present the linear relaxation results for each of the following formulations: ESWW, SES, 2LSWW, p2LSWW, MC, TR, SP and DDP. The columns show the geometric mean of the time spent (time) to solve the linear relaxation and the arithmetic average of the linear relaxation gap (\(\hbox {gap}_{LP}\)) for the instance group, with the gap for each instance calculated as \(100 \times \frac{z_{IP} - z_{LP}}{z_{IP}}\) being \(z_{IP}\) the best known integer feasible solution and \(z_{LP}\) the corresponding linear relaxation bound. The values x and \(\sim \) in columns time and \(\hbox {gap}_{LP}\), respectively, indicate that the linear relaxation could not be solved within the 1800s time limit for any of the instances in the group. We remark that geometric means were generally used in our tables as the values measured may vary considerably considering different instances in a group. The exception was for the linear relaxation gaps, as some of them were equal to zero and in this situation the arithmetic average illustrated better what we proposed to compare. We note that the linear relaxations were solved using the solver’s barrier method. Preliminary results showed that such setting did not improve the solver’s performance when dealing with the integer solutions and we therefore kept the solver’s standard settings.

The results in Table 1 show that all formulations, with exception of ESWW and SES, provided very good bounds for the considered instances, with means always below \(0.4\,\%\). Note that the linear relaxations could not be solved using 2LSWW for the instances with \(NT=200\) and \(NC=60\). An important observation is that the proposed partial formulation did not decrease the bounds obtained using 2LSWW, but allowed a significant time reduction and additional linear programs to be solved within the time limit. MC obtained optimal linear programming solutions in less mean time, but in certain cases the gaps were slightly worse than those obtained by SP and DDP. It is noteworthy that both SP and DDP obtained the same average gaps for all considered instance groups. Based on the experiments, our view is that MC and p2LSWW offer the best compromise among the obtained linear relaxation bounds and the time spent.

Table 2 summarizes the results regarding the integer feasible solutions. The first two columns describe the dimensions of the instances and the other columns present, for each formulation, the geometric mean of the time spent (time) to solve the instances to optimality, the geometric mean of the remaining gap (gap) for the unsolved instances and the number of instances solved to optimality (opt). The value x is present in column time if none of the instances were solved to optimality and the value \(\sim \) in column gap if a feasible solution was not encountered for any of the unsolved instances. The superscripts in the values of the gap indicate the number of instances for which a feasible solution was not encountered: a (one instance), b (two instances), c (three instances) and d (four instances). The results show that in general MC outperformed all the other approaches considering the number of instances solved to optimality as it could solve all the 60 (100 %) of them, and it was closely followed by p2LSWW which solved 59 (98.3 %). It is noteworthy that p2LSWW performed best in certain instance groups when we analyze the mean time to solve the instances to optimality. The two weaker formulations, ESWW and SES, could only solve 3 (5 %) and 5 (8.3 %) instances to optimality each. Note that probably due to its large size, TR could solve 53 (88.3 %) instances, which was not as many as MC, even though they provide the same linear relaxation bounds. The efficiency of the two other largest formulations, SP and DDP, decreased considerably with the increase of the instance sizes confirming what was also observed in Solyali and Süral (2012). Note that only 42 (70 %) instances were solved using SP and 44 (73.3 %) instances using DDP.

6.4 Results for instances with variable transportation costs

Table 3 summarizes the linear relaxation results for the instances with variable transportation costs. The relative comparison of the formulations is not much different from the case with invariable transportation costs, as it can be observed in Table  1. For this set of instances, the mean gap did not reach 0.2 % using any of the formulations 2LSWW, p2LSWW, MC, TR, SP and DDP. Again, the linear relaxations of instances with \(NT=200\) and \(NC=60\) could not be solved using 2LSWW within the time limit. Formulations 2LSWW and p2LSWW offer the same linear relaxation gaps, but p2LSWW has the advantage of offering the bounds in less mean time. The mean time to solve the linear relaxation of MC is always smaller than that to solve the linear relaxation of TR. The gaps of formulations SP and DDP are the same, and the time spent is usually better for DDP with the exception of some of the smaller instance groups. Overall, SP and DDP provide better linear relaxation bounds but we remark that p2LSWW and MC provide bounds that are almost as good in much less time.

Table 3 Linear relaxation bounds for the instances with variable transportation costs
Full size table

The integer solutions results for this set of instances are summarized in Table  4. It can be observed that, for this set, p2LSWW outperformed all the other approaches when we consider the number of instances solved to optimality, with a total of 59 (98.3 %), followed by MC with 58 (96.7 %), TR with 54 (90 %), SP with 43 (71.7 %), DDP with 42 (70 %), 2LSWW with 24 (40 %), SES with 5 (8.3 %) and ESWW with 3(5 %).

Table 4 Integer solution results for the instances with variable transportation costs
Full size table

7 Final remarks

In this paper, we considered the one-warehouse multi-retailer problem and compared several integer programming formulations for the problem. We performed a theoretical comparison of the formulations based on the provided linear relaxation bounds. After that, computational experiments were carried out comparing these formulations with respect to the provided linear relaxation bounds and obtained integer solutions. This work complements the literature on formulations for the OWMR described in Solyali and Süral (2012).

A theoretical study was performed comparing the linear relaxation bounds obtained by the different formulations. An ordering of the formulations was then established according to the strength of the obtained bounds. It is noteworthy that the multicommodity formulation can obtain the same bounds provided by a larger transportation formulation. It remains an open question whether the dynamic programming based formulation (DDP) strictly dominates the shortest path formulation (SP) considering the assumption on the costs, as we were not able to show a strict dominance of DDP over SP and this was not observed in the experimental results. Observe that we only considered the case in which there is no initial storage and, in this way, the situation in which initial storage is present remains an open object of study.

The computational results indicate that the multicommodity formulation and a partial version of the two-level lot-sizing based formulation strengthened with valid inequalities outperform all the other tested approaches. The results showed that these two formulations obtained, using much less computational time, linear relaxation bounds which were not much weaker than those obtained by the strongest ones considering the tested instances. They were able to solve almost all instances to optimality, a much larger number when compared with the other approaches. These two formulations seem to be good alternatives to the larger ones which were previously the best performing approaches, especially as the size of the instances become larger. They appear to be promising to problems that have the one-warehouse multi-retailer as a subproblem, for example certain production routing problems (see Adulyasak et al. 2015).