IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v54y2008i4p763-776.html

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. 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.
    3. 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.
    4. 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).
    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)

    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. 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.
    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. 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.
    8. Archetti, Claudia & Bertazzi, Luca & Grazia Speranza, M., 2014. "Polynomial cases of the economic lot sizing problem with cost discounts," European Journal of Operational Research, Elsevier, vol. 237(2), pages 519-527.
    9. 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.
    10. 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.
    11. François Vanderbeck, 1998. "Lot-Sizing with Start-Up Times," Management Science, INFORMS, vol. 44(10), pages 1409-1425, October.
    12. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. 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).
    19. 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.
    20. Sun, Haoying & Vanajakumari, Manoj & Sriskandarajah, Chelliah & Kumar, Subodha, 2024. "Supply chain planning with free trade zone and uncertain demand," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 192(C).

    More about this item

    Keywords

    ;
    ;
    ;

    Statistics

    Access and download statistics

    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.