OR Spectrum (2008) 30:773–785 DOI 10.1007/s00291-007-0094-3 REGULAR ARTICLE

Equivalence of the LP relaxations of two strong formulations for the capacitated lot-sizing problem with setup times Meltem Denizel · F. Tevhide Altekin · Haldun Süral · Hartmut Stadtler

Published online: 15 August 2007 © Springer-Verlag 2007

Abstract The multi-item Capacitated Lot-Sizing Problem (CLSP) has been widely studied in the literature due to its relevance to practice, such as its application in constructing a master production schedule. The problem becomes more realistic with the incorporation of setup times since they may use up significant amounts of the available resource capacity. In this paper, we present a proof to show the linear equivalence of the Shortest Path (SP) formulation and the Transportation Problem (TP) formulation for CLSP with setup costs and times. Our proof is based on a linear transformation from TP to SP and vice versa. In our proof, we explicitly consider the case when there is no demand for an item in a period, a case that is frequently observed in the real world and in test problems in the literature. The equivalence result in this paper has an impact on the choice of model formulation and the development of solution procedures. Keywords Production · Capacitated lot-sizing · Strong formulation · Linear relaxation

M. Denizel · F. T. Altekin (B) Faculty of Management, Sabancı University, Orhanlı 34956, Tuzla, ˙Istanbul, Turkey e-mail: [email protected] M. Denizel e-mail: [email protected] H. Süral Industrial Engineering Department, Middle East Technical University, 06531 Ankara, Turkey e-mail: [email protected] H. Stadtler Institute for Logistics and Transport, University of Hamburg, Von-Melle-Park 5, 20146 Hamburg, Germany e-mail: [email protected]

123

774

M. Denizel et al.

1 Introduction The multi-item Capacitated Lot-Sizing Problem (CLSP) has been extensively studied in the production scheduling literature due to its relevance to practice, such as its application in constructing a master production schedule. The aim is to find a cost minimizing production plan for a multi-item, multi-period problem, constrained by a limited capacity resource. Starting the production of an item in a period requires a setup on the resource at a cost independent of the production volume; and each item requires a certain amount of processing time on the resource. As the demands for each period are to be met without backordering and within the capacity limit, items can be carried in inventory, with a per unit per period cost, to supply the demand of future periods. Hence, the main tradeoff is between inventory carrying and setup costs. CLSP can be formulated as a mixed integer program, and alternative formulations have been suggested in the literature. Since, CLSP is strongly NP-hard (Chen and Thizy 1990), there are very few exact methods based on techniques such as branch and bound, cut generation, and variable redefinition. The majority of the studies involve heuristics, which are classified as common-sense heuristics and mathematical programming-based heuristics. A recent review of all these CLSP models and algorithms is presented in Karimi et al. (2003). Linear Programming (LP) relaxations of the alternative CLSP formulations are of special interest in various studies since the LP objective function value can be used as a lower bound on the optimal solution, and the LP solution can be used to construct solutions to the original problem via mathematical programming-based heuristics. Among alternative formulations, the LP relaxations of two strong formulations, namely, the Transportation Problem (TP) formulation (also known as the simple plant location formulation) and the Shortest Path (SP) formulation lead to higher objective function values than others and are therefore more promising in finding optimal or near-optimal solutions to the problem. They use the basic constructs of the classical transportation and shortest path problems; however, they include integer variables to incorporate setups. Alfieri et al. (2002) observed, within their experimental settings, that the LP relaxations of SP and TP lead to objective function values that are about 60% higher than those obtained through the LP relaxation of the weak standard formulation. Moreover, they report that the LP relaxation of SP is solved more quickly on average. Although these empirical findings are recent, the TP formulation of the single-item Uncapacitated Lot-Sizing Problem (ULSP) dates back to Krarup and Bilde (1977) who showed that ULSP could be solved as the LP relaxation of the TP formulation (there called the plant location formulation) to find the optimal solution. Later, Eppen and Martin (1987) introduced the SP formulation for the multi-item CLSP. Dropping the capacity constraints in SP, they showed that the remaining constraints define the convex hull of the multi-item ULSP. The first equivalence result is by Nemhauser and Wolsey (1988) who showed the equivalence of the TP and SP formulations for ULSP by proving that the LP relaxations of both formulations define the convex hull of ULSP. Based on this result, they also stated a proposition on the equivalence of the LP relaxations of the two formulations in the presence of complicating constraints. Stadtler (1996b) showed in the context of multi-level CLSP that any feasible solution

