Approximation Algorithms for the Capacitated Multi-Item Lot-Sizing Problem via Flow-Cover Inequalities

References

• Aardal K. Capacitated facility location: Separation algorithms and computational experience. Math. Programming (1998) 81:149–175Crossref, Google Scholar
• Aardal K., Pochet Y., Wolsey L. A. Capacitated facility location: Valid inequalities and facets. Math. Oper. Res. (1995) 20:562–582Link, Google Scholar
• Anily S., Tzur M. Shipping multiple-items by capacitated vehicles—An optimal dynamic programming approach. Transportation Sci. (2005) 39:233–248Link, Google Scholar
• Anily S., Tzur M., Wolsey L. A. Multi-item lot-sizing with joint set-up cost. Math. Programming (2005) . ForthcomingGoogle Scholar
• Atamtürk A., Rajan D. On splittable and unsplittable flow capacity network design arc-set polyhedra. Math. Programming (2002) 92:315–333Crossref, Google Scholar
• Bitran G. R., Yanasee H. H. Computational complexity of the capacitated lot-size problem. Management Sci. (1982) 28:1174–1186Link, Google Scholar
• Carnes T., Shmoys D. B. A primal-dual 2-approximation algorithm the single-demand fixed-charge minimum-cost flow problem. (2006) . Working paperGoogle Scholar
• Carnes T., Shmoys D., Lodi A., Panconesi A., Rinaldi G. A primal-dual schema for capacitated covering problems. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science (2008) 5035(Springer, Berlin) 288–302Crossref, Google Scholar
• Carr R. D., Fleischer L. K., Leung V. J., Phillips C. A. Strengthening integrality gaps for capacitated network design and covering problems. Proc. 11th ACM/SIAM Sympos. Discrete Algorithms (SODA) (2000) 106–115Google Scholar
• Even G., Levi R., Rawitz D., Schieber B., Shahar S., Sviridenko M. Algorithms for capacitated rectangle stabbing and lot-sizing with joint set-up costs. Trans. Algorithms (2008) . ForthcomingCrossref, Google Scholar
• Federgruen A., Meissner J. Probabilistic analysis of multi-item capacitated lot sizing problems. (2004) . Working paperGoogle Scholar
• Federgruen A., Meissner J., Tzur M. Progressive interval heuristics for the multi-item capacitated lot sizing problem. Oper. Res. (2007) 55:490–502Link, Google Scholar
• Florian M., Lenstra J. K., Rinooy Kan A. H. G. Deterministic production planning: Algorithms and complexity. Management Sci. (1980) 26:669–679Link, Google Scholar
• Garey M., Johnson D. S.Computers and Intractability. A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Co., San Francisco) Google Scholar
• Leung J., Magnanti T. Valid inequalities and facets of the capacitated plant location problem. Math. Programming (1989) 44:271–291Crossref, Google Scholar
• Levi R., Roundy R. O., Shmoys D. B. Primal-dual algorithms for deterministic inventory problems. Math. Oper. Res. (2006) 31:267–284Link, Google Scholar
• Levi R., Roundy R. O., Shmoys D. B., Sviridenko M. First constant approximation algorithm for the single-warehouse multi-retailer problem. Management Sci. (2008) 54(4):762–776Link, Google Scholar
• Magnanti T. L., Mirchandani P., Vachani R. The convex hull of two core capacitated network design problems. Math. Programming (1993) 60:233–250Crossref, Google Scholar
• Nemhauser G., Wolsey L. A.Integer Programming and Combinatorial Optimization (1988) (Wiley-Interscience, New York) Google Scholar
• Padberg M. W., Roy T. J. V., Wolsey L. A. Valid inequalities for fixed charge problems. Oper. Res. (1985) 33:842–861Link, Google Scholar
• Pochet Y., Wolsey L. A. Lot-sizing with constant batches: Formulation and valid inequalities. Math. Oper. Res. (1993) 18:767–785Link, Google Scholar
• Pochet Y., Wolsey L. A.Production Planning by Mixed Integer Programming (2006) (Springer-Verlag, Berlin) Google Scholar
• van Hoesel C. P. M., Wagelmans A. P. M. Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems. Math. Oper. Res. (2001) 26:339–357Link, Google Scholar