Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems

References

• Akartunalı K (2007) Computational methods for big bucket production planning problems: Feasible solutions and strong formulations. Unpublished doctoral thesis, Industrial Engineering, University of Wisconsin-Madison, Madison, WI.Google Scholar
• Akartunalı K, Miller AJ (2009) A heuristic approach for big bucket multi-level production planning problems. Eur. J. Oper. Res. 193(2):396–411.Crossref, Google Scholar
• Akartunalı K, Miller AJ (2012) A computational analysis of lower bounds for big bucket production planning problems. Comput. Optim. Appl. 53(3):729–753.Crossref, Google Scholar
• Andersen K, Cornuéjols G, Li Y (2005) Split closure and intersection cuts. Math. Program. 102(3):457–493.Crossref, Google Scholar
• Anily S, Tzur M, Wolsey LA (2009) Multi-item lot-sizing with joint set-up costs. Math. Program. 119(1):79–94.Crossref, Google Scholar
• Applegate D, Bixby R, Chvátal V, Cook W (2003) Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems. Math. Program. 97(1):91–153.Crossref, Google Scholar
• Applegate DL, Cook W, Dash S, Espinoza DG (2007) Exact solutions to linear programming problems. Oper. Res. Lett. 35(6):693–699.Crossref, Google Scholar
• Atamtürk A, Muñoz JC (2004) A study of the lot-sizing polytope. Math. Program. 99(3):443–465.Crossref, Google Scholar
• Balas E, Margot F (2013) Generalized intersection cuts and a new cut generating paradigm. Math. Program. 137(1):19–35.Crossref, Google Scholar
• Balas E, Saxena A (2008) Optimizing over the split closure. Math. Program. 113(2):219–240.Crossref, Google Scholar
• Barany I, Van Roy TJ, Wolsey LA (1984) Strong formulations for multi-item capacitated lot-sizing. Management Sci. 30(10):1255–1261.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
• Belvaux G, Wolsey LA (2001) Modelling practical lot-sizing problems as mixed-integer programs. Management Sci. 47(7):993–1007.Link, Google Scholar
• Bergner M, Caprara A, Ceselli A, Furini F, Lübbecke ME, Malaguti E, Traversi E (2015) Automatic Dantzig-Wolfe reformulation of mixed integer programs. Math. Program. 149(1):391–424.Crossref, Google Scholar
• Billington PJ, McClain JO, Thomas LJ (1986) Heuristics for multilevel lot-sizing with a bottleneck. Management Sci. 32(8): 989–1006.Link, Google Scholar
• Bitran GR, Matsuo H (1986) The multi-item capacitated lot size problem: Error bounds of Manne’s formulations. Management Sci. 32(3):350–359.Link, Google Scholar
• Boyd EA (1994) Fenchel cutting planes for integer programs. Oper. Res. 42(1):53–64.Link, Google Scholar
• Cadoux F (2010) Computing deep facet-defining disjunctive cuts for mixed-integer programming. Math. Program. 122(2):197–223.Crossref, Google Scholar
• Chvátal V, Cook W, Espinoza D (2013) Local cuts for mixed integer programming. Math. Program. Comput. 5(2):171–200.Crossref, Google Scholar
• Constantino M (1996) A cutting plane approach to capacitated lot-sizing with start-up costs. Math. Program. 75(3):353–376.Crossref, Google Scholar
• Cook W, Dash S, Fukasawa R, Goycoolea M (2009) Numerically safe Gomory mixed-integer cuts. INFORMS J. Comput. 21(4):641–649.Link, Google Scholar
• Curtis AR, Reid JK (1972) On the automatic scaling of matrices for Gaussian elimination. IMA J. Appl. Math. 10(1):118–124.Crossref, Google Scholar
• Dash S, Günlük O, Lodi A (2010) MIR closures of polyhedral sets. Math. Program. 121(1):33–60.Crossref, 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
• Doostmohammadi M, Fragkos I, Akartunalı K (2016) A polyhedral study of and a branch-and-cut framework for two-period relaxations of big-bucket lot-sizing problems with setup times. Working paper, University of Strathclyde Business School, Glasgow.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
• Federgruen A, Tzur M (1991) A simple forward algorithm to solve general dynamic lot sizing models with n periods in 0(n log n) or 0(n) time. Management Sci. 37(8):909–925.Link, Google Scholar
• Federgruen A, Meissner J, Tzur M (2007) Progressive interval heuristics for multi-item capacitated lot-sizing problems. Oper. Res. 55(3):490–502.Link, Google Scholar
• Fischetti M, Lodi A (2005) Optimizing over the first Chvátal closure. Integer Programming and Combinatorial Optimization (IPCO) XI, Lecture Notes in Computer Science, Vol. 3509 (Springer, Berlin), 12–22.Crossref, Google Scholar
• Florian M, Klein M (1971) Deterministic production planning with concave costs and capacity constraints. Management Sci. 18(1):12–20.Link, Google Scholar
• Florian M, Lenstra JK, Rinnooy Kan AHG (1980) Deterministic production planning: Algorithms and complexity. Management Sci. 26(7):669–679.Link, Google Scholar
• Fragkos I, Akartunalı K (2014) A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems. 5th Internat. Workshop Lot Sizing, Porto, Portugal, 41–45.Google Scholar
• Fukasawa R, Goycoolea M (2011) On the exact separation of mixed integer knapsack cuts. Math. Program. 128(1):19–41.Crossref, Google Scholar
• Fukuda K (2014) cdd and cddplus. Accessed October 19, 2015, http://www.inf.ethz.ch/personal/fukudak/cdd_home/.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
• Krarup J, Bilde O (1977) Plant location, set covering and economic lotsizes: An O(mn) algorithm for structured problems. Collatz Let al., eds. Optimierung bei Graphentheoretischen und Ganzzahligen Probleme (Birkhauser Verlag, Basel, Switzerland), 155–180.Crossref, Google Scholar
• Letchford AN (2001) On disjunctive cuts for combinatorial optimization. J. Comb. Optim. 5(3):299–315.Crossref, Google Scholar
• Levi R, Lodi A, Sviridenko M (2008) Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities. Math. Oper. Res. 33(2):461–474.Link, Google Scholar
• Mangasarian O (1994) Nonlinear Programming (SIAM Classics in Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Manne AS (1957) Programming of economic lot sizes. Cowles Foundation Discussion Papers 23, Cowles Foundation for Research in Economics, Yale University, New Haven, CT.Google Scholar
• Miller AJ, Nemhauser GL, Savelsbergh MWP (2000) Solving the multi-item capacitated lot-sizing problem with setup times by branch-and-cut. Technical Report CORE DP 2000/39, Université Catholique de Louvain, Louvain-la-Neuve, France.Google Scholar
• Miller AJ, Nemhauser GL, Savelsbergh MWP (2003) On the polyhedral structure of a multi-item production planning model with setup times. Math. Program. 94(2):375–405.Crossref, Google Scholar
• Pimentel CMO, Alvelos FP, Valério de Carvalho JM (2010) Comparing Dantzig–Wolfe decompositions and branch-and-price algorithms for the multi-item capacitated lot sizing problem. Optim. Method. Softw. 25(2):299–319.Crossref, Google Scholar
• Pochet Y, Van Vyve M (2004) A general heuristic for production planning problems. INFORMS J. Comput. 16(3):316–327.Link, Google Scholar
• Pochet Y, Wolsey LA (1988) Lot-size models with backlogging: Strong reformulations and cutting planes. Math. Program. 40(1):317–335.Crossref, Google Scholar
• Pochet Y, Wolsey LA (1991) Solving multi-item lot-sizing problems using strong cutting planes. Management Sci. 37(1):53–67.Link, Google Scholar
• Pochet Y, Wolsey LA (1994) Polyhedra for lot-sizing with Wagner-Whitin costs. Math. Program. 67(1):297–323.Crossref, Google Scholar
• Pochet Y, Wolsey LA (2006) Production Planning by Mixed Integer Programming (Springer, New York).Google Scholar
• Ralphs TK, Kopman L, Pulleyblank WR, Trotter LE (2003) On the capacitated vehicle routing problem. Math. Program. 94(2):343–359.Crossref, Google Scholar
• Rardin RL, Wolsey LA (1993) Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems. Eur. J. Oper. Res. 71(1):95–109.Crossref, Google Scholar
• Stadtler H (2003) Multilevel lot sizing with setup times and multiple constrained resources: Internally rolling schedules with lot-sizing windows. Oper. Res. 51(3):487–502.Link, 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
• Van Vyve M, Wolsey L (2006) Approximate extended formulations. Math. Program. 105(2):501–522.Crossref, Google Scholar
• Van Vyve M, Wolsey LA, Yaman H (2014) Relaxations for two-level multi-item lot-sizing problems. Math. Program. 146(1):495–523.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
• Zangwill WI (1969) A backlogging model and a multi-echelon model of a dynamic economic lot size production system—A network approach. Management Sci. 15(9):506–527.Link, Google Scholar
• Zhang M, Küçükyavuz S, Yaman H (2012) A polyhedral study of multiechelon lot sizing with intermediate demands. Oper. Res. 60(4):918–935.Link, Google Scholar