123

LP relaxation equivalence of strong CLSPwS formulations

775

to the LP relaxation of the TP formulation is also feasible to the LP relaxation of the SP formulation and both lead to the same LP objective function value. One of the variants of CLSP is the multi-item Capacitated Lot-Sizing Problem with Setups (CLSPwS), which, in addition to setup costs, also considers setup times as an important capacity requirement. In this variant, the problem becomes more difficult, since now even the problem of finding a feasible solution is NP-complete (Maes et al. 1991) and the strong formulations of CLSPwS yield wider integrality gaps (Denizel and Süral 2006; Süral et al. 2006) when compared to the case with no setup times. In developing LP-based heuristics for CLSPwS, Denizel and Süral (2006) observed that, within their experimental settings, the LP relaxations of SP and TP lead to the same objective function values, which are about 30% higher than those obtained through the LP relaxation of the weak standard formulation. They also report that the LP relaxation of SP is solved more quickly on average. Researchers who tackle the lot-sizing problems usually resort to the SP formulation as the basis of good solution procedures (Alfieri et al. 2002; Eppen and Martin 1987; Jans and Degraeve 2004; Stadtler 1996a, 1997), except Süral et al. (2006). The objective of this paper is to present a proof for the linear equivalence of the TP and SP formulations for CLSPwS by extending the proof of equivalence of the ULSP formulations in Nemhauser and Wolsey (1988). The motivation is that the former study does not incorporate setup times and assumes positive demands in each period. When there is no demand for an item in a period (which we refer to as the zero-demand case), unnecessary setups must be avoided in the SP formulation, a requirement that is sometimes overlooked in the literature. We consider the zero-demand case explicitly in our proof since it is frequently observed in the real world and test problem instances used in the literature. Our proof is based on a linear transformation from TP to SP and vice versa. With an approach similar to Stadtler (1996b), we show that any feasible solution to a formulation is also feasible to the other formulation and leads to the same objective function value. In the next section, after summarizing the assumptions of CLSPwS, we review the SP and TP formulations. We show the linear equivalence of the two formulations in the third section. Conclusions are presented in the last section.

2 Two strong formulations of CLSPwS In this section, we present the two alternative formulations for CLSPwS, based on the notation provided below: i Item index i = 1, 2, . . . , N t Period index t = 1, 2, . . . , T Ct Available capacity in time units in period t dit Demand for item i in period t Processing time of item i ai Cost of carrying one unit of item i in inventory from a period to the next hi Setup time for item i si sci Setup cost by item i.

123

776

M. Denizel et al.

We assume that demand of all N items in each period of the planning horizon T is known and should be satisfied on time. There is a single capacitated resource whose capacity Ct is given for each period. The production of each unit item uses ai time units of capacity and has constant production costs (which can be ignored). We assume sequence-independent setup costs sci and setup times si for each item, which are stationary over time. Without loss of generality there is no initial stock on hand and the holding cost for carrying one unit of product i during a period h i is given. Note that the standard (weak) formulation of CLSPwS is presented in the Appendix. 2.1 Transportation problem formulation (TP) Define z itr as the quantity produced in period t to satisfy the demand of item i in period r , where r ≥ t. Let y¯it be equal to 1 if a setup for item i is incurred in period t, 0 otherwise. The following formulation makes use of the advantage that stems from a strong formulation of the single item ULSP. TP Minimize z =

