A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times

References

• Akartunal K, Miller AJ (2012) A computational analysis of lower bounds for big bucket production planning problems. Computational Optim. Appl. 53(3):729–753.Crossref, Google Scholar
• Akartunali K, Fragkos I, Miller A, Wu T (2016) Local cuts and two-period convex hull closures for big-bucket lot-sizing problems. INFORMS J. Comput. Forthcoming.Link, Google Scholar
• Barany I, Van Roy T, Wolsey LA (1984) Uncapacitated lot-sizing: The convex hull of solutions. Math. Programming Stud. 22:32–43.Crossref, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Belvaux G, Wolsey LA (2000) bc—prod: A specialized branch-and-cut system for lot-sizing problems. Management Sci. 46(5):724–738.Link, Google Scholar
• Ben Amor H, Desrosiers J, de Carvalho JMV (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463.Link, Google Scholar
• Bergner M, Caprara A, Ceselli A, Furini F, Lübbecke ME, Malaguti E, Traversi E (2014) Automatic Dantzig-Wolfe reformulation of mixed integer programs. Math. Programming 149(1):391–424.Google Scholar
• Caprara A, Furini F, Malaguti E (2013) Uncommon Dantzig-Wolfe reformulation for the temporal knapsack problem. INFORMS J. Comput. 25(3):560–571.Link, Google Scholar
• Danna E, Rothberg E, Le Pape C (2005) Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Programming 102(1):71–90.Crossref, Google Scholar
• Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8(1):101–111.Link, Google Scholar
• de Araujo SA, De Reyck B, Degraeve Z, Fragkos I, Jans R (2015) Period decompositions for the capacitated lot sizing problem with setup times. INFORMS J. Comput. 27(3):431–448.Link, Google Scholar
• Degraeve Z, Jans R (2007) A new Dantzig-Wolfe reformulation and branch-and-price algorithm for the capacitated lot-sizing problem with setup times. Oper. Res. 55(5):909–920.Link, Google Scholar
• Degraeve Z, Peeters M (2003) Optimal integer solutions to industrial cutting-stock problems: Part 2, benchmark results. INFORMS J. Comput. 15(1):58–81.Link, Google Scholar
• du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1–3):229–237.Crossref, Google Scholar
• Elhallaoui I, Villeneuve D, Soumis F, Desaulniers G (2005) Dynamic aggregation of set-partitioning constraints in column generation. Oper. Res. 53(4):632–645.Link, Google Scholar
• Eppen GD, Martin RK (1987) Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper. Res. 35(6):832–848.Link, Google Scholar
• Fisher ML (2004) The Lagrangian relaxation method for solving integer programming problems. Management Sci. 50(12_suppl.):1861–1871.Link, Google Scholar
• Geoffrion AM (1974) Lagrangean relaxation for integer programming. Balinski M, ed. Approaches to Integer Programming, Mathematical Programming Studies, Vol. 2 (Springer, Berlin), 82–114.Crossref, Google Scholar
• Guignard M, Kim S (1987) Lagrangean decomposition: A model yielding stronger Lagrangean bounds. Math. Programming 39(2):215–228.Crossref, Google Scholar
• Jans R, Degraeve Z (2004) Improved lower bounds for the capacitated lot sizing problem with setup times. Oper. Res. Lett. 32(2):185–195.Crossref, Google Scholar
• Kleindorfer PR, Newson EFP (1975) A lower bounding structure for lot-size scheduling problems. Oper. Res. 23(2):299–311.Link, Google Scholar
• Larsson T, Patriksson M (2006) Global optimality conditions for discrete and nonconvex optimization—With applications to Lagrangian heuristics and column generation. Oper. Res. 54(3):436–453.Link, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Manne AS (1958) Programming of economic lot sizes. Management Sci. 4(2):115–135.Link, Google Scholar
• Martin A (1999) Integer programs with block angular structure. PhD thesis, Konrad-Zuse-Zentrum für Informationstechnik Berlin.Google Scholar
• Martin B, Lübbecke ME, Malaguti E, Traversi E (2011) Partial convexification of general MIPs by Dantzig-Wolfe reformulation. Günlük O, Woeginger GJ, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 6655 (Springer-Verlag, Berlin), 39–51.Crossref, Google Scholar
• Miller A, Nemhauser GL, Savelsbergh MW (2000) Solving multi-item capacitated lot-sizing problems with setup times by branch-and-cut. CORE Discussion Papers 2000039, Université catholique de Louvain, Center for Operations Research and Econometrics, Belgium.Google Scholar
• Müller LF, Spoorendonk S, Pisinger D (2012) A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times. Eur. J. Oper. Res. 218(3):614–623.Crossref, Google Scholar
• Pimentel CMO, Pereira e Alvelos F, de Carvalho JMV (2010) Comparing Dantzig-Wolfe decompositions and branch-and-price algorithms for the multi-item capacitated lot-sizing problem. Optim. Methods Software 25(2):299–319.Crossref, Google Scholar
• Pochet Y, Wolsey LA (2006) Production Planning by Mixed Integer Programming, Springer Series in Operations Research and Financial Engineering (Springer-Verlag, New York).Google Scholar
• Süral H, Denizel M, Van Wassenhove LN (2009) Lagrangean relaxation based heuristics for lot sizing with setup times. Eur. J. Oper. Res. 194(1):51–63.Crossref, Google Scholar
• Trigeiro WW, Thomas LJ, McClain JO (1989) Capacitated lot sizing with setup times. Management Sci. 35(3):353–366.Link, Google Scholar
• Vanderbeck F (1998) Lot-sizing with start-up times. Management Sci. 44(10):1409–1425.Link, Google Scholar
• Vanderbeck F (2005) Implementing mixed integer column generation. Desaulniers G, Desrosiers J, Solomon M, eds. Column Generation (Springer, New York), 331–358.Crossref, Google Scholar
• Vanderbeck F (2011) Branching in branch-and-price: A generic scheme. Math. Program. 130(2):249–294.Crossref, Google Scholar
• Vanderbeck F, Savelsbergh MWP (2006) A generic view of Dantzig-Wolfe decomposition in mixed integer programming. Oper. Res. Lett. 34(3):296–306.Crossref, Google Scholar
• Van Vyve M, Wolsey LA (2006) Approximate extended formulations. Math. Programming 105(2–3):501–522.Crossref, Google Scholar
• Villeneuve D, Desrosiers J, Lübbecke ME, Soumis F (2005) On compact formulations for integer programs solved by column generation. Ann. Oper. Res. 139(1):375–388.Crossref, Google Scholar
• Wagner HM, Whitin TM (1958) Dynamic version of the economic lot size model. Management Sci. 5(1):89–96.Link, Google Scholar