IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v54y2008i4p763-776.html
   My bibliography  Save this article

A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem

Author

Listed:
  • Retsef Levi

    (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Robin Roundy

    (School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853)

  • David Shmoys

    (School of Operations Research and Information Engineering and Department of Computer Science, Cornell University, Ithaca, New York 14853)

  • Maxim Sviridenko

    (IBM T. J. Watson Research Center, Yorktown Heights, New York 10598)

Abstract

Deterministic inventory theory provides streamlined optimization models that attempt to capture trade-offs in managing the flow of goods through a supply chain. We will consider two well-studied deterministic inventory models, called the one-warehouse multiretailer (OWMR) problem and its special case the joint replenishment problem (JRP), and give approximation algorithms with worst-case performance guarantees. That is, for each instance of the problem, our algorithm produces a solution with cost that is guaranteed to be at most 1.8 times the optimal cost; this is called a 1.8-approximation algorithm. Our results are based on an LP-rounding approach; we provide the first constant approximation algorithm for the OWMR problem and improve the previous results for the JRP.

Suggested Citation

  • Retsef Levi & Robin Roundy & David Shmoys & Maxim Sviridenko, 2008. "A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem," Management Science, INFORMS, vol. 54(4), pages 763-776, April.
    • Handle: RePEc:inm:ormnsc:v:54:y:2008:i:4:p:763-776
    DOI: 10.1287/mnsc.1070.0781
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.1070.0781
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.1070.0781?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. Leroy B. Schwarz, 1973. "A Simple Continuous Review Deterministic One-Warehouse N-Retailer Inventory Problem," Management Science, INFORMS, vol. 19(5), pages 555-566, January.
    2. 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).
    3. 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.
    4. Retsef Levi & Robin O. Roundy & David B. Shmoys, 2006. "Primal-Dual Algorithms for Deterministic Inventory Problems," Mathematics of Operations Research, INFORMS, vol. 31(2), pages 267-284, May.
    5. 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.
    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. Danny Segev, 2014. "An Approximate Dynamic-Programming Approach to the Joint Replenishment Problem," Mathematics of Operations Research, INFORMS, vol. 39(2), pages 432-444, May.
    2. Lehilton L. C. Pedrosa & Maxim Sviridenko, 2018. "Integrated Supply Chain Management via Randomized Rounding," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 124-136, February.
    3. Levi DeValve & Saša Pekeč & Yehua Wei, 2020. "A Primal-Dual Approach to Analyzing ATO Systems," Management Science, INFORMS, vol. 66(11), pages 5389-5407, November.
    4. Sainathuni, Bhanuteja & Parikh, Pratik J. & Zhang, Xinhui & Kong, Nan, 2014. "The warehouse-inventory-transportation problem for supply chains," European Journal of Operational Research, Elsevier, vol. 237(2), pages 690-700.
    5. Wang, Min & Zhao, Lindu & Herty, Michael, 2019. "Joint replenishment and carbon trading in fresh food supply chains," European Journal of Operational Research, Elsevier, vol. 277(2), pages 561-573.
    6. Adam N. Elmachtoub & Retsef Levi, 2016. "Supply Chain Management with Online Customer Selection," Operations Research, INFORMS, vol. 64(2), pages 458-473, April.
    7. Takahashi, Katsuhiko & Aoi, Takahiko & Hirotani, Daisuke & Morikawa, Katsumi, 2011. "Inventory control in a two-echelon dual-channel supply chain with setup of production and delivery," International Journal of Production Economics, Elsevier, vol. 133(1), pages 403-415, September.
    8. Zhengyi Li, 2019. "Optimal Utilization of Ports’ Free-of-Charge Times in One Distribution Center and Multiple Ports Inventory Systems," Complexity, Hindawi, vol. 2019, pages 1-12, February.
    9. Tamar Cohen-Hillel & Liron Yedidsion, 2018. "The Periodic Joint Replenishment Problem Is Strongly 𝒩𝒫-Hard," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1269-1289, November.
    10. Niv Buchbinder & Tracy Kimbrel & Retsef Levi & Konstantin Makarychev & Maxim Sviridenko, 2013. "Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms," Operations Research, INFORMS, vol. 61(4), pages 1014-1029, August.
    11. Marcin Bienkowski & Martin Böhm & Jaroslaw Byrka & Marek Chrobak & Christoph Dürr & Lukáš Folwarczný & Łukasz Jeż & Jiří Sgall & Nguyen Kim Thang & Pavel Veselý, 2020. "Online Algorithms for Multilevel Aggregation," Operations Research, INFORMS, vol. 68(1), pages 214-232, January.
    12. Gautier Stauffer, 2018. "Approximation algorithms for k-echelon extensions of the one warehouse multi-retailer problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 88(3), pages 445-473, December.
    13. Jesus Cunha & Rafael Melo, 2016. "On reformulations for the one-warehouse multi-retailer problem," Annals of Operations Research, Springer, vol. 238(1), pages 99-122, March.
    14. Xuefei Shi & Haiyan Wang, 2022. "Design of the cost allocation rule for joint replenishment to an overseas warehouse with a piecewise linear holding cost rate," Operational Research, Springer, vol. 22(5), pages 4905-4929, November.
    15. Hossein Abouee-Mehrizi & Opher Baron & Oded Berman, 2014. "Exact Analysis of Capacitated Two-Echelon Inventory Systems with Priorities," Manufacturing & Service Operations Management, INFORMS, vol. 16(4), pages 561-577, October.
    16. Dinçer Konur & Joseph Geunes, 2019. "Integrated districting, fleet composition, and inventory planning for a multi-retailer distribution system," Annals of Operations Research, Springer, vol. 273(1), pages 527-559, February.
    17. Péter Györgyi & Tamás Kis & Tímea Tamási & József Békési, 2023. "Joint replenishment meets scheduling," Journal of Scheduling, Springer, vol. 26(1), pages 77-94, February.
    18. Gayon, J.-P. & Massonnet, G. & Rapine, C. & Stauffer, G., 2016. "Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales," European Journal of Operational Research, Elsevier, vol. 250(1), pages 155-163.
    19. Jesus O. Cunha & Rafael A. Melo, 2016. "On reformulations for the one-warehouse multi-retailer problem," Annals of Operations Research, Springer, vol. 238(1), pages 99-122, March.
    20. Adeinat, Hamza & Pazhani, Subramanian & Mendoza, Abraham & Ventura, Jose A., 2022. "Coordination of pricing and inventory replenishment decisions in a supply chain with multiple geographically dispersed retailers," International Journal of Production Economics, Elsevier, vol. 248(C).
    21. Oğuz Solyalı & Haldun Süral, 2012. "The one-warehouse multi-retailer problem: reformulation, classification, and computational results," Annals of Operations Research, Springer, vol. 196(1), pages 517-541, July.
    22. Jean-Philippe Gayon & Guillaume Massonnet & Christophe Rapine & Gautier Stauffer, 2017. "Fast Approximation Algorithms for the One-Warehouse Multi-Retailer Problem Under General Cost Structures and Capacity Constraints," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 854-875, August.
    23. Retsef Levi & Cong Shi, 2013. "Approximation Algorithms for the Stochastic Lot-Sizing Problem with Order Lead Times," Operations Research, INFORMS, vol. 61(3), pages 593-602, June.
    24. Carvajal, Jimmy & Castaño, Fabian & Sarache, William & Costa, Yasel, 2020. "Heuristic approaches for a two-echelon constrained joint replenishment and delivery problem," International Journal of Production Economics, Elsevier, vol. 220(C).

    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. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    2. Hark-Chin Hwang, 2010. "Economic Lot-Sizing for Integrated Production and Transportation," Operations Research, INFORMS, vol. 58(2), pages 428-444, April.
    3. 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.
    4. Hark-Chin Hwang, 2009. "Inventory Replenishment and Inbound Shipment Scheduling Under a Minimum Replenishment Policy," Transportation Science, INFORMS, vol. 43(2), pages 244-264, May.
    5. 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.
    6. Alper Atamtürk & Dorit S. Hochbaum, 2001. "Capacity Acquisition, Subcontracting, and Lot Sizing," Management Science, INFORMS, vol. 47(8), pages 1081-1100, August.
    7. 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.
    8. Retsef Levi & Andrea Lodi & Maxim Sviridenko, 2008. "Approximation Algorithms for the Capacitated Multi-Item Lot-Sizing Problem via Flow-Cover Inequalities," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 461-474, May.
    9. Jean-Philippe Gayon & Guillaume Massonnet & Christophe Rapine & Gautier Stauffer, 2017. "Fast Approximation Algorithms for the One-Warehouse Multi-Retailer Problem Under General Cost Structures and Capacity Constraints," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 854-875, August.
    10. 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.
    11. 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.
    12. 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.
    13. VAN VYVE, Mathieu & WOLSEY, Laurence & YAMAN, Hande, 2012. "Relaxations for two-level multi-item lot-sizing problem," LIDAM Discussion Papers CORE 2012031, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. Mathieu Van Vyve, 2007. "Algorithms for Single-Item Lot-Sizing Problems with Constant Batch Size," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 594-613, August.
    15. Hwang, Hark-Chin & Kang, Jangha, 2016. "Two-phase algorithm for the lot-sizing problem with backlogging for stepwise transportation cost without speculative motives," Omega, Elsevier, vol. 59(PB), pages 238-250.
    16. François Vanderbeck, 1998. "Lot-Sizing with Start-Up Times," Management Science, INFORMS, vol. 44(10), pages 1409-1425, October.
    17. Archibald, Thomas W. & Bokkers, Menno B. & Dekker, Rommert & Vliet, Andre van, 1999. "Minimising bins in transmission systems," European Journal of Operational Research, Elsevier, vol. 115(2), pages 380-391, June.
    18. 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.
    19. 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.
    20. van Hoesel, C.P.M. & Wagelmans, A., 1997. "Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems," Research Memorandum 029, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).

    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:ormnsc:v:54:y:2008:i:4:p:763-776. 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.