N
r −1 T



(r − t)h i z itr +

N
T


i=1 r =1 t=1

s. t.

r


sci y¯it

(TP.1)

i=1 t=1

z itr = dir ∀ i and r = 1, . . . , T

(TP.2)

t=1

N
i=1

  T  
z itr + si y¯it ≤ Ct ∀ t ai

(TP.3)

r =t

z itr ≤ dir y¯it ∀ i, t and r where t ≤ r z itr ≥ 0 ∀ i, t and r where t ≤ r y¯it ∈ {0, 1} ∀ i and t

(TP.4) (TP.5) (TP.6)

In this formulation, TP.1 minimizes the total inventory carrying and setup costs, TP.2 assures that total production for item i in periods 1 through r is equal to the demand in period r (see Fig. 1 for its network representation for one product), TP.3 maintains that total production and setup times in period t do not exceed the available (time) capacity Ct , and TP.4 incurs a setup for each production run. TP.5 and TP.6 impose non-negativity on the production variables and integrality on the setup variables, respectively. The formulation has O(T 2 N ) variables and constraints. zi13 zi12

zi23

1

2

3

zi11

zi22

zi33

Fig. 1 Network representation of the TP model with T = 3 for item i

123

LP relaxation equivalence of strong CLSPwS formulations

777

2.2 Shortest path problem formulation (SP) Define u itk as the fraction of total demand for periods t through k of item i that is produced in period t. Let yit be equal to 1 if a setup for item i is incurred in period t, 0 otherwise. Let Ditk , Hitk and I Ditk >0 be defined as follows: Ditk =

k


di j ,

j=t

Hitk =

k


h i Di jk , and

j=t+1

 I Ditk >0 =

1 when Ditk > 0 0 otherwise

This formulation extends the reformulation of the single item ULSP as a shortest path problem, developed by Eppen and Martin (1987), to the capacitated case. SP Minimize z =

s. t.

N
i=1

−

t−1
k=1

T


 ai

N
T
i=1 t=1

T




T


 Hitk u itk

k=t

 + sci yit

(SP.1)



(Ditk u itk ) + si yit

≤ Ct ∀ t

(SP.2)

k=t

u ik,t−1 +

T


u itk = 0 ∀ i and t where t ≥ 2

(SP.3)

k=t

u i1t = 1 ∀ i

(SP.4)

I Ditk >0 u itk ≤ yit ∀ i and t

(SP.5)

u itk ≥ 0 ∀ i, t and k where t ≤ k yit ∈ {0, 1} ∀ i and t

(SP.6) (SP.7)

t=1 T
k=t

In this formulation, SP.1 minimizes the total inventory carrying and setup costs. SP.2 restricts the (time) capacity usage in each period. SP.3 defines the conservation equations for each item and each period on the network. SP.4 initiates a unit flow for each item in the first period. Conservation equations require that flow of each item cannot be created or destroyed through the network. Since flow generation does not depend on whether there is a production run or not in the first period, SP.5 ensures that a setup is incurred only for an actual production run. SP.6 and SP.7 impose non-negativity on the production variables and integrality on the setup variables,

123

778

M. Denizel et al.

ui13 ui12 ui11 1

ui33

ui22 2

3

4

ui23 Fig. 2 Network representation of the SP model with T = 3 for item i

