×

Local cuts and two-period convex hull closures for big-bucket lot-sizing problems. (English) Zbl 1355.90075

Summary: Despite the significant attention they have drawn, big-bucket lot-sizing problems remain notoriously difficult to solve. Previous literature contained results (computational and theoretical) indicating that what makes these problems difficult are the embedded single-machine, single-level, multiperiod submodels. We therefore consider the simplest such submodel, a multi-item, two-period capacitated relaxation. We propose a methodology that can approximate the convex hulls of all such possible relaxations by generating violated valid inequalities. To generate such inequalities, we separate two-period projections of fractional linear programming solutions from the convex hulls of the two-period closure we study. The convex hull representation of the two-period closure is generated dynamically using column generation. Contrary to regular column generation, our method is an outer approximation and can therefore be used efficiently in a regular branch-and-bound procedure. We present computational results that illustrate how these two-period models could be effective in solving complicated problems.

MSC:

90C27 Combinatorial optimization
90C10 Integer programming

Software:

cdd
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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.
[2] 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 · Zbl 1160.90358
[3] 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 · Zbl 1264.90125
[4] Andersen K, Cornuéjols G, Li Y (2005) Split closure and intersection cuts. Math. Program. 102(3):457-493. CrossRef · Zbl 1066.90070
[5] Anily S, Tzur M, Wolsey LA (2009) Multi-item lot-sizing with joint set-up costs. Math. Program. 119(1):79-94. CrossRef · Zbl 1170.90005
[6] 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. · Zbl 1106.90369
[7] Applegate DL, Cook W, Dash S, Espinoza DG (2007) Exact solutions to linear programming problems. Oper. Res. Lett. 35(6):693-699. CrossRef · Zbl 1177.90282
[8] Atamtürk A, Muñoz JC (2004) A study of the lot-sizing polytope. Math. Program. 99(3):443-465. CrossRef · Zbl 1073.90067
[9] Balas E, Margot F (2013) Generalized intersection cuts and a new cut generating paradigm. Math. Program. 137(1):19-35. CrossRef · Zbl 1262.90099
[10] Balas E, Saxena A (2008) Optimizing over the split closure. Math. Program. 113(2):219-240. CrossRef · Zbl 1135.90030
[11] Barany I, Van Roy TJ, Wolsey LA (1984) Strong formulations for multi-item capacitated lot-sizing. Management Sci. 30(10):1255-1261. Link · Zbl 0601.90037
[12] Belvaux G, Wolsey LA (2000) bc–prod: A specialized branch-and-cut system for lot-sizing problems. Management Sci. 46(5):724-738. Link · Zbl 1231.90384
[13] Belvaux G, Wolsey LA (2001) Modelling practical lot-sizing problems as mixed-integer programs. Management Sci. 47(7):993-1007. Link · Zbl 1232.90169
[14] 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 · Zbl 1307.90114
[15] Billington PJ, McClain JO, Thomas LJ (1986) Heuristics for multilevel lot-sizing with a bottleneck. Management Sci. 32(8): 989-1006. Link · Zbl 0596.90038
[16] 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 · Zbl 0596.90043
[17] Boyd EA (1994) Fenchel cutting planes for integer programs. Oper. Res. 42(1):53-64. Link · Zbl 0809.90104
[18] Cadoux F (2010) Computing deep facet-defining disjunctive cuts for mixed-integer programming. Math. Program. 122(2):197-223. CrossRef · Zbl 1184.90105
[19] Chvátal V, Cook W, Espinoza D (2013) Local cuts for mixed integer programming. Math. Program. Comput. 5(2):171-200. CrossRef · Zbl 1275.90043
[20] Constantino M (1996) A cutting plane approach to capacitated lot-sizing with start-up costs. Math. Program. 75(3):353-376. CrossRef · Zbl 0874.90098
[21] Cook W, Dash S, Fukasawa R, Goycoolea M (2009) Numerically safe Gomory mixed-integer cuts. INFORMS J. Comput. 21(4):641-649. Link · Zbl 1243.90135
[22] Curtis AR, Reid JK (1972) On the automatic scaling of matrices for Gaussian elimination. IMA J. Appl. Math. 10(1):118-124. CrossRef · Zbl 0249.65026
[23] Dash S, Günlük O, Lodi A (2010) MIR closures of polyhedral sets. Math. Program. 121(1):33-60. CrossRef · Zbl 1184.90107
[24] 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 · Zbl 1328.90088
[25] 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 · Zbl 1167.90321
[26] 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.
[27] Eppen GD, Martin RK (1987) Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper. Res. 35(6): 832-848. Link · Zbl 0639.90046
[28] 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 · Zbl 0748.90011
[29] Federgruen A, Meissner J, Tzur M (2007) Progressive interval heuristics for multi-item capacitated lot-sizing problems. Oper. Res. 55(3):490-502. Link · Zbl 1167.90322
[30] 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 · Zbl 1119.90329
[31] Florian M, Klein M (1971) Deterministic production planning with concave costs and capacity constraints. Management Sci. 18(1):12-20. Link · Zbl 0273.90023
[32] Florian M, Lenstra JK, Rinnooy Kan AHG (1980) Deterministic production planning: Algorithms and complexity. Management Sci. 26(7):669-679. Link · Zbl 0445.90025
[33] 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.
[34] Fukasawa R, Goycoolea M (2011) On the exact separation of mixed integer knapsack cuts. Math. Program. 128(1):19-41. CrossRef · Zbl 1218.90126
[35] Fukuda K (2014) cdd and cddplus. Accessed October 19, 2015, http://www.inf.ethz.ch/personal/fukudak/cdd_home/.
[36] 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 · Zbl 1137.90584
[37] Krarup J, Bilde O (1977) Plant location, set covering and economic lotsizes: An O(mn) algorithm for structured problems. Collatz L, eds. Optimierung bei Graphentheoretischen und Ganzzahligen Probleme (Birkhauser Verlag, Basel, Switzerland), 155-180. CrossRef · Zbl 0364.90067
[38] Letchford AN (2001) On disjunctive cuts for combinatorial optimization. J. Comb. Optim. 5(3):299-315. CrossRef · Zbl 1078.90039
[39] 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 · Zbl 1231.90046
[40] Mangasarian O (1994) Nonlinear Programming (SIAM Classics in Applied Mathematics, Philadelphia). CrossRef
[41] Manne AS (1957) Programming of economic lot sizes. Cowles Foundation Discussion Papers 23, Cowles Foundation for Research in Economics, Yale University, New Haven, CT.
[42] 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.
[43] 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 · Zbl 1030.90022
[44] 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 · Zbl 1189.90103
[45] Pochet Y, Van Vyve M (2004) A general heuristic for production planning problems. INFORMS J. Comput. 16(3):316-327. Link · Zbl 1239.90043
[46] Pochet Y, Wolsey LA (1988) Lot-size models with backlogging: Strong reformulations and cutting planes. Math. Program. 40(1):317-335. CrossRef · Zbl 0663.90038
[47] Pochet Y, Wolsey LA (1991) Solving multi-item lot-sizing problems using strong cutting planes. Management Sci. 37(1):53-67. Link · Zbl 0727.90034
[48] Pochet Y, Wolsey LA (1994) Polyhedra for lot-sizing with Wagner-Whitin costs. Math. Program. 67(1):297-323. CrossRef · Zbl 0822.90049
[49] Pochet Y, Wolsey LA (2006) Production Planning by Mixed Integer Programming (Springer, New York).
[50] Ralphs TK, Kopman L, Pulleyblank WR, Trotter LE (2003) On the capacitated vehicle routing problem. Math. Program. 94(2):343-359. CrossRef · Zbl 1030.90131
[51] 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 · Zbl 0807.90051
[52] 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 · Zbl 1163.90474
[53] 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 · Zbl 1179.90023
[54] Trigeiro WW, Thomas LJ, McClain JO (1989) Capacitated lot sizing with setup times. Management Sci. 35(3):353-366. Link
[55] Van Vyve M, Wolsey L (2006) Approximate extended formulations. Math. Program. 105(2):501-522. CrossRef · Zbl 1085.90051
[56] Van Vyve M, Wolsey LA, Yaman H (2014) Relaxations for two-level multi-item lot-sizing problems. Math. Program. 146(1):495-523. CrossRef · Zbl 1319.90058
[57] Wagner HM, Whitin TM (1958) Dynamic version of the economic lot size model. Management Sci. 5(1):89-96. Link · Zbl 0977.90500
[58] 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 · Zbl 0172.44603
[59] 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 · Zbl 1260.90031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.