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

Preservation of Supermodularity in Parametric Optimization: Necessary and Sufficient Conditions on Constraint Structures

Author

Listed:
  • Xin Chen

    (Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801)

  • Daniel Zhuoyu Long

    (Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong, Shatin, Hong Kong, China)

  • Jin Qi

    (Department of Industrial Engineering and Decision Analytics, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong, China)

Abstract

This paper presents a systematic study of the preservation of supermodularity under parametric optimization, allowing us to derive complementarity among parameters and monotonic structural properties for optimal policies in many operational models. We introduce the new concepts of mostly sublattice and additive mostly sublattice, which generalize the commonly imposed sublattice condition significantly, and use them to establish the necessary and sufficient conditions for the feasible set so that supermodularity can be preserved under various assumptions about the objective functions. Furthermore, we identify some classes of polyhedral sets that satisfy these concepts. Finally, we illustrate the use of our results in assemble-to-order systems.

Suggested Citation

  • Xin Chen & Daniel Zhuoyu Long & Jin Qi, 2021. "Preservation of Supermodularity in Parametric Optimization: Necessary and Sufficient Conditions on Constraint Structures," Operations Research, INFORMS, vol. 69(1), pages 1-12, January.
    • Handle: RePEc:inm:oropre:v:69:y:2021:i:1:p:1-12
    DOI: 10.1287/opre.2020.1992
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2020.1992
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2020.1992?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. John K.-H Quah, 2007. "The Comparative Statics of Constrained Optimization Problems," Econometrica, Econometric Society, vol. 75(2), pages 401-431, March.
    2. Oben Ceryan & Ozge Sahin & Izak Duenyas, 2013. "Dynamic Pricing of Substitutable Products in the Presence of Capacity Flexibility," Manufacturing & Service Operations Management, INFORMS, vol. 15(1), pages 86-101, April.
    3. Jian Yang, 2004. "Production Control in the Face of Storable Raw Material, Random Supply, and an Outside Market," Operations Research, INFORMS, vol. 52(2), pages 293-311, April.
    4. Xin Chen & Peng Hu & Stephen Shum & Yuhan Zhang, 2016. "Dynamic Stochastic Inventory Management with Reference Price Effects," Operations Research, INFORMS, vol. 64(6), pages 1529-1536, December.
    5. Atan, Zümbül & Ahmadi, Taher & Stegehuis, Clara & Kok, Ton de & Adan, Ivo, 2017. "Assemble-to-order systems: A review," European Journal of Operational Research, Elsevier, vol. 261(3), pages 866-879.
    6. Susan Athey, 2002. "Monotone Comparative Statics under Uncertainty," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 117(1), pages 187-223.
    7. Yao Zhao & David Simchi-Levi, 2006. "Performance Analysis and Evaluation of Assemble-to-Order Systems with Stochastic Sequential Lead Times," Operations Research, INFORMS, vol. 54(4), pages 706-724, August.
    8. Yingdong Lu & Jing-Sheng Song & David D. Yao, 2003. "Order Fill Rate, Leadtime Variability, and Advance Demand Information in an Assemble-to-Order System," Operations Research, INFORMS, vol. 51(2), pages 292-308, April.
    9. Xin Chen & Peng Hu & Simai He, 2013. "Technical Note---Preservation of Supermodularity in Parametric Optimization Problems with Nonlattice Structures," Operations Research, INFORMS, vol. 61(5), pages 1166-1173, October.
    10. Xiuli Chao & Hong Chen & Shaohui Zheng, 2009. "Dynamic Capacity Expansion for a Service Firm with Capacity Deterioration and Supply Uncertainty," Operations Research, INFORMS, vol. 57(1), pages 82-93, February.
    11. Mustafa K. Doğru & Martin I. Reiman & Qiong Wang, 2017. "Assemble-to-Order Inventory Management via Stochastic Programming: Chained BOMs and the M-System," Production and Operations Management, Production and Operations Management Society, vol. 26(3), pages 446-468, March.
    12. Yingdong Lu & Jing-Sheng Song & Yao Zhao, 2010. "No-Holdback Allocation Rules for Continuous-Time Assemble-to-Order Systems," Operations Research, INFORMS, vol. 58(3), pages 691-705, June.
    13. Frieda Granot & Arthur F. Veinott, 1985. "Substitutes, Complements and Ripples in Network Flows," Mathematics of Operations Research, INFORMS, vol. 10(3), pages 471-497, 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. Xiaojuan Zhang & Qian Liu & Min Li & Yang Zhou, 2022. "Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy," Journal of Combinatorial Optimization, Springer, vol. 44(5), pages 3549-3574, December.

    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. Atan, Zümbül & Ahmadi, Taher & Stegehuis, Clara & Kok, Ton de & Adan, Ivo, 2017. "Assemble-to-order systems: A review," European Journal of Operational Research, Elsevier, vol. 261(3), pages 866-879.
    2. Xin Chen & Peng Hu & Simai He, 2013. "Technical Note---Preservation of Supermodularity in Parametric Optimization Problems with Nonlattice Structures," Operations Research, INFORMS, vol. 61(5), pages 1166-1173, October.
    3. ElHafsi, Mohsen & Fang, Jianxin & Hamouda, Essia, 2020. "A novel decomposition-based method for solving general-product structure assemble-to-order systems," European Journal of Operational Research, Elsevier, vol. 286(1), pages 233-249.
    4. David A. Goldberg & Martin I. Reiman & Qiong Wang, 2021. "A Survey of Recent Progress in the Asymptotic Analysis of Inventory Systems," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1718-1750, June.
    5. Rahimi-Ghahroodi, S. & Al Hanbali, A. & Vliegen, I.M.H. & Cohen, M.A., 2019. "Joint optimization of spare parts inventory and service engineers staffing with full backlogging," International Journal of Production Economics, Elsevier, vol. 212(C), pages 39-50.
    6. de Kok, Ton & Grob, Christopher & Laumanns, Marco & Minner, Stefan & Rambau, Jörg & Schade, Konrad, 2018. "A typology and literature review on stochastic multi-echelon inventory models," European Journal of Operational Research, Elsevier, vol. 269(3), pages 955-983.
    7. Xin Chen & Menglong Li, 2021. "Discrete Convex Analysis and Its Applications in Operations: A Survey," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1904-1926, June.
    8. Jie Chu & Kai Huang, 2020. "Integrating decisions with advance supply information in an assemble‐to‐order system," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(1), pages 34-44, February.
    9. Karaarslan, Gönül A. & Atan, Zümbül & de Kok, Ton & Kiesmüller, Gudrun P., 2018. "Optimal and heuristic policies for assemble-to-order systems with different review periods," European Journal of Operational Research, Elsevier, vol. 271(1), pages 80-96.
    10. Mirman, Leonard J. & Morand, Olivier F. & Reffett, Kevin L., 2008. "A qualitative approach to Markovian equilibrium in infinite horizon economies with capital," Journal of Economic Theory, Elsevier, vol. 139(1), pages 75-98, March.
    11. Bar Light, 2021. "Stochastic Comparative Statics in Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 797-810, May.
    12. Walid W. Nasr, 2022. "Inventory systems with stochastic and batch demand: computational approaches," Annals of Operations Research, Springer, vol. 309(1), pages 163-187, February.
    13. Koch, Caleb M., 2019. "Index-wise comparative statics," Mathematical Social Sciences, Elsevier, vol. 102(C), pages 35-41.
    14. 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.
    15. Bar Light, 2019. "Stochastic Comparative Statics in Markov Decision Processes," Papers 1904.05481, arXiv.org, revised Jan 2020.
    16. Mustafa K. Doğru & Martin I. Reiman & Qiong Wang, 2010. "A Stochastic Programming Based Inventory Policy for Assemble-to-Order Systems with Application to the W Model," Operations Research, INFORMS, vol. 58(4-part-1), pages 849-864, August.
    17. Bruno Strulovici & Thomas Weber, 2010. "Generalized monotonicity analysis," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 43(3), pages 377-406, June.
    18. Zhu, Stuart X., 2013. "Dynamic replenishment, production, and pricing decisions, in the face of supply disruption and random price-sensitive demand," International Journal of Production Economics, Elsevier, vol. 146(2), pages 612-619.
    19. Kai Huang, 2014. "Benchmarking non-first-come-first-served component allocation in an assemble-to-order system," Annals of Operations Research, Springer, vol. 223(1), pages 217-237, December.
    20. Yao Zhao, 2008. "Evaluation and Optimization of Installation Base-Stock Policies in Supply Chains with Compound Poisson Demand," Operations Research, INFORMS, vol. 56(2), pages 437-452, April.

    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:69:y:2021:i:1:p:1-12. 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.