respectively. The formulation has O(T 2 N ) variables and O(T N ) constraints. Figure 2 illustrates the network representation of the SP formulation for one product where the last node represents a dummy period. Due to the variable definitions in SP, a virtual period is needed in the network to show the associated flows. 3 Linear equivalence Theorem The LP relaxations of SP and TP provide the same solution set and objective function values for CLSPwS. We present the proof for the theorem by showing that for each continuous solution to SP (TP) there exist a corresponding solution in TP (SP) and both of these solutions lead to the same continuous solution value for CLSPwS. Let F(.) denote the solution set for problem(.) and SPLP and TPLP denote the LP relaxations of SP and TP, respectively. Let the solutions in F(SPLP ) and F(TPLP ) be represented by (u, y) ≡ { (u itk , yit )| i = 1, 2, . . . , N ; t = 1, 2, . . . , T ; k = t, t + 1, . . . , T } and (z, y¯ ) ≡ { (z itr , y¯it )| i = 1, 2, . . . , N ; t = 1, 2, . . . , T ; r = t, t + 1, . . . , T } , respectively. For (z, ¯y) ∈ F(T P L P ) and (u, y) ∈ F(S P L P ), Z T P (z, ¯y) and Z S P (u, y) denote the corresponding linear objective function values of TP and SP, respectively. In what follows, we present a proof of the Theorem at a moderate level of computational detail. We refer the reader to Denizel et al. (2005) for a more detailed version. Proof We show the equivalence of F(SPLP ) and F(TPLP ) and that SPLP and TPLP lead to the same continuous solution in three parts. Part I To show F(TPLP ) ⊆ F(SPLP ), we take a solution (z, y¯ ) ∈ F(TPLP ) and construct a solution (u, y) ∈ F(SPLP ). Given (z, y¯ ) ∈ F(TPLP ), construct (u, y) in the following manner: u it T = wit T ∀ i and t u itk = witk − wit,k+1 ∀ i, t and k where t ≤ k < T

123

(1) (2)

LP relaxation equivalence of strong CLSPwS formulations

779

where

witk

⎧z itk ⎪ ⎨ dik if dik > 0 = 1 if dik = 0 and t = k ⎪ ⎩ 0 otherwise

yit = y¯it

(3)

∀ i and t.

Note that a similar construction is given in Nemhauser and Wolsey (1988) for the single item ULSP with positive demand in all periods. Claim 1 (u, y) constructed through Eqs. (1)–(3) is in F(SPLP ). Proof of Claim 1 We show that (u, y) constructed through Eqs. (1)–(3) satisfy the constraints SP.2–SP.5. (a) Constraints SP.2: For any i and t, the inner summation on the left hand side of SP.2 can be written as T


Ditk u itk =

T


dir

T


r =t

k=t

u itk .

k=r

Substituting (1) and (2) in to the above equation for u itk we get T


Ditk u itk =

T


k=t

r =t

T


T


Ditk u itk =

T −1 
 dir witk − wit,k+1 + wit T k=r

dir witr ∀ iand t.

r =t

k=t

We consider the two possible demand situations in witr for any i, t and r ≥ t. = z itr . When dir = 0, we get dir witr = 0. When dir > 0, we have dir witr = dir zditr ir Due to TP.4, z itr = 0 when dir = 0 hence, without loss of generality we can write dir witr = z itr ∀ i, t and r ≥ t. Then, for all i and t T


Ditk u itk =

T


z itr .

r =t

k=t

Furthermore, since yit = y¯it by construction for all i and t SP.2 becomes N
i=1

 ai

T


 z itr + si y¯it

≤ Ct .

r =t

Since (z, y¯ ) ∈ F(TPLP ), this inequality holds by TP.3.

123

780

M. Denizel et al.

(b) Constraints SP.3: For any i and t the first term in SP.3 can be written as −

t−1


u ik,t−1 = −

k=1

t−1


t−1 t

wik,t−1 − wikt = − wik,t−1 + wikt − witt .

k=1

k=1

k=1

We consider the first term under the two possible demand situations for period t − 1. When for any item i, di,t−1 > 0, t−1


wik,t−1

k=1

t−1
z ik,t−1 = = di,t−1

t−1

k=1 z ik,t−1

k=1

di,t−1

= 1.

When for any item i, di,t−1 = 0, t−1


wik,t−1 = wi1,t−1 + wi2,t−1 + · · · + wi,t−2,t−1 + wi,t−1,t−1

k=1

= 0 + 0 + · · · + 0 + 1 = 1. Similarly, we get SP.3 becomes −

t

