This article was downloaded by: [186.217.236.55] On: 19 June 2019, At: 11:49 Publisher: Institute for Operations Research and the Management Sciences (INFORMS) INFORMS is located in Maryland, USA INFORMS Journal on Computing Publication details, including instructions for authors and subscription information: http://pubsonline.informs.org Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times Silvio Alexandre de Araujo, Bert De Reyck, Zeger Degraeve, Ioannis Fragkos, Raf Jans To cite this article: Silvio Alexandre de Araujo, Bert De Reyck, Zeger Degraeve, Ioannis Fragkos, Raf Jans (2015) Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times. INFORMS Journal on Computing 27(3):431-448. https://doi.org/10.1287/ ijoc.2014.0636 Full terms and conditions of use: https://pubsonline.informs.org/page/terms-and-conditions This article may be used only for the purposes of research, teaching, and/or private study. Commercial use or systematic downloading (by robots or other automatic processes) is prohibited without explicit Publisher approval, unless otherwise noted. For more information, contact permissions@informs.org. The Publisher does not warrant or guarantee the article’s accuracy, completeness, merchantability, fitness for a particular purpose, or non-infringement. Descriptions of, or references to, products or publications, or inclusion of an advertisement in this article, neither constitutes nor implies a guarantee, endorsement, or support of claims made of that product, publication, or service. Copyright © 2015, INFORMS Please scroll down for article—it is on subsequent pages INFORMS is the largest professional society in the world for professionals in the fields of operations research, management science, and analytics. For more information on INFORMS, its publications, membership, or meetings visit http://www.informs.org http://pubsonline.informs.org https://doi.org/10.1287/ijoc.2014.0636 https://doi.org/10.1287/ijoc.2014.0636 https://pubsonline.informs.org/page/terms-and-conditions http://www.informs.org INFORMS Journal on Computing Vol. 27, No. 3, Summer 2015, pp. 431–448 ISSN 1091-9856 (print) � ISSN 1526-5528 (online) http://dx.doi.org/10.1287/ijoc.2014.0636 © 2015 INFORMS Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times Silvio Alexandre de Araujo Departamento de Matemática Aplicada, Universidade Estadual Paulista, São José do Rio Preto SP, 15054-000, Brazil, saraujo@ibilce.unesp.br Bert De Reyck UCL School of Management, University College London, London WC1E 6BT, United Kingdom, b.dereyck@ucl.ac.uk Zeger Degraeve Melbourne Business School, University of Melbourne, Carlton VIC 3053, Australia; and Department of Management Science and Operations, London Business School, Regents Park, London NW1 4SA, United Kingdom, z.degraeve@mbs.edu Ioannis Fragkos Rotterdam School of Management, Erasmus University Rotterdamn, 3062 PA Rotterdam, Netherlands, ifragkos@rsm.nl Raf Jans HEC Montréal and GERAD, Montréal, Canada H3T 2A7, raf.jans@hec.ca We study the multi-item capacitated lot sizing problem with setup times. Based on two strong reformula- tions of the problem, we present a transformed reformulation and valid inequalities that speed up column generation and Lagrange relaxation. We demonstrate computationally how both ideas enhance the performance of our algorithm and show theoretically how they are related to dual space reduction techniques. We compare several solution methods and propose a new efficient hybrid scheme that combines column generation and Lagrange relaxation in a novel way. Computational experiments show that the proposed solution method for finding lower bounds is competitive with textbook approaches and state-of-the-art approaches found in the literature. Finally, we design a branch-and-price-based heuristic and report computational results. The heuristic scheme compares favorably or outperforms other approaches. Keywords : lot sizing; column generation; Lagrange relaxation; branch and price; heuristics History : Accepted by Karen Aardal, Area Editor for Design and Analysis of Algorithms; received September 2013; revised June 2014, October 2014; accepted November 2014. Published online June 30, 2015. 1. Introduction Lot sizing problems have been studied extensively by the operations research community in the past five decades. Despite the vast progress of mixed-integer programming (MIP) theory and software, many lot sizing problems remain computationally challenging to solve in practice. In this paper, we study a classical lot sizing problem, namely the multi-item capacitated lot sizing problem with setup times (CLST). Given a discrete time horizon, the objective of CLST is to find a minimum cost production plan that satisfies the demand for all items and respects the per-period capacity constraints. A setup operation is necessary whenever a positive amount is produced in a period. Such a setup entails a cost and consumes capacity. Moreover, production is done on a single machine that can produce many items in any given period, and no dependencies among items exist other than the single-machine capacity restriction. CLST is clas- sified as a multi-item, single-machine, single-level, big-bucket capacitated lot sizing problem. Despite the simple problem statement and formulation, CLST instances can be computationally challenging even for modern mixed-integer programming software. In particular, obtaining tight lower bounds and good feasible solutions requires considerable effort, if at all possible, even for instances with a few hundred inte- ger variables. The aim of this paper is to design a fast heuris- tic procedure for CLST that provides good solutions and a strong lower bound used to assess the solution quality. Period Dantzig-Wolfe decompositions of two network reformulations of CLST are proposed. The main advantage of the proposed decompositions is 431 mailto:saraujo@ibilce.unesp.br mailto:b.dereyck@ucl.ac.uk mailto:z.degraeve@mbs.edu mailto:ifragkos@rsm.nl mailto:raf.jans@hec.ca de Araujo et al.: Period Decompositions for the CLST 432 INFORMS Journal on Computing 27(3), pp. 431–448, © 2015 INFORMS that they provide a lower bound that is stronger than those of the standard and network formulations. The potential downside is their computational tractabil- ity: when computed with column generation, the already large number of variables of the network formulations and their inherent degeneracy could lead to long solution times for the restricted master (RM) programs and only minor bound improvements per iteration. Although there exists limited compu- tational experience with decompositions of extended formulations on this problem, evidence suggests that simplex-based solvers do not exhibit good conver- gence behavior (Jans and Degraeve 2004). We pro- pose a novel, considerably faster subgradient-based hybrid scheme that combines Lagrange relaxation and column generation. This scheme gives valid lower bounds of excellent quality and outperforms pure simplex-based column generation, Lagrange relax- ation, and subgradient-based column generation (in which the RM programs are solved with subgradient optimization). Further, we enhance the performance of our algorithm by utilizing two new dual-space reduction techniques. First, we show how a primal space reformulation can lead to improved perfor- mance of dual-based algorithms during column gen- eration. Second, we employ a class of valid inequal- ities introduced by Wolsey (1989) in the context of single-item problems with startup costs and show how this corresponds to adding dual-optimal inequal- ities in the dual space of the RM program (Ben Amor et al. 2006). The new subproblems remain tractable and the performance of the hybrid column generation scheme is improved further. The new hybrid scheme is embedded in a heuris- tic branch-and-price framework, designed specifically to obtain good feasible solutions fast. To achieve this, we recover a primal solution of the RM using the volume algorithm of Barahona and Anbil (2000) and branch on the resulting fractional setup vari- ables. Moreover, we integrate in a customized fash- ion recent MIP-based heuristic approaches, such as relaxation induced neighborhoods and selective dives (Danna et al. 2005), with established ones such as the forward/backward smoothing heuristic of Trigeiro et al. (1989). Extensive computational experiments show that the branch-and-price heuristic performs very well against other competitive approaches. The remainder of this paper is organized as fol- lows. Section 2 provides a brief literature review. Section 3 describes CLST formulations and §4 their Dantzig-Wolfe decompositions. Section 5 describes customized procedures for solving the subproblems. Section 6 describes the hybrid scheme and §7 the branch-and-price heuristic. Finally, §8 presents com- putational results and §9 concludes with comments and directions for future research. 2. Literature Review The literature on capacitated lot sizing problems is vast. A broad categorization would distinguish research related to exact and heuristic methods. We review both streams of literature, because our approach utilizes exact methods but also constructs heuristic solutions. With respect to the more recent research on exact approaches, Van Vyve and Wolsey (2006) suggest an approximate extended formulation based on the network reformulation of Eppen and Martin (1987) that uses a single parameter to control the trade- off between the number of variables and the lower bound strength. They show that selecting small val- ues of that parameter is sufficient to solve hard prob- lems, especially when a redundant row that facil- itates the solver to generate cuts is added in the formulation. Degraeve and Jans (2007) discuss the structural deficiency of the decomposition proposed by Manne (1958), which only allows the computa- tion of a lower bound for the problem. Furthermore, they show the correct implementation of the Dantzig- Wolfe decomposition principle for CLST and develop a branch-and-price algorithm. Pimentel et al. (2010) propose three Dantzig-Wolfe decompositions of the standard formulation of CLST, and compare the per- formance of the corresponding branch-and-price algo- rithms. Specifically, they describe and compare the item, period, and the simultaneous item and period decompositions. Belvaux and Wolsey (2000) devel- oped BC-PROD, a specialized branch-and-cut system for generic lot sizing problems. Some of the corner- stone work that is less recent include the variable redefinition approach of Eppen and Martin (1987), the use of valid inequalities (Barany et al. 1984), and the simple plant location reformulation of Krarup and Bilde (1977). Recently, many authors (Alfieri et al. 2002, Pochet and Van Vyve 2004, Denizel et al. 2008 and Süral et al. 2009) have used such alter- native formulations with stronger linear relaxations for the CLSP. Finally, Miller et al. (2000b, 2003) also derive strong valid inequalities from simplified mod- els, which are single-period relaxations with preced- ing inventory. The single-period models contain the capacity constraint and demand constraints for mul- tiple items taking into account only the preceding inventory level. Heuristic approaches have also received consider- able attention. The seminal paper of Trigeiro et al. (1989) proposed a per item Lagrange relaxation and presented a smoothing heuristic (TTM) that was able to find good feasible solutions quickly. Heuristics that use several iterations of solving a reduced problem such as relax-and-fix and relax-and-optimize, have been successfully used by a number of researchers (Pochet and Wolsey 2006, Stadtler 2007, Helber and Sahling 2010). Süral et al. (2009) designed a Lagrange de Araujo et al.: Period Decompositions for the CLST INFORMS Journal on Computing 27(3), pp. 431–448, © 2015 INFORMS 433 relaxation-based heuristic that outperforms TTM for problems without setup costs. Other recent heuris- tic approaches include, among others, the cross- entropy Lagrange hybrid algorithm (Caserta and Rico 2009), the adaptive large neighborhood search algo- rithm (Müller et al. 2012), the LP-based heuristic and curtailed branch and bound (Denizel and Süral 2006), and the iterative production estimate (IPE) heuristic (Pochet and Van Vyve 2004). A notable recent approach is that of Tempelmeier (2011), who uses a set-partitioning approximation and column generation-based heuristic to solve a multi-item capac- itated model with random demands and a fill-rate constraint. A very comprehensive review of heuristic approaches can be found in Buschkühl et al. (2010). Relevant to the current work is also the decomposi- tion approach proposed in Jans and Degraeve (2004). The authors propose a period decomposition of a strong reformulation proposed in Eppen and Martin (1987). They obtain improved lower bounds, but their computational experiments show that standard com- putation schemes may be very time consuming for hard problems. Finally, Fiorotto and de Araujo (2014) build upon and extend the Lagrange relaxation pre- sented in Jans and Degraeve (2004) by developing a heuristic for the capacitated lot sizing problem with parallel machines. The main contributions of the present work are (a) the development and comparison of two period Dantzig-Wolfe network reformulations for CLST; (b) the development of a methodology that circum- vents the computational difficulties of extended for- mulations through the design of a stabilization algo- rithm, and the use of problem-specific inequalities in the customized algorithm that solves the subprob- lems; (c) the development of a state-of-the-art branch- and-price heuristic that integrates and customizes several recent advances such as the volume algorithm (Barahona and Anbil 2000), relaxation induced neigh- borhoods, and selected dives (Danna et al. 2005); and finally, (d) the presentation of computational results that suggest the competitiveness of the proposed scheme against other approaches. Section 3 gives an overview of several formulations that are used throughout the paper. 3. Formulations for the Capacitated Lot Sizing Problem In this section we present different formulations for the capacitated lot sizing problem: the regular formu- lation (CL), the shortest path formulation (SP) pro- posed in Eppen and Martin (1987), a transformed shortest path formulation (SPt), the facility location formulation (FL) studied in Krarup and Bilde (1977), and the facility location formulation with precedence constraints (FLp). The notation conv4P5 of problem P signifies the convex hull of the polyhedron defined by the set of constraints of problem P . 3.1. The Regular Formulation (CL) The regular formulation for the capacitated lot sizing problem with setup times is described by the follow- ing sets, parameters, and decision variables (Trigeiro et al. 1989). Sets I 2 set of items, = 811 0 0 0 1 �I �9 T 2 set of time periods, = 811 0 0 0 1 �T �9 Parameters dit2 demand of item i in period t, ∀ i ∈ I , ∀ t ∈ T sditk2 sum of demand of item i, from period t until k, ∀ i ∈ I , ∀ t1 k ∈ T 2 k ≥ t hcit2 unit holding cost for item i in period t, ∀ i ∈ I , ∀ t ∈ T scit2 setup cost for item i in period t, ∀ i ∈ I , ∀ t ∈ T vcit2 variable production cost for item i in period t, ∀ i ∈ I , ∀ t ∈ T fci2 unit cost for initial inventory for item i, ∀ i ∈ I stit2 setup time for item i in period t, ∀ i ∈ I , ∀ t ∈ T vtit2 variable production time for item i in period t, ∀ i ∈ I , ∀ t ∈ T capt2 time capacity in period t,∀ t ∈ T Decision variables xit2 production quantity of item i in period t, ∀ i ∈ I , ∀ t ∈ T yit = 1 if setup for item i in period t, 0 otherwise, ∀ i ∈ I , ∀ t ∈ T sit2 inventory for item i at the end of period t, ∀ i ∈ I , ∀ t ∈ T si02 amount of initial inventory for item i, ∀ i ∈ I The mathematical formulation of CLST is then as follows: min { ∑ i∈I fcisi0 + ∑ i∈I ∑ t∈T 4scityit+vcitxit+hcitsit5 } 4CL5 (1) s0t0 si1 t−1 +xit =dit+sit ∀ i∈ I1∀ t∈T (2) ∑ i∈I 4stityit+vtitxit5≤capt ∀ t∈T (3) xit ≤min ( capt−stit vtit 1sdit�T � ) yit ∀ i∈ I1∀ t∈T (4) yit ∈801191xit ≥01sit ≥01si0 ≥01si�T � =0 ∀ i∈ I1∀ t∈T 0 (5) The objective function (1) minimizes the setup cost, variable production cost, inventory holding cost, and de Araujo et al.: Period Decompositions for the CLST 434 INFORMS Journal on Computing 27(3), pp. 431–448, © 2015 INFORMS initial inventory cost. Constraints (2) are the demand constraints: inventory carried over from the previous period and production in the current period can be used to satisfy current demand and build up inven- tory. As in Vanderbeck (1998), we deal with possible infeasible problems by allowing for initial inventory (si0), which is available in the first period at a large cost, fci. There is no setup required for initial inven- tory. Next, there is a constraint on the available capac- ity in each period (3). Constraint (4) forces the setup variable to one if any production takes place in that period. Finally, we have the nonnegativity and inte- grality constraints (5) and the ending inventory is set to 0. 3.2. The Shortest Path Formulation (SP) Next, model (1)–(5) is reformulated using the variable redefinition approach of Eppen and Martin (1987). Define the following parameters: cvitk2 total production and holding cost for pro- ducing item i in period t to satisfy demand for the periods t until k, cvitk = vcitsditk + ∑k s=t+1 ∑s−1 u=t hciudis3 ciit2 total production and holding cost for ini- tial inventory for item i to satisfy demand from period 1 up to period t, ciit = fcisdi1t + ∑t s=2 ∑s−1 u=1 hciudis0 We also have the following new variables: zitk2 fraction of the production plan for item i, where production in period t satisfies demand from period t to period k, xit = ∑�T � k=t sditkzitk, ∀ i ∈ I1 ∀ t ∈ T 3 pit2 fraction of the initial inventory plan for item i, where demand is satisfied for the first t periods, si0 = ∑�T � t=1 sdi1tpit , ∀ i ∈ I . The network reformulation is then as follows: min { ∑ i∈I ∑ t∈T 4scityit+ciitpit5 + ∑ i∈I ∑ t∈T �T � ∑ k=t cvitkzitk } 4SP5 (6) s0t0 �T � ∑ k=1 4zi1k+pik5=1 ∀ i∈ I (7) t−1 ∑ j=1 zijt−1 +pit−1 = �T � ∑ k=t zitk ∀ i∈ I1∀ t∈T \819 (8) ∑ i∈I stityit+ ∑ i∈I �T � ∑ k=t vtitsditkzitk ≤capt ∀ t∈T (9) �T � ∑ k=t zitk ≤yit ∀ i∈ I1∀ t∈T (10) yit ∈801191pit ≥0 ∀ i∈ I1∀ t∈T (11) zitk ≥0 ∀ i∈ I1∀ t∈T 1∀k∈T 1 k≥ t0 (12) The objective function (6) minimizes the total costs. Constraints (7) and (8) define the flow balance con- straints of each node (i1 t), which ensure that demand is satisfied. For each item, a unit flow is sent through the network, imposing that its demand has to be satis- fied without backlogging. The capacity constraints (9) limit the sum of the total setup times and production times to the available capacity in each period. Con- straint (10) defines the setup forcing for each item. Finally, setup decisions are binary (11). 3.3. Transformed Shortest Path Formulation (SPt) We reformulate constraints (7) and (8) of SP in a way that reduces the dual feasible region of its LP relax- ation. The aim is to achieve a better convergence for algorithms that operate in the dual space. The idea is to substitute, for each item, the demand balance constraint of period t with the sum of the demand balance constraints of the first t periods. Doing so, constraints (7) and (8) are replaced with �T � ∑ k=t pik + t ∑ j=1 �T � ∑ k=t zijk = 1 ∀ i ∈ I1 ∀ t ∈ T 0 (13) We denote the resulting transformed formulation SPt. Eppen and Martin (1987) showed that their net- work reformulation corresponds to a shortest path problem defined on an acyclic graph. The demand constraints (7) and (8) express the flow balance in each node of this graph. Equation (13) imposes that the flow of the cut set defined by the s − t cut Ct = 4801 0 0 0 1 t − 19 ∪ 8t1 0 0 0 1 �T �95 is equal to one. Figure 1 illustrates a single-item four-period example with no initial inventory. Equation (8) for period 3 reads z12 + z22 = z33 + z34, which corresponds to the flow balance of node 2. For the same period, (13) sets the total flow through the edges connecting the sets of nodes {0, 1, 2} and {3, 4} equal to one, i.e., 1 = z13 +z14 +z23 + z24 + z33 + z34. The idea behind this transformation is that of dual space reduction. Let D be the feasible dual space asso- ciated with constraints (7) and (8), and D′ the one associated with constraints (13). If vi1 and vit are the 1 0 Z12 Z13 Z14 Z11 Z22 Z23 Z24 Z33 Z44 Z34 1 2 3 4 Figure 1 A Single-Item Four-Period Example with No Initial Inventory de Araujo et al.: Period Decompositions for the CLST INFORMS Journal on Computing 27(3), pp. 431–448, © 2015 INFORMS 435 dual values of (7) and (8) and v̄it the dual values of (13), then D=                    vit ∈< ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ vit−vi1k+1 ≤cvitk ∀ i∈ I1 t1k∈T 2 t≤k< �T � vi1 −vit+1 ≤ciit ∀ i∈ I1t∈T \8�T �9 vit ≤cvit�T �1 ∀ i∈ I1 t∈T vi1 ≤cii�T �1 ∀ i∈ I                    3 D′ =            v̄it ∈< ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ t ∑ l=1 v̄il ≤min8ciit1cvi1t9 ∀ i∈ I1 t∈T k ∑ l=t v̄il ≤cvitk ∀ i∈ I1 t1k∈T 2 k≥ t0            Theorem 1. D′ ⊆D. Proof. See the online supplement (available as supplemental material at http://dx.doi.org/10.1287/ ijoc.2014.0636). � For the numerical example illustrated in Figure 1, we observe from the definitions of D and D′ for �T � = 4 and �I � = 1 that if we define �= cv11, the point 4v11v21v31v45 = 4cv11 + �1�1�1�5 is feasible for D but infeasible for D′. Transformed formulations like the SPt imply a denser form of the constraint matrix, which, in the context of the simplex method, might result in more pivots and therefore be less efficient. Since our algo- rithm works in the dual space, it is interesting to investigate computationally if the dual space reduc- tion of subsystem (7) and (8) is beneficial. 3.4. Facility Location Formulation (FL) CL can be reformulated using variables originally employed in facility location problems. To the best of our knowledge, the first paper that used facility loca- tion variables to formulate lot sizing models was the work of Krarup and Bilde (1977). The resulting model (FL) is described as follows. Parameters csitk2 total production and holding cost for produc- ing item i in period t to satisfy demand of period k, csitk = 4vcit + ∑k−1 u=t hciu5dik; cuit2 initial inventory and holding cost for item i, to satisfy demand in period t, cuit = 4fci + ∑t−1 u=1 hciu5dit . We also define the following variables: witk2 fraction of demand for item i in period k that is satisfied by production in period t, xit = ∑�T � k=t dikwitk, ∀ i ∈ I1 ∀ t ∈ T ; spit2 fraction of demand for item i in period k that is satisfied by initial inventory, si0 = ∑�T � t=1 spitdit , ∀ i ∈ I . The facility location reformulation is then as follows: min { ∑ i∈I ∑ t∈T 4scityit + cuitspit5 + ∑ i∈I ∑ t∈T �T � ∑ k=t csitkwitk } 4FL5 (14) s0t0 spit + t ∑ k=1 wikt = 1 ∀ i ∈ I1 ∀ t ∈ T (15) ∑ i∈I stityit + ∑ i∈I �T � ∑ k=t vtitdikwitk ≤ capt ∀ t ∈ T (16) witk ≤ yit ∀ i ∈ I1 ∀ t ∈ T 1 ∀k ∈ T 1 k ≥ t (17) yit ∈ 801191 spit ≥ 0 ∀ i ∈ I1 ∀ t ∈ T (18) witk ≥ 0 ∀ i ∈ I1 ∀ t ∈ T 1 ∀k ∈ T 1 k ≥ t0 (19) The objective function (14) minimizes the total cost, which consists of the setup cost, the aggregated pro- duction and holding costs, and the initial inven- tory and holding costs. Equation (15) corresponds to the demand constraints (2) and state that period t demand must be covered by a combination of initial inventory and production in periods 811 0 0 0 1 t9. The capacity constraints (14) are in exact correspondence with (4). The setup constraints (17) do not allow any production in period t unless a setup is done and the non-negativity conditions (18) and (19) complete the FL formulation. 3.5. Facility Location Formulation with Precedence Constraints (FLp) Many extended formulations are often degenerate or have multiple optimal solutions. The decision vari- ables of formulation (14)–(19) indicate not only the amount of production of each item in each period, as the original decision variables, but also allocate each production amount to forward demands. Mul- tiple alternative solutions of (14)–(19) arise when the allocation of a given production amount to forward demands is not unique. The existence of multiple alternative solutions in the extended formulation may degrade the efficiency of column generation. Hence, the addition of valid inequalities in the subprob- lem that cut off some of the primal space con- taining alternative optimal solutions, may lead to improved convergence, as it prevents the subprob- lem from generating columns that describe alterna- tive solutions. A class of such valid inequalities is described next. Observation 1. There exists an optimal solution of FL with wit1 k−1 ≥ witk for all i ∈ I, t, k ∈ T 2 t + 1 ≤ k ≤ �T � and spi1 t−1 ≥ spit for all i ∈ I and t ∈ T \819. http://dx.doi.org/10.1287/ijoc.2014.0636 http://dx.doi.org/10.1287/ijoc.2014.0636 de Araujo et al.: Period Decompositions for the CLST 436 INFORMS Journal on Computing 27(3), pp. 431–448, © 2015 INFORMS We will refer to the above valid inequalities as prece- dence constraints. Observation 1 is used in Wosley’s Wolsey (1989) study of the facility location formula- tion in the context of lot sizing problems with startup costs and no capacity constraints. A short proof can be found in the online supplement. FL is not a minimal image of the conv(CL) in the sense that there exists a subset of conv(FL) that is the image of all extreme points of conv(CL). A key insight is that not all feasible points of FL are necessary for an accurate representa- tion of the original feasible space of the problem (CL). This is important from a computational perspective, because columns whose convex combination repre- sents redundant points need to be generated on the fly, resulting in more column generation iterations and in a possibly amplified tailing-off effect. The precedence constraints wit1 k−1 ≥ witk can be used alongside the setup, forcing witt ≤ yit in place of witk ≤ yit for all i ∈ I , t, k ∈ T 2 t+ 1 ≤ k. The FL formu- lation with the primal valid inequalities is written as min { ∑ i∈I ∑ t∈T 4scityit+cuitspit5+ ∑ i∈I ∑ t∈T �T � ∑ k=t csitkwitk } 4FLp5 s0t0 witt ≤yit ∀ i∈ I1∀ t∈T (20) wit1k−1 ≥witk ∀ i∈ I1∀ t∈T 1∀k∈T 1 k>t0 (21) 4155–41651 4185–4195 The idea behind the inclusion of constraints (21) is that of primal space reduction. Although it is reason- able to assume that a decomposition scheme that uses (21) in the subproblem would deliver an improved lower bound compared to not including them, we show that this is not the case. This is because the objective function cost depends on the setup deci- sions and the amount produced of each item, which remains the same after the inclusion of constraints (21). Rather, (21) accelerates the column generation conver- gence because the feasible space of eligible columns is reduced. 4. Period Dantzig-Wolfe Decompositions 4.1. Formulations We formulate period decompositions of the CLST starting from formulations SP, SPt, FL, and FLp. We denote each decomposition formulation by append- ing /P to the original notation. For example, SP/P denotes the period decomposition of the shortest path formulation. The demand balance constraints of each formulation are the complicating constraints, and the capacity and setup forcing constraints of each period form the subproblems. We focus on period decom- positions of network formulations because their lin- ear programming (LP) relaxations provide improved lower bounds compared to the LP relaxation of the corresponding extended formulations, since the sub- problems do not have the integrality property (Geof- frion 1974). Note that an item decomposition of any of the above extended formulations would lead to sub- problems that have the integrality property. Therefore the decomposition lower bound would be the same as the one obtained by the LP relaxation of the original extended formulation (Jans and Degraeve 2004). The formulation of the period decomposition of SP, SP/P, is described in detail in Jans and Degraeve (2004). The formulation of the period decomposi- tion of SPt, SPt/P is very similar to SP/P and we skip it for brevity. Instead, we present the period decompositions of FL and FLp. To this end, let us define by St the index set of extreme point production plans of the subproblem for period t, i.e., St 2=8q∈extr4conv84witk1yit5i∈I1k≥t � 4165–4195959. We associate a decision variable �tq with the fraction of the extreme point q of subproblem t that is used in a feasible solution. If we denote by 4w̄ q itk1ȳ q it5 the com- ponents of point q, its cost can be written as cttq = ∑ i∈I 4scit ȳ q it+ ∑�T � k=t csitkw̄ q itk5. Then the master program can be formulated as follows: min { ∑ t∈T ∑ q∈St cttq�tq + ∑ i∈I ∑ t∈T cuitspit } 4FL/P5 (22) s0t0 spit+ t ∑ l=1 ∑ q∈Sl w̄ q itk�lq =1 ∀ i∈ I ∀ t∈T 6�it7 (23) ∑ q∈St �tq =1 ∀ t∈T 6�t7 (24) yit = ∑ q∈St ȳ q it�tq ∀ i∈ I ∀ t∈T (25) �tq ≥01 yit ∈801191 spit ≥0 ∀ i∈ I1∀q∈St1∀ t∈T 0 (26) The objective function (22) minimizes the total cost of the initial inventory and the cost of the production plans chosen in each period. Constraints (23) model demand and correspond to constraints (15) in the standard formulation. The convexity constraints (24) and the non-negativity constraints (26) enforce a con- vex combination. The setup variables definition is given in (25). The integrality must be imposed on the original setup variables (26). The constraint coefficient parameters 4w̄ q itk1ȳ q it5 are defined by the subproblem extreme points. The subproblem objective function minimizes the reduced cost over the extreme points. Specifically, the period t subproblem reads: min { ∑ i∈I scityit+ ∑ i∈I �T � ∑ k=t 4csitk−�ik5witk } 4SUB5 (27) s0t0 ∑ i∈I stityit+ ∑ i∈I �T � ∑ k=t vtitdikwitk ≤capt (28) de Araujo et al.: Period Decompositions for the CLST INFORMS Journal on Computing 27(3), pp. 431–448, © 2015 INFORMS 437 witk ≤yit ∀i∈ I1∀k∈T 2 k≥ t (29) yit ∈801191witk ≥0 ∀i∈ I1∀k∈T 2 k≥ t0 (30) The period decomposition of the formulation FLp has the same master problem. However, the subprob- lem, denoted SUBp, is different because it includes the precedence constraints (20) and (21) in place of (29). 4.2. Lower Bounds It is interesting to investigate the lower bound qual- ity of the proposed decompositions. To this end, let v̄FL/P be the optimal objective value of the linear relax- ation of the decomposed model FL/P (22)–(26). Also, let v̄FLp/P 1v̄SP/P and v̄SPt/P be the corresponding lower bounds obtained by the linear relaxation of FLp/P, SP/P, and SPt/P, respectively. To obtain a first result, we will need the following definition and lemma. Definition 1 (Ben Amor et al. 2006). Let D be the dual space polyhedron of a linear program and D∗ be the set of its optimal solutions. Also, assume a new set of constraints ET�≤e that cuts off part of the dual space. If D∗ ⊆8�2 ET�≤e9, then ET�≤e is called a set of dual-optimal inequalities. If ET�≤e cuts off a nonempty set of dual-optimal solutions but is still satisfied by at least one dual-optimal solution, it is called a set of deep dual-optimal inequalities. Lemma 1. Using subproblem SUBp is equivalent to using subproblem SUB and imposing constraints 4csitk−�ik5di1k+1 ≥ 4csit1k+1 −�i1k+15dik ∀i∈P1t1k∈T 2 t≤k≤�T �−1 (31) in the dual space of the LP master of FL/P. Moreover, these constraints are deep dual-optimal inequalities. Proof. It suffices to show that SUB has the same optimal solution as SUBp whenever (31) holds. Note that vtit can be added to both sides of the inequality, but is omitted since they cancel each other out. There- fore, (31) states that the profit-to-weight ratio of witk should be greater than that of wit1k+1. It follows that there exists an optimal solution of the LP relaxation of SUB when (31) holds, which is also optimal for the LP relaxation of SUBp. Also, SUB has the same structure after branching, so if (31) holds, the prece- dence constraints hold at any node of the branch- and-bound tree, and therefore at an integer optimal solution. Hence, from construction, (31) implies the precedence constraints, that do not cut off all opti- mal solutions. Their equivalence with the precedence constraints and Definition 1 imply that they are deep dual-optimal inequalities. � The next proposition states that all formulations deliver the same lower bound. Proposition 1. v̄SP/P = v̄SPt/P = v̄FLp/P = v̄FL/P . Proof. First, note that v̄SP/P = v̄SPt/P because the cor- responding subproblems have the same set of extreme points, and the linking constraints of SPt/P are lin- ear combinations of those of SP/P. Second, con- sider the subproblem SUBp. The linear transformation zitt =wtt3zitk =wit1k−1 −witk1k>t maps every extreme point 4yit1witk5 of SUBp to a unique extreme point 4yit1zitk) of the SP/P subproblem. Using this trans- formation in FLp/P, the resulting model is exactly SPt/P. On the other hand, every feasible solution of the SPt/P subproblem can be mapped to FLp/P with the inverse transformation, i.e., witt =ztt3witk = ∑k l=tzitl. Hence, v̄SPt/P = v̄FLp/P . Finally, we show that v̄FLp/P = v̄FL/P . To this end, notice that v̄FLp/P ≥ v̄FL/P , since adding constraints to the subproblem can never lead to a worse bound. Denote by v̄′ FL/P the opti- mal value obtained when solving the dual of FL/P amended with the dual restrictions (31). Then v̄′ FL/P = v̄FLp/P from Lemma 1 and v̄′ FL/P ≤ v̄FL/P , since adding cuts to the dual of a primal minimization prob- lem can never increase its optimal value. The result follows. � Interestingly, the above lower bound is stronger than the one obtained by the simultaneous item and period decomposition of formulation CL studied by Pimentel et al. (2010). Let us denote the latter lower bound by v̄CL/P/I . Proposition 2. v̄CL/P/I ≤ v̄SP/P . Proof. See the online supplement. � 5. Solving the Subproblems This section describes two fast customized algorithms used to solve subproblems SUB and SUBp. Note that since the feasible solutions of FLp are in exact corre- spondence with those of SPt, and the subproblem of SP and SPt is common, solving SUB and SUBp implies a solution for all four subproblems. 5.1. A Customized Algorithm for SUB For SUB, the following simple observation plays a key role in the subsequent solution approach. Observation 2. In an optimal solution of the LP relaxation of SUB there exist some ki ≥ t such that witki =yit , ∀i∈ I . This implies that the subset of tight inequalities (29) can be used to substitute out the yit variables in (28). As a result, the LP relaxation of SUB reduces to a lin- ear knapsack problem, which admits a greedy solu- tion similar to the one proposed in Holmberg and Yuan (2000). It follows that an optimal solution of SUB has fractional continuous variables for at most one item. The following algorithm identifies the subset of tight inequalities in Phase I and solves a regular linear knapsack problem in Phase II. de Araujo et al.: Period Decompositions for the CLST 438 INFORMS Journal on Computing 27(3), pp. 431–448, © 2015 INFORMS Algorithm (SUB (for period t)) Phase I ritk ← csitk−�ik vtitdik 1 ∀k∈T �k≥ t1∀i∈ I . Ki ←Ø, P ←8t10001�T �9, Besti ←False1 ∀i∈ I For each i∈ I : While Besti =False: rit ←mink∈P\Ki 8ritk93 ki ←argrit //min ratio calculation Ki ←Ki∪8ki93 Replace rit ← scit+ ∑ k∈Ki 4csitk−�ik5 stit+ ∑ k∈Ki vtitdik //Update set and ratio of If rit>mink∈P\Ki 8ritk9 or Ki =P then //periods merged so far Besti =True //If ratio of merged periods is not min, exit If rit>mink∈P\Ki 8ritk9 then Ki ←Ki\8ki9 //Retain best set of merged periods vcmit ←scit+ ∑ k∈Ki 4csitk−�ik5 vtmit ←stit+ ∑ k∈Ki vtitdik //Define cost and weight of merged periods End If End While End For Phase II Solve a linear knapsack with weights 8vtmit3vtitdik ∀kyKi1i∈ I9 and costs 8csmit3csitk ∀kyKi1i∈ I9. Let 8wmit3witk ∀kyKi1i∈ I9 denote the optimal solution. Set yit ←wmit1 ∀k∈Ki1i∈ I . Return 4yit1witk5 ∀i∈ I1∀k≥ t. Phase I identifies which of the variable upper bound constraints (29) are satisfied as equalities. Then, the value of the setup variable is set equal to the value of the production variable with the most attractive cost-to-weight ratio. If the new ratio is still the most attractive after the substitution, Phase I terminates for that item. If it is not, another constraint (29) is tight for the same item, and the corresponding substitution is made. Phase II solves a linear knapsack problem where all witk with k∈Ki are equated with yit and substituted out. Note that adjusting the algorithm to tackle items with zero setup time or cost is straightfor- ward. Due to Observation 2, algorithm SUB produces an optimal solution of the SUB linear relaxation. After solving the relaxation, a depth-first branch- and-bound algorithm is implemented. Branching is needed only when some wmit is the last variable to enter the knapsack at fractional level, and therefore yit<1. Thus, at most one setup variable is fractional. In addition, branching does not change the problem structure because it either fixes witk to zero when yit =0 or reduces the problem capacity by stit and fixes scit in the objective, when yit =1. For this rea- son, algorithm SUB can be called at each node of the branch-and-bound tree, with different input data. Computational experiments confirm the superiority of this approach compared to simplex-based branch and bound. 5.2. A Customized Algorithm for SUBp The addition of the precedence constraints changes the structure of subproblem SUB and the previous algorithm cannot be employed. However, we can take advantage of the fact that each solution of SUBp corre- sponds to a solution of the SP/P subproblem (9)–(12), whose relaxation is a linear multiple choice knap- sack problem (Jans and Degraeve 2004) that can be solved efficiently using the sorting algorithm of Sinha and Zoltners (1979). Therefore, we solve the subprob- lem (9)–(12) and then map back the solution to SUBp. Sinha and Zoltners (1979) call a variable dominated if there exists another variable, or a convex combina- tion of other variables, that has a smaller or equal weight and a smaller or equal cost. Dominated vari- ables can be eliminated, and the remaining variables enter the knapsack under a greedy sorting criterion. It is important to observe that the nondominated vari- ables form the convex envelope of all variables when graphed in the (weight, cost) space. We use the pro- cedure of Sinha and Zoltners (1979) to solve the lin- ear relaxations of (9)–(12) and develop a customized depth-first branch-and-bound algorithm. The multi- ple choice knapsack structure is preserved in every node of the branch-and-bound tree, but the cost coef- ficients of some variables change as the setup costs change with branching. This means that the convex envelopes do not need to be fully reconstructed in each node, because only a few variables change posi- tions. We use a variant of the algorithm suggested by Graham (1972) to construct and update the con- vex hulls. Graham’s algorithm determines the convex envelope of a set of n points in O4nlogn5 time. This implies that solving the linear relaxation of (9)–(12) in every node takes O4nlogn5 time, and therefore this method has better complexity compared to using the simplex algorithm. 6. Solving the RM Problem: A New Hybrid Algorithm Huisman et al. (2005) discuss how exploiting the rela- tionship between Dantzig-Wolfe decomposition and Lagrange relaxation can lead to the development of improved algorithms that combine the strengths of both methods. They explore two different ways to combine column generation and Lagrange relaxation. First, Lagrange relaxation can be used to solve the RM, by dualizing the linking constraints, and the result- ing near-optimal dual values can be used to price out de Araujo et al.: Period Decompositions for the CLST INFORMS Journal on Computing 27(3), pp. 431–448, © 2015 INFORMS 439 the subproblems. Second, Lagrange relaxation on the original formulation can be employed within column generation, exploiting the fact that both methods solve the same subproblem. Specifically, the RM programs are solved with simplex, and next the RM dual prices are used as a starting point for a number of Lagrange relaxation iterations, during which several negative reduced cost columns can be found and added to the RM at once. We propose a new method, which is a combination of the two previously discussed meth- ods. Specifically, it uses Lagrange relaxation of the RM to solve this RM program, and it also uses Lagrange relaxation on the original formulation to generate new columns. Figure 2 gives a schematic representation of the algorithm. Implementation details can be found in the online supplement. We initialize the column generation process using the heuristic of Trigeiro et al. (1989). This is a fast heuristic that performs several rounds of smooth- ing and rounding operations. For the instances that Trigeiro et al. (1989) generated, their heuristic can find high-quality feasible solutions, giving integrality gaps lower than 3% on most problems. This heuris- tic returns a feasible solution, a lower bound, and a set of Lagrange dual prices of the capacity con- straints. Using the dual of the relaxation of SP or FL, we can then calculate the starting dual prices �it . Also, the feasible solution 4yit1xit5 F is split into per- period columns of the SPt or FLp RM programs. To perform this operation, it is necessary to transform the 4yit1xit5 F solution to the space of the extended formu- lation variables. This can be done by fixing the setup variables to their given values and solving the corre- sponding formulation, which is a shortest path prob- lem. Next, the Lagrange relaxation subroutine uses the modified subgradient method of Crowder (1976) to update the dual prices �it . The modified subgradi- ent method is a variant of the traditional subgradient 0. Initialization: Call TTM. Add feasible solution to master. Initialize �t, �it, vLB, vUB. 1. Lagrange relaxation: Col = FALSE. Call subgradient. If a column prices out: {Return vLB, �it, Col = TRUE; store columns that price out.} 3. Solve restricted master: Call subgradient to solve restricted master. Return vM, �it, �t. 2. Update pool: Enter new columns to master. Move columns with high reduced cost to pool. Col = FALSE? Call volume to obtain a primal solution Return: max (vLB, vM), yit. No Yes Figure 2 The Main Building Blocks of the New Hybrid Algorithm method that incorporates past history in each itera- tion by searching in a direction that is the weighted average of the current vector of violations and the pre- vious searched direction. Computational experiments in Barahona and Anbil (2000) show that the conver- gence of this variant is a lot faster compared to the regular subgradient method. For each updated set of dual prices �it we check if the subproblem solutions price out, using the last obtained dual prices of the convexity constraints, �t . The columns that price out are added to the RM. Existing columns with a high reduced cost are removed from the RM and kept in a separate column pool. Then, the RM problem is solved using subgradient optimization by relaxing the link- ing constraints (23) (Huisman et al. 2005). Specifically, the dualization of constraints (23) decomposes the RM into separate subproblems per period, each of which is of the form min8 ∑ i∈I ∑ q∈St cttq4�it5�tq+ ∑ i∈I 4cuit+�it5· spit− ∑ i∈I�it � ∑ q∈St �tq =13�tq ≥01spit ≥09. These prob- lems are trivially solved by setting the �tq variable that has the minimum cost coefficient to one, and all other variables to zero. The scheme iterates until no column prices out. We then invoke the volume algorithm to obtain an approximate primal solution. In this way, we are able to make better informed branching deci- sions in the subsequent branch-and-price phase. An alternative implementation would be to use the inter- mediate dual prices of the subgradient optimization of the RM problem to price out new columns. Our exper- iments with this strategy revealed that the generated columns are not of good quality, because the interme- diate dual prices of the RM problem price out many columns that do not price out with its terminal dual prices. Instead, using the near-optimal dual prices to warm start the Lagrange relaxation produced better results and resulted in fewer iterations of the hybrid scheme. de Araujo et al.: Period Decompositions for the CLST 440 INFORMS Journal on Computing 27(3), pp. 431–448, © 2015 INFORMS Contrary to existing hybrid algorithms (Bara- hona and Jensen 1998, Degraeve and Peeters 2003, Degraeve and Jans 2007), this scheme relies exclu- sively on Lagrange relaxation. It has the benefits that it (a) avoids the degeneracy issues of the simplex method and therefore exhibits faster convergence and (b) returns good-quality dual prices that help the col- umn generation convergence. Note that the interme- diate value of the RM programs vM is not necessarily a valid upper bound of the column generation lower bound, because it is calculated using Lagrange relax- ation. It is a valid lower bound (Huisman et al. 2005) when no column prices out, and therefore the scheme returns the best bound that is obtained by the RM and by Lagrange relaxation. 7. A Branch-and-Price Heuristic We have combined the hybrid column generation algorithm with heuristic techniques and integrated them in an enumeration scheme, using formula- tion FLp. The goal is to find good feasible solutions fast by exploiting the structure of the network formu- lation and its subproblem. Section 7.1 describes the heuristics employed in each node of the tree. 7.1. Node Heuristics We employ a successive rounding heuristic that uses a smoothing subroutine, which in turn employs some operations of the heuristic of Trigeiro et al. (1989). The successive rounding heuristic gets as input the setup variables produced by the volume algorithm, deter- mines a threshold level, and fixes the setup variables below and above that threshold to 0 and 1, respec- tively. The process iterates for increasing threshold values. Typically, the objective function values of the feasible solutions obtained in this way follow a U -shaped fashion (Degraeve and Jans 2007). There- fore, when the solution quality starts to degrade, the heuristic terminates. Starting from this solution, the smoothing heuristic that searches for an improved feasible solution is applied. The smoothing part starts from the last period and tries to push production backward, such that the Lagrange costs are mini- mized. This is done iteratively until the first period, and if any capacity constraints are violated it per- forms a similar forward operation to recover feasibil- ity. Thus, the rounding/smoothing heuristic scheme searches the feasible space by modifying incremen- tally the proposed setup schedules and produc- tion plans and can be classified as an exploitation heuristic. 7.2. Node Lower Bounds At each node we solve the RM problem using subgra- dient optimization, without generating any columns. If its objective value is lower than the incumbent value, we recover an approximate primal solution using the volume algorithm and use that solution to branch. Else, if the RM objective value is higher than the incumbent value, the hybrid algorithm is invoked to generate columns. During the hybrid algo- rithm iterations, a nondecreasing node lower bound is recorded. If that lower bound comes to exceed the incumbent value, the node is pruned. When the hybrid algorithm terminates and the lower bound is below the incumbent value, the volume algorithm is invoked to recover an approximate primal solution of the RM, which is then used for branching. When the volume algorithm returns all-integer setup vari- ables, we fix these variables and solve the resulting LP problem using formulation CL, which is a general- ized network flow problem for fixed setups (Degraeve and Jans 2007). More details about this procedure can be found in the online supplement of this paper. 7.3. Tree Exploration Strategies Algorithm HBP summarizes the main building blocks of the heuristic branch-and-price algorithm. Algorithm (HBP) Input: LowerBound, UpperBound, CGSolution 4yr it1x r it5, Incumbent 4yh it1x h it5 Output: LowerBound, UpperBound, Incumbent 4yh it1x h it5 Pass←0; NodeLimit←100 B←84i1t5�4yh it =1∧yr it ≥0085∨4yh it =0∧yr it ≤00259 //RINS initialization of explored space Do While Time