IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v53y2005i4p711-730.html
   My bibliography  Save this article

Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation

Author

Listed:
  • Alper Atamtürk

    (Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720–1777)

  • Simge Küçükyavuz

    (Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720–1777)

Abstract

We investigate the polyhedral structure of the lot-sizing problem with inventory bounds. We consider two models, one with linear cost on inventory, the other with linear and fixed costs on inventory. For both models, we identify facet-defining inequalities that make use of the inventory bounds explicitly and give exact separation algorithms. We also describe a linear programming formulation of the problem when the order and inventory costs satisfy the Wagner-Whitin nonspeculative property. We present computational experiments that show the effectiveness of the results in tightening the linear programming relaxations of the lot-sizing problem with inventory bounds and fixed costs.

Suggested Citation

  • Alper Atamtürk & Simge Küçükyavuz, 2005. "Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation," Operations Research, INFORMS, vol. 53(4), pages 711-730, August.
    • Handle: RePEc:inm:oropre:v:53:y:2005:i:4:p:711-730
    DOI: 10.1287/opre.1050.0223
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1050.0223
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1050.0223?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. POCHET, Yves & WOLSEY, Laurence A., 1988. "Lot-size models with backlogging: strong reformulations and cutting planes," LIDAM Reprints CORE 791, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Albert Wagelmans & Stan van Hoesel & Antoon Kolen, 1992. "Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case," Operations Research, INFORMS, vol. 40(1-supplem), pages 145-156, February.
    3. BELVAUX, Gaetan & WOLSEY, Laurence A., 2001. "Modelling practical lot-sizing problems as mixed-integer programs," LIDAM Reprints CORE 1516, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. WOLSEY, Laurence A., 2002. "Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation," LIDAM Reprints CORE 1605, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. ORTEGA, Francisco & WOLSEY, Laurence, 2000. "A branch-and-cut algorithm for the single commodity uncapacitated fixed charge network flow problem," LIDAM Discussion Papers CORE 2000049, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. WOLSEY, Laurence A., 1989. "Submodularity and valid inequalities in capacitated fixed charge networks," LIDAM Reprints CORE 842, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. BARANY, Imre & VAN ROY, Tony & WOLSEY, Laurence A., 1984. "Uncapacitated lot-sizing: the convex hull of solutions," LIDAM Reprints CORE 605, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Miguel Constantino, 1998. "Lower Bounds in Lot-Sizing Models: A Polyhedral Study," Mathematics of Operations Research, INFORMS, vol. 23(1), pages 101-118, February.
    9. BELVAUX, Gaëtan & WOLSEY, Laurence A., 2000. "bc-prod: A specialized branch-and-cut system for lot-sizing problems," LIDAM Reprints CORE 1455, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. WOLSEY, Laurence, 2002. "Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation," LIDAM Discussion Papers CORE 2002012, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Stephen F. Love, 1973. "Bounded Production and Inventory Models with Piecewise Concave Costs," Management Science, INFORMS, vol. 20(3), pages 313-318, November.
    12. Aghezzaf, E.H. & Wolsey, L.A., 1994. "Modelling piecewise linear concave costs in a tree partitioning problem," LIDAM Reprints CORE 1088, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. Yves Pochet & Laurence A. Wolsey, 1991. "Solving Multi-Item Lot-Sizing Problems Using Strong Cutting Planes," Management Science, INFORMS, vol. 37(1), pages 53-67, January.
    14. LOPARIC, Marko & POCHET, Yves & WOLSEY, Laurence A., 2001. "The uncapacitated lot-sizing problem with sales and safety stocks," LIDAM Reprints CORE 1498, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. VAN ROY, Tony J. & WOLSEY, Laurence A., 1985. "Valid inequalities and separation for uncapacitated fixed charge networks," LIDAM Reprints CORE 671, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
    17. Miller, Andrew J. & Nemhauser, George L. & Savelsbergh, Martin W. P., 2000. "On the capacitated lot-sizing and continuous 0-1 knapsack polyhedra," European Journal of Operational Research, Elsevier, vol. 125(2), pages 298-315, September.
    18. POCHET, Yves & WOLSEY, Laurence A., 1993. "Lot-sizing with constant batches: formulation and valid inequalities," LIDAM Reprints CORE 1066, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    19. Laurence A. Wolsey, 2002. "Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation," Management Science, INFORMS, vol. 48(12), pages 1587-1602, December.
    20. Pochet, Y. & Wolsey, L. A., 1994. "Polyhedra for lot-sizing with Wagner-Whitin costs," LIDAM Reprints CORE 1129, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    21. ORTEGA , Francisco & WOLSEY, Laurence A., 2003. "A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem," LIDAM Reprints CORE 1611, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    22. Gaetan Belvaux & Laurence A. Wolsey, 2001. "Modelling Practical Lot-Sizing Problems as Mixed-Integer Programs," Management Science, INFORMS, vol. 47(7), pages 993-1007, July.
    23. LOPARIC, Marko & MARCHAND, Hugues & WOLSEY, Laurence A., 2003. "Dynamic knapsack sets and capacitated lot-sizing," LIDAM Reprints CORE 1600, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    24. Gaetan Belvaux & Laurence A. Wolsey, 2000. "bc --- prod: A Specialized Branch-and-Cut System for Lot-Sizing Problems," Management Science, INFORMS, vol. 46(5), pages 724-738, May.
    25. Awi Federgruen & Michal Tzur, 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 Science, INFORMS, vol. 37(8), pages 909-925, August.
    26. Alok Aggarwal & James K. Park, 1993. "Improved Algorithms for Economic Lot Size Problems," Operations Research, INFORMS, vol. 41(3), pages 549-571, June.
    27. M. W. Padberg & T. J. Van Roy & L. A. Wolsey, 1985. "Valid Linear Inequalities for Fixed Charge Problems," Operations Research, INFORMS, vol. 33(4), pages 842-861, August.
    28. VAN VYVE, Mathieu & ORTEGA, Francisco, 2003. "Lot-sizing with fixed charges on stocks: the convex hull," LIDAM Discussion Papers CORE 2003014, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    29. Alper Atamtürk & Dorit S. Hochbaum, 2001. "Capacity Acquisition, Subcontracting, and Lot Sizing," Management Science, INFORMS, vol. 47(8), pages 1081-1100, August.
    30. Yves Pochet & Laurence A. Wolsey, 1993. "Lot-Sizing with Constant Batches: Formulation and Valid Inequalities," Mathematics of Operations Research, INFORMS, vol. 18(4), pages 767-785, November.
    31. Padberg, M.W. & Van Roy, T.J. & Wolsey, L.A., 1985. "Valid linear inequalities for fixed charge problems," LIDAM Reprints CORE 656, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ayse Akbalik & Bernard Penz & Christophe Rapine, 2015. "Capacitated lot sizing problems with inventory bounds," Annals of Operations Research, Springer, vol. 229(1), pages 1-18, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    2. Laurence A. Wolsey, 2002. "Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation," Management Science, INFORMS, vol. 48(12), pages 1587-1602, December.
    3. AkartunalI, Kerem & Miller, Andrew J., 2009. "A heuristic approach for big bucket multi-level production planning problems," European Journal of Operational Research, Elsevier, vol. 193(2), pages 396-411, March.
    4. Kerem Akartunalı & Andrew Miller, 2012. "A computational analysis of lower bounds for big bucket production planning problems," Computational Optimization and Applications, Springer, vol. 53(3), pages 729-753, December.
    5. Minjiao Zhang & Simge Küçükyavuz & Hande Yaman, 2012. "A Polyhedral Study of Multiechelon Lot Sizing with Intermediate Demands," Operations Research, INFORMS, vol. 60(4), pages 918-935, August.
    6. Absi, Nabil & Kedad-Sidhoum, Safia, 2008. "The multi-item capacitated lot-sizing problem with setup times and shortage costs," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1351-1374, March.
    7. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.
    8. Atamturk, Alper & Munoz, Juan Carlos, 2002. "A Study of the Lot-Sizing Polytope," University of California Transportation Center, Working Papers qt6zz2g0z4, University of California Transportation Center.
    9. Kerem Akartunalı & Ioannis Fragkos & Andrew J. Miller & Tao Wu, 2016. "Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 766-780, November.
    10. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    11. Yongpei Guan & Andrew J. Miller, 2008. "Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 56(5), pages 1172-1183, October.
    12. Atamturk, Alper & Munoz, Juan Carlos, 2002. "A Study of the Lot-Sizing Polytope," University of California Transportation Center, Working Papers qt9gx170tx, University of California Transportation Center.
    13. Awi Federgruen & Joern Meissner & Michal Tzur, 2007. "Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 55(3), pages 490-502, June.
    14. Francesco Gaglioppa & Lisa A. Miller & Saif Benjaafar, 2008. "Multitask and Multistage Production Planning and Scheduling for Process Industries," Operations Research, INFORMS, vol. 56(4), pages 1010-1025, August.
    15. Hark-Chin Hwang, 2010. "Economic Lot-Sizing for Integrated Production and Transportation," Operations Research, INFORMS, vol. 58(2), pages 428-444, April.
    16. Toledo, Franklina Maria Bragion & Armentano, Vinicius Amaral, 2006. "A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines," European Journal of Operational Research, Elsevier, vol. 175(2), pages 1070-1083, December.
    17. Brian T. Denton & John Forrest & R. John Milne, 2006. "IBM Solves a Mixed-Integer Program to Optimize Its Semiconductor Supply Chain," Interfaces, INFORMS, vol. 36(5), pages 386-399, October.
    18. Wolsey, Laurence A., 1995. "Progress with single-item lot-sizing," European Journal of Operational Research, Elsevier, vol. 86(3), pages 395-401, November.
    19. Wei, Mingyuan & Qi, Mingyao & Wu, Tao & Zhang, Canrong, 2019. "Distance and matching-induced search algorithm for the multi-level lot-sizing problem with substitutable bill of materials," European Journal of Operational Research, Elsevier, vol. 277(2), pages 521-541.
    20. Chung-Lun Li & Qingying Li, 2016. "Polynomial-Time Solvability of Dynamic Lot Size Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-20, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:53:y:2005:i:4:p:711-730. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.