wikt = 1 ∀ i and t. Then for any i and t, the first term of

k=1 t−1

u ik,t−1 = −witt and the second term in SP.3 is

k=1 T


u itk =

k=t

T −1


 witk − wit,k+1 + wit T = witt .

k=t

We then have −witt + witt = 0 and SP.3 holds. (c) Constraints SP.4: Upon substitution of Eqs. (1)–(3) in SP.4 for any item i, the left hand side becomes T
k=1

u i1k =

T −1


 wi1k − wi1,k+1 + wi1T = wi11 .

k=1

We consider the two possible demand situations for wi11 . When di1 > 0 for = ddi1 = 1. This follows since some item i and r = 1, we have wi11 = zdi11 i1 i1 (z, y¯ ) ∈ F(TPLP ) and z i11 = di1 by TP.2. When di1 = 0 for any item i, by definition, we have that wi11 = 1. Hence SP.4 holds in both cases. (d) Constraints SP.5: By substituting Eqs. (1)–(3) in SP.5 we get   I Dit,t+1 >0 wit,t+1 − wit,t+2 + · · · + I Ditt >0 witt − wit,t+1 +  I Dit,T −1 >0 wit,T −1 − wit T + I Dit T >0 wit T ≤ yit ∀ i and t.



For any i and t, we consider two different demand values for dit . When dit > 0 ⇒ Ditk > 0 for all k ≥ t and SP.5 becomes witt = zdittit ≤ yit . As yit = y¯it for

123

LP relaxation equivalence of strong CLSPwS formulations

781

all i and t and (z, y¯ ) ∈ F(TPLP ), the last inequality holds by TP.4. When dit = 0 two different demand situations may arise: (i) dik = 0 ∀ k ≥ t. Then SP.5 becomes    0 witt − wit,t+1 + · · · + 0 witk − wit,k+1 + · · · + 0 wit,T −1 − wit T + 0 wit T ≤ yit . It follows that 0 ≤ yit . (ii) There exists at least one period greater than t with positive demand. Let k be the index of the first such period; i.e. dik > 0 ⇒ Dik j > 0 ∀ j ≥ k. Then di j = 0 ∀ j = t, t + 1, . . . , k − 1 and SP.5 becomes    0 witt − wit,t+1 + · · · + 1 witk − wit,k+1 + · · · + 1 wit,T −1 − wit T + 1 wit T ≤ yit . It follows that witk = zditk ≤ yit . As yit = y¯it for all i and t and (z, y¯ ) ∈ ik F(TPLP ), the last inequality holds by TP.4. With a, b, c and d we show that (u, y) ∈ F(SPLP), which proves Claim 1.  Part II To show that F(SPLP ) ⊆ F(TPLP ), we take a solution (u, y) ∈ F(SPLP ) and construct a solution (z, y¯ ) ∈ F(TPLP ). Given (u, y) ∈ F(SPLP ), construct (z, y¯ ) in the following manner. z itr = dir

T


u it j ∀ i, t and r where t ≤ r

(4)

j=r

y¯it = yit ∀ i and t.

(5)

Claim 2 (z, y¯ ) constructed through Eqs. (4)–(5) is in F(TPLP ). Proof of Claim 2 We show that (z, y¯ ) constructed through Eqs. (4)–(5) satisfy the constraints TP.2–TP.4. (a) Constraints TP.2: For any i and r , by inserting z itr in TP.2 we get, r


dir

t=1

T


u it j = dir .

j=r

This equality always holds for dir = 0. For any i and r = k with dik > 0, r T

Eq. TP.2 becomes u it j = 1. Similarly for any i and r = k − 1, we have t=1 j=r k−1

T

t=1 j=k−1

as

u it j = 1. Then,

k T

t=1 j=k

u it j =

k−1

T

u it j , which can be rewritten

t=1 j=k−1

123

782

M. Denizel et al. T




k−1


u ik j +

u ik j +

=

u it j

k−1


t=1

t=1

k−1
T


k−1


j=k T




j=k

u it j =

t=1 j=k

t=1

T


k−1


u ik j =

⎛ ⎝u it,k−1 +

T


⎞ u it j ⎠

j=k

u it,k−1 +

k−1
T


u it j

t=1 j=k

∀ i and k ≥ 2.

u it,k−1

t=1

j=k

This inequality holds by SP.3, since (u, y) ∈ F(SPLP ). (b) Constraints TP.3: For any i and t we can write T


z itr =

r =t

T


dir

r =t

=

T


T


u it j = dit

j=r

T


u it j + di,t+1

j=t

T


u it j + · · · + di T

j=t+1

T


u it j

j=T

Ditk u itk .

k=t

Substituting this term in TP.3, we obtain, for any t, N
i=1

 ai

T


 (Ditk u itk ) + si y¯it

≤ Ct .

k=t

This inequality holds by SP.2, since y¯it = yit for all i and t and (u, y) ∈ F(SPLP ). (c) Constraints TP.4: For any i, t and r ≥ t by substituting (4) in TP.4 we obtain

dir

T


u it j ≤ dir y¯it .

j=r

This inequality always holds for dir = 0. When dir > 0 for any i, t, and r ≥ t, T

we have u it j ≤ y¯it . Moreover, since dir > 0, Dir j > 0 for all j ≥ r and we j=r

can rewrite it as

T

I Dit j>0 u it j ≤ y¯it ∀i, t, r ≥ t. This inequality holds by SP.5,

j=r

since y¯it = yit for all i and t and (u, y) ∈ F(SPLP ). With a, b, and c we show that (z, y¯ ) ∈ F(TPLP ), which proves Claim 2.

123



LP relaxation equivalence of strong CLSPwS formulations

783

Part III We now show that the given (u, y) ∈ F(SPLP ) and the constructed (z, y¯ ) ∈ F(TPLP ) lead to the same objective function value for CLSPwS, i.e. ZSP (u, y) = ZTP (z, y¯ ). Claim 3 ZTP (z, y¯ ) = ZSP (u, y). Proof of Claim 3 Since by construction of z itr and y¯it for any i, t and r ≥ t, ZTP (z, y¯ ) can be rewritten as ⎛ ⎞ T N
N
r T
T


(r − t)h i ⎝dir u it j ⎠ + sci yit ZTP (z, y¯ ) = i=1 r =1 t=1

=

N
i=1

=

N
i=1

=

hi

j=r

T
r


i=1 t=1

N
T 
  (r − t) dir u itr + u it,r +1 +· · · + u it T + sci yit

r =1 t=1

⎧ ⎫ ⎡ ⎤ T
k N
T T ⎨
⎬

⎣ hi Di jk ⎦ u itk + sci yit ⎩ ⎭ t=1 k=t

T N
T



i=1 t=1

j=t+1

Hitk u itk +

i=1 t=1 k=t

The last expression is ZSP (u, y).

N
T


i=1 t=1

sci yit .

i=1 t=1



4 Conclusions We present a proof for the equivalence of the linear relaxations of two strong formulations for the multi-item capacitated lot-sizing problem with setups. We show that any feasible solution to one formulation is also feasible to the other and leads to the same linear objective function value. This equivalence result has an impact on the choice of a particular model formulation and the development of solution procedures. Since the bounds provided by the LP relaxation are equivalent for the TP and SP formulations, the choice should be based on other characteristics. For instance, TP has O(T 2 N ) constraints while SP has O(TN). In this manuscript, we present the empirical results of references Alfieri et al. (2002) and Denizel and Süral (2006) where in both studies shorter CPU times are reported in favor of the SP formulation. On the other hand the matrix of the TP formulation is less dense and involves smaller coefficients (dit instead of Ditk ). Thus characteristics of different solvers may be exploited by using of either the TP or SP formulations. Appendix Here, we present the (weak) standard formulation of CLSPwS for the sake of completeness. Define xit and Iit as the amount of item i produced in period t and inventory level of item i at the end of period t, respectively. Let the binary variable yit take the

123

784

M. Denizel et al.

value of 1 if a setup for item i is incurred in period t, 0 otherwise. Assuming si ≤ Ct for each  T item i and periodt an upper bound on production quantity m it is equal to

dik , (Ct − si )/ai . The mathematical programming model for the standard min k=t

formulation is as follows: P Minimize z =

N
T


h i Iit +

i=1 r =1

N
T


sci yit

s. t. Ii,t−1 + xit − Iit = dit ∀ i and t N


[ai xit + si yit ] ≤ Ct

(P.1)

i=1 t=1

∀t

(P.2) (P.3)

i=1

xit ≤ m ir yit ∀ i and t

(P.4)

Ii0 = 0 ∀ i xit ≥ 0, Iit ≥ 0 ∀ i and t

(P.5) (P.6)

yit ∈ {0, 1} ∀ i and t

(P.7)

In this formulation, P.1 minimizes the total inventory carrying and setup costs, P.2 represents the inventory balance equations for each item and each period, P.3 maintains that total production and setup times within the given capacity limit in each period, P.4 ensures a setup is incurred for each production run and P.5 represents the zero initial inventory level for each item assumption. P.6 and P.7 impose non-negativity on the production and inventory variables and integrality on the setup variables, respectively. The formulation contains O(N T ) variables and constraints. References Alfieri A, Brandimarte P, D’Orazio S (2002) LP-based heuristics for the capacitated lot-sizing problem: the interaction of model formulation and solution algorithm. Int J Prod Res 40(2):441–458 Chen WH, Thizy JM (1990) Analysis of relaxations for the multi-item capacitated lot-sizing problem. Ann Oper Res 26:29–72 Denizel M, Süral H (2006) On alternative mixed integer programming formulations and LP based heuristics for lot-sizing with setup times. J Oper Res Soc 57(4):389–399 Denizel M, Altekin FT, Süral H (2005) Equivalence of the LP relaxation solutions of two MIP formulations for the capacitated lot-sizing problem with setups. Working paper no: SUGSM-05-09, Faculty of Management, Sabanci University, Istanbul Eppen GD, Martin RK (1987) Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper Res 35:832–848 Jans R, Degraeve Z (2004) Improved lower bounds for the capacitated lot sizing problem with setup times. Oper Res Lett 32(2):185–195 Karimi B, Fatemi Ghomi SMT, Wilson JM (2003) The capacitated lot sizing problem: a review of models and algorithms. Omega 31:365–378 Krarup J, Bilde O (1977) Plant location, set covering and economic lot size: An O(mn)-algorithm for structured problems. In: Numerische methoden bei optimierungsaufgaben, band 3: Optimierung bei graphentheoritischen ganzzahligen problemen, Birkhauser, pp 155–186 Maes J, McClain JO, Van Wassenhove LN (1991) Multilevel capacitated lot sizing complexity and LP-based heuristics. Eur J Oper Res 53(2):131–148

123

LP relaxation equivalence of strong CLSPwS formulations

785

Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley, New York Stadtler H (1996a) Mixed integer programming model formulations for dynamic multi-item multi-level capacitated lotsizing. Eur J Oper Res 94:561–581 Stadtler H (1996b) On the equivalence of LP bounds provided by the shortest route and the simple plant location model formulation for dynamic multi-item multi-level capacitated lot-sizing, Schriften zur Quantitativen Betriebswirtschaftslehre, Technische Hochschule Darmstadt, 5/96, Darmstadt Stadtler H (1997) Reformulations of the shortest route model for dynamic multi-item multi-level lotsizing. OR Spektrum 19:87–96 Süral H, Denizel M, Van Wassenhove LN (2006) Lagrangean relaxation based heuristics for lot sizing with setup times. Working paper no: SUGSM-06-01, Faculty of Management, Sabanci University, Istanbul

123