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

Polymatroid Optimization, Submodularity, and Joint Replenishment Games

Author

Listed:
  • Simai He

    (Department of Management Sciences, City University of Hong Kong, Kowloon Tong, Hong Kong)

  • Jiawei Zhang

    (Department of Information, Operations, and Management Sciences, Stern School of Business, New York University, New York, New York 10012)

  • Shuzhong Zhang

    (Industrial and Systems Engineering Program, University of Minnesota, Minneapolis, Minnesota 55455)

Abstract

In this paper we consider the problem of maximizing a separable concave function over a polymatroid. More specifically, we study the submodularity of its optimal objective value in the parameters of the objective function. This question is interesting in its own right and is encountered in many applications. But our research has been motivated mainly by a cooperative game associated with the well-known joint replenishment model. By applying our general results on polymatroid optimization, we prove that this cooperative game is submodular (i.e., its characteristic cost function is submodular) if the joint setup cost is a normalized and nondecreasing submodular function. Furthermore, the same result holds true for a more general one-warehouse multiple retailer game, which affirmatively answers an open question posed by Anily and Haviv [Anily, S., M. Haviv. 2007. The cost allocation problem for the first order interaction joint replenishment model. Oper. Res. 55 (2) 292--302].

Suggested Citation

  • Simai He & Jiawei Zhang & Shuzhong Zhang, 2012. "Polymatroid Optimization, Submodularity, and Joint Replenishment Games," Operations Research, INFORMS, vol. 60(1), pages 128-137, February.
    • Handle: RePEc:inm:oropre:v:60:y:2012:i:1:p:128-137
    DOI: 10.1287/opre.1110.1000
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1110.1000
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1110.1000?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. Laurence A. Wolsey, 1982. "Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems," Mathematics of Operations Research, INFORMS, vol. 7(3), pages 410-425, August.
    2. Awi Federgruen & Yu-Sheng Zheng, 1992. "The Joint Replenishment Problem with General Joint Cost Structures," Operations Research, INFORMS, vol. 40(2), pages 384-403, April.
    3. Jiawei Zhang, 2009. "Cost Allocation for Joint Replenishment Models," Operations Research, INFORMS, vol. 57(1), pages 146-156, February.
    4. Nagarajan, Mahesh & Sosic, Greys, 2008. "Game-theoretic analysis of cooperation among supply chain agents: Review and extensions," European Journal of Operational Research, Elsevier, vol. 187(3), pages 719-745, June.
    5. A. Federgruen & M. Queyranne & Yu-Sheng Zheng, 1992. "Simple Power-of-Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with General Joint Setup Costs," Mathematics of Operations Research, INFORMS, vol. 17(4), pages 951-963, November.
    6. WOLSEY, Laurence A., 1982. "Maximising real-valued submodular functions: primal and dual heuristics for location problems," LIDAM Reprints CORE 486, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Robin Roundy, 1985. "98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer Systems," Management Science, INFORMS, vol. 31(11), pages 1416-1430, November.
    8. Andreas S. Schulz & Nelson A. Uhan, 2010. "Sharing Supermodular Costs," Operations Research, INFORMS, vol. 58(4-part-2), pages 1051-1056, August.
    9. Shoshana Anily & Moshe Haviv, 2007. "The Cost Allocation Problem for the First Order Interaction Joint Replenishment Model," Operations Research, INFORMS, vol. 55(2), pages 292-302, April.
    10. Jeroen Kuipers & Ulrich Faigle & Walter Kern, 2001. "On the computation of the nucleolus of a cooperative game," International Journal of Game Theory, Springer;Game Theory Society, vol. 30(1), pages 79-98.
    11. R. Garbe & K. D. Glazebrook, 1998. "Submodular Returns and Greedy Heuristics for Queueing Scheduling Problems," Operations Research, INFORMS, vol. 46(3), pages 336-346, June.
    12. Awi Federgruen & Henri Groenevelt, 1986. "The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality," Operations Research, INFORMS, vol. 34(6), pages 909-918, December.
    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. Simai He & Jay Sethuraman & Xuan Wang & Jiawei Zhang, 2017. "A NonCooperative Approach to Cost Allocation in Joint Replenishment," Operations Research, INFORMS, vol. 65(6), pages 1562-1573, December.
    2. Martijn H. H. Schoot Uiterkamp & Marco E. T. Gerards & Johann L. Hurink, 2022. "On a Reduction for a Class of Resource Allocation Problems," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1387-1402, May.
    3. Nguyen, Christine & Dessouky, Maged & Toriello, Alejandro, 2014. "Consolidation strategies for the delivery of perishable products," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 108-121.
    4. Luo, Chunlin & Zhou, Xiaoyang & Lev, Benjamin, 2022. "Core, shapley value, nucleolus and nash bargaining solution: A Survey of recent developments and applications in operations management," Omega, Elsevier, vol. 110(C).
    5. Lindong Liu & Xiangtong Qi & Zhou Xu, 2016. "Computing Near-Optimal Stable Cost Allocations for Cooperative Games by Lagrangian Relaxation," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 687-702, November.
    6. Jingjing Tan & Yicheng Xu & Dongmei Zhang & Xiaoqing Zhang, 2023. "On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice," Journal of Combinatorial Optimization, Springer, vol. 45(2), pages 1-19, March.

    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. Simai He & Jay Sethuraman & Xuan Wang & Jiawei Zhang, 2017. "A NonCooperative Approach to Cost Allocation in Joint Replenishment," Operations Research, INFORMS, vol. 65(6), pages 1562-1573, December.
    2. Fiestras-Janeiro, M.G. & García-Jurado, I. & Meca, A. & Mosquera, M.A., 2011. "Cooperative game theory and inventory management," European Journal of Operational Research, Elsevier, vol. 210(3), pages 459-466, May.
    3. Jiawei Zhang, 2009. "Cost Allocation for Joint Replenishment Models," Operations Research, INFORMS, vol. 57(1), pages 146-156, February.
    4. M Dror & B C Hartman, 2011. "Survey of cooperative inventory games and extensions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 565-580, April.
    5. Padilla Tinoco, Silvia Valeria & Creemers, Stefan & Boute, Robert N., 2017. "Collaborative shipping under different cost-sharing agreements," European Journal of Operational Research, Elsevier, vol. 263(3), pages 827-837.
    6. Xin Chen & Jiawei Zhang, 2009. "A Stochastic Programming Duality Approach to Inventory Centralization Games," Operations Research, INFORMS, vol. 57(4), pages 840-851, August.
    7. 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.
    8. Shoshana Anily & Moshe Haviv, 2007. "The Cost Allocation Problem for the First Order Interaction Joint Replenishment Model," Operations Research, INFORMS, vol. 55(2), pages 292-302, April.
    9. Luyi Gui & Christopher S. Tang & Shuya Yin, 2019. "Improving Microretailer and Consumer Welfare in Developing Economies: Replenishment Strategies and Market Entries," Service Science, INFORMS, vol. 21(1), pages 231-250, January.
    10. Körpeoğlu, Evren & Şen, Alper & Güler, Kemal, 2013. "Non-cooperative joint replenishment under asymmetric information," European Journal of Operational Research, Elsevier, vol. 227(3), pages 434-443.
    11. Xin Chen & Zhisong Chen, 2013. "Cost allocation of capacity investment games," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(6), pages 512-523, September.
    12. Dror, Moshe & Hartman, Bruce C. & Chang, Wei, 2012. "The cost allocation issue in joint replenishment," International Journal of Production Economics, Elsevier, vol. 135(1), pages 242-254.
    13. Julien Bramel & Shobhna Goyal & Paul Zipkin, 2000. "Coordination of Production/Distribution Networks with Unbalanced Leadtimes," Operations Research, INFORMS, vol. 48(4), pages 570-577, August.
    14. Huang, H. C. & Chew, E. P. & Goh, K. H., 2005. "A two-echelon inventory system with transportation capacity constraint," European Journal of Operational Research, Elsevier, vol. 167(1), pages 129-143, November.
    15. Boissiere, J. & Frein, Y. & Rapine, C., 2008. "Optimal stationary policies in a 3-stage serial production-distribution logistic chain facing constant and continuous demand," European Journal of Operational Research, Elsevier, vol. 186(2), pages 608-619, April.
    16. Herer, Yale T., 1999. "Submodularity and the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 114(3), pages 489-508, May.
    17. Suning Gong & Qingqin Nong & Shuyu Bao & Qizhi Fang & Ding-Zhu Du, 2023. "A fast and deterministic algorithm for Knapsack-constrained monotone DR-submodular maximization over an integer lattice," Journal of Global Optimization, Springer, vol. 85(1), pages 15-38, January.
    18. Akiyoshi Shioura, 2015. "Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints," Mathematics of Operations Research, INFORMS, vol. 40(1), pages 192-225, February.
    19. Shoshana Anily & Moshe Haviv, 2010. "Cooperation in Service Systems," Operations Research, INFORMS, vol. 58(3), pages 660-673, June.
    20. LAMAS, ALEJANDRO & CHEVALIER, Philippe, 2013. "Jumping the hurdles for collaboration: fairness in operations pooling in the absence of transfer payments," LIDAM Discussion Papers CORE 2013073, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).

    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:60:y:2012:i:1:p:128-137. 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.