A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot-Sizing Problem with Setup Times

References

• Barany I., Van Roy T. J., Wolsey L. A. Strong formulations for multi-item capacitated lot sizing. Management Sci. (1984) 30(10):1255–1261Link, Google Scholar
• Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P., Vance P. H. Branch-and-price: Column generation for solving huge integer programs. Oper. Res. (1998) 46(3):316–329Link, Google Scholar
• Belvaux G., Wolsey L. A. BC-PROD: A specialized branch-and-cut system for lot-sizing problems. Management Sci. (2000) 46(5):724–738Link, Google Scholar
• Belvaux G., Wolsey L. A. Modelling practical lot-sizing problems as mixed integer programs. Management Sci. (2001) 47(7):993–1007Link, Google Scholar
• Bitran G. R., Matsuo H. The multi-item capacitated lot size problem: Error bounds of Manne's formulations. Management Sci. (1986) 32(3):350–359Link, Google Scholar
• Cattrysse D., Maes J., Van Wassenhove L. N. Set partitioning and column generation heuristics for capacitated dynamic lotsizing. Eur. J. Oper. Res. (1990) 46:38–47Crossref, Google Scholar
• Dantzig G. B., Wolfe P. Decomposition principle for linear programs. Oper. Res. (1960) 8:101–111Link, Google Scholar
• Degraeve Z., Jans R. A new Dantzig-Wolfe reformulation and branch-and-price algorithm for the capacitated lot sizing problem with set up times. (2003) ERIM Report Series ERS-2003-010-LIS, Erasmus University, Rotterdam, The NetherlandsGoogle Scholar
• Degraeve Z., Peeters M. Optimal integer solutions to industrial cutting stock problems: Part 2, Benchmark results. INFORMS J. Comput. (2003) 15(1):58–81Link, Google Scholar
• Dzielinski B. P., Gomory R. E. Optimal programming of lot sizes, inventory, and labor allocations. Management Sci. (1965) 11(9):874–890Link, Google Scholar
• Eppen G. D., Martin R. K. Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper. Res. (1987) 35(6):832–848Link, Google Scholar
• Florian M., Klein M. Deterministic production planning with concave costs and capacity constraints. Management Sci. (1971) 18(1):12–20Link, Google Scholar
• Geoffrion A. M. Lagrangean relaxation for integer programming. Math. Programming Stud. (1974) 2:82–113Crossref, Google Scholar
• Gopalakrishnan M., Ding K., Bourjolly J.-M., Mohan S. A tabu-search heuristic for the capacitated lot-sizing problem with set-up carryover. Management Sci. (2001) 47(6):851–863Link, Google Scholar
• Huisman D., Jans R., Peeters M., Wagelmans A. P. M., Desaulniers G., Desrosiers J., Solomon M. Combining column generation and Lagrangian relexation. Column Generation (2005) (Springer, New York) 247–270Crossref, Google Scholar
• Jans R., Degraeve Z. Improved lower bounds for the capacitated lot sizing problem with setup times. Oper. Res. Lett. (2004) 32:185–195Crossref, Google Scholar
• Jans R., Degraeve Z. Meta-heuristics for dynamic lot-sizing: A review and comparison of solution approaches. Eur. J. Oper. Res. (2007) 177(3):1855–1875Crossref, Google Scholar
• Kleindorfer P. R., Newson E. F. P. A lower bounding structure for lot-size scheduling problems. Oper. Res. (1975) 23(2):299–311Link, Google Scholar
• Lambrecht M., Vanderveken H. Heuristic procedures for the single operation, multi-item loading problem. AIIE Trans. (1979) 11(4):319–326Crossref, Google Scholar
• Lasdon L.Optimization Theory for Large Systems (1970) (Macmillan Company, New York) Google Scholar
• Leung J. M. Y., Magnanti T. L., Vachani R. Facets and algorithms for capacitated lot sizing. Math. Programming (1989) 45:331–359Crossref, Google Scholar
• Manne A. S. Programming of economic lot sizes. Management Sci. (1958) 4(2):115–135Link, Google Scholar
• Martin K. Generating alternative mixed-integer programming models using variable redefinition. Oper. Res. (1987) 35(6):820–831Link, Google Scholar
• Miller A. J., Nemhauser G. L., Savelsbergh M. W. P. On the capacitated lot-sizing and continuous 0-1 knapsack polyhedra. Eur. J. Oper. Res. (2000) 125:298–315Crossref, Google Scholar
• Nemhauser G. L., Wolsey L. A.Integer and Combinatorial Optimization (1988) (John Wiley & Sons, New York) Crossref, Google Scholar
• Pochet Y. Valid inequalities and separation for capacitated economic lot sizing. Oper. Res. Lett. (1988) 7(3):109–115Crossref, Google Scholar
• Schrage L.LINDO: Optimization Software for Linear Programming (1995) (Lindo Systems Inc., Chicago, IL) Google Scholar
• Thizy J. M., Van Wassenhove L. N. Lagrangean relaxation for the multi-item capacitated lot-sizing problem: A heuristic implementation. IIE Trans. (1985) 17(4):308–313Crossref, Google Scholar
• Trigeiro W., Thomas L. J., McClain J. O. Capacitated lot sizing with set-up times. Management Sci. (1989) 35(3):353–366Link, Google Scholar
• Vanderbeck F. Lot-sizing with start-up times. Management Sci. (1998) 44(10):1409–1425Link, Google Scholar
• Vanderbeck F. On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. (2000) 48(1):111–128Link, Google Scholar
• Vanderbeck F., Savelsbergh M. W. P. A generic view of Dantzig-Wolfe decomposition in mixed integer programming. Oper. Res. Lett. (2006) 34:296–306Crossref, Google Scholar
• Wagner H. M., Whitin T. M. Dynamic version of the economic lot size model. Management Sci. (1958) 5(1):89–96Link, Google Scholar