IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v33y2021i2p685-705.html
   My bibliography  Save this article

Lagrangian Duality for Robust Problems with Decomposable Functions: The Case of a Robust Inventory Problem

Author

Listed:
  • Filipe Rodrigues

    (Department of Mathematics, University of Aveiro, 3810-193 Aveiro, Portugal)

  • Agostinho Agra

    (Department of Mathematics, University of Aveiro, 3810-193 Aveiro, Portugal)

  • Cristina Requejo

    (Department of Mathematics, University of Aveiro, 3810-193 Aveiro, Portugal)

  • Erick Delage

    (Department of Decision Sciences, HEC Montréal, Montreal, Quebec H3T 2A7, Canada; Group for Research in Decision Analysis (GERAD), Montreal, Quebec H3T 1J4, Canada)

Abstract

We consider a class of min-max robust problems in which the functions that need to be “robustified” can be decomposed as the sum of arbitrary functions. This class of problems includes many practical problems, such as the lot-sizing problem under demand uncertainty. By considering a Lagrangian relaxation of the uncertainty set, we derive a tractable approximation, called the dual Lagrangian approach, that we relate with both the classical dualization approximation approach and an exact approach. Moreover, we show that the dual Lagrangian approach coincides with the affine decision rule approximation approach. The dual Lagrangian approach is applied to a lot-sizing problem, in which demands are assumed to be uncertain and to belong to the uncertainty set with a budget constraint for each time period. Using the insights provided by the interpretation of the Lagrangian multipliers as penalties in the proposed approach, two heuristic strategies, a new guided iterated local search heuristic, and a subgradient optimization method are designed to solve more complex lot-sizing problems in which additional practical aspects, such as setup costs, are considered. Computational results show the efficiency of the proposed heuristics that provide a good compromise between the quality of the robust solutions and the running time required in their computation. Summary of Contribution: The paper includes both theoretical and algorithmic contributions for a class of min-max robust optimization problems where the objective function includes the maximum of a sum of affine functions. From the theoretical point of view, a tractable Lagrangian dual model resulting from a relaxation of the well-known adversarial problem is proposed, providing a new perspective of well-known models, such as the affinely adjustable robust counterpart (AARC) and the dualization technique introduced by Bertsimas and Sim. These results are particularized to lot-sizing problems. From the algorithm point of view, efficient heuristic schemes—which exploit the information based on the interpretation of the Lagrangian multipliers to solve large size robust problems—are proposed, and their performance is evaluated through extensive computational results based on the lot-sizing problem. In particular, a guided iterated local search and a subgradient optimization method are proposed and compared against the dualization approach proposed by Bertsimas and Sim and with several heuristics based on the AARC approach, which include an iterated local search heuristic and a Benders decomposition approach. Computational results show the efficiency of the proposed heuristics, which provide a good compromise between the quality of the robust solutions and the running time.

Suggested Citation

  • Filipe Rodrigues & Agostinho Agra & Cristina Requejo & Erick Delage, 2021. "Lagrangian Duality for Robust Problems with Decomposable Functions: The Case of a Robust Inventory Problem," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 685-705, May.
  • Handle: RePEc:inm:orijoc:v:33:y:2021:i:2:p:685-705
    DOI: 10.1287/ijoc.2020.0978
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.0978
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2020.0978?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. Yanıkoğlu, İhsan & Gorissen, Bram L. & den Hertog, Dick, 2019. "A survey of adjustable robust optimization," European Journal of Operational Research, Elsevier, vol. 277(3), pages 799-813.
    2. Dimitris Bertsimas & Frans J. C. T. de Ruiter, 2016. "Duality in Two-Stage Adaptive Linear Optimization: Faster Computation and Stronger Bounds," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 500-511, August.
    3. Angelos Georghiou & Angelos Tsoukalas & Wolfram Wiesemann, 2020. "A Primal–Dual Lifting Scheme for Two-Stage Robust Optimization," Operations Research, INFORMS, vol. 68(2), pages 572-590, March.
    4. Dan A. Iancu & Mayank Sharma & Maxim Sviridenko, 2013. "Supermodularity and Affine Policies in Dynamic Robust Optimization," Operations Research, INFORMS, vol. 61(4), pages 941-956, August.
    5. Oğuz Solyalı & Jean-François Cordeau & Gilbert Laporte, 2012. "Robust Inventory Routing Under Demand Uncertainty," Transportation Science, INFORMS, vol. 46(3), pages 327-340, August.
    6. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    7. Amir Ardestani-Jaafari & Erick Delage, 2016. "Robust Optimization of Sums of Piecewise Linear Functions with Application to Inventory Problems," Operations Research, INFORMS, vol. 64(2), pages 474-494, April.
    8. Gorissen, Bram L. & den Hertog, Dick, 2013. "Robust counterparts of inequalities containing sums of maxima of linear functions," European Journal of Operational Research, Elsevier, vol. 227(1), pages 30-43.
    9. Amir Ardestani-Jaafari & Erick Delage, 2018. "The Value of Flexibility in Robust Location–Transportation Problems," Transportation Science, INFORMS, vol. 52(1), pages 189-209, January.
    10. Dimitris Bertsimas & Aurélie Thiele, 2006. "A Robust Optimization Approach to Inventory Theory," Operations Research, INFORMS, vol. 54(1), pages 150-168, February.
    11. Wei, Cansheng & Li, Yongjian & Cai, Xiaoqiang, 2011. "Robust optimal policies of production and inventory with uncertain returns and demand," International Journal of Production Economics, Elsevier, vol. 134(2), pages 357-367, December.
    12. Xin Chen & Yuhan Zhang, 2009. "Uncertain Linear Programs: Extended Affinely Adjustable Robust Counterparts," Operations Research, INFORMS, vol. 57(6), pages 1469-1482, 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. Chargui, Kaoutar & Zouadi, Tarik & Sreedharan, V. Raja & El Fallahi, Abdellah & Reghioui, Mohamed, 2023. "A novel robust exact decomposition algorithm for berth and quay crane allocation and scheduling problem considering uncertainty and energy efficiency," Omega, Elsevier, vol. 118(C).
    2. Metzker Soares, Paula & Thevenin, Simon & Adulyasak, Yossiri & Dolgui, Alexandre, 2024. "Adaptive robust optimization for lot-sizing under yield uncertainty," European Journal of Operational Research, Elsevier, vol. 313(2), pages 513-526.

    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. Amir Ardestani-Jaafari & Erick Delage, 2016. "Robust Optimization of Sums of Piecewise Linear Functions with Application to Inventory Problems," Operations Research, INFORMS, vol. 64(2), pages 474-494, April.
    2. Hamed Mamani & Shima Nassiri & Michael R. Wagner, 2017. "Closed-Form Solutions for Robust Inventory Management," Management Science, INFORMS, vol. 63(5), pages 1625-1643, May.
    3. Aliakbari Sani, Sajad & Bahn, Olivier & Delage, Erick, 2022. "Affine decision rule approximation to address demand response uncertainty in smart Grids’ capacity planning," European Journal of Operational Research, Elsevier, vol. 303(1), pages 438-455.
    4. Jianzhe Zhen & Ahmadreza Marandi & Danique de Moor & Dick den Hertog & Lieven Vandenberghe, 2022. "Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2410-2427, September.
    5. Mengshi Lu & Zuo‐Jun Max Shen, 2021. "A Review of Robust Operations Management under Model Uncertainty," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1927-1943, June.
    6. Angelos Georghiou & Angelos Tsoukalas & Wolfram Wiesemann, 2020. "A Primal–Dual Lifting Scheme for Two-Stage Robust Optimization," Operations Research, INFORMS, vol. 68(2), pages 572-590, March.
    7. Metzker Soares, Paula & Thevenin, Simon & Adulyasak, Yossiri & Dolgui, Alexandre, 2024. "Adaptive robust optimization for lot-sizing under yield uncertainty," European Journal of Operational Research, Elsevier, vol. 313(2), pages 513-526.
    8. Viktoryia Buhayenko & Dick den Hertog, 2017. "Adjustable Robust Optimisation approach to optimise discounts for multi-period supply chain coordination under demand uncertainty," International Journal of Production Research, Taylor & Francis Journals, vol. 55(22), pages 6801-6823, November.
    9. Marcio Costa Santos & Michael Poss & Dritan Nace, 2018. "A perfect information lower bound for robust lot-sizing problems," Annals of Operations Research, Springer, vol. 271(2), pages 887-913, December.
    10. Andreas Thorsen & Tao Yao, 2017. "Robust inventory control under demand and lead time uncertainty," Annals of Operations Research, Springer, vol. 257(1), pages 207-236, October.
    11. Agra, Agostinho & Poss, Michael & Santos, Micael, 2018. "Optimizing make-to-stock policies through a robust lot-sizing model," International Journal of Production Economics, Elsevier, vol. 200(C), pages 302-310.
    12. Ning Zhang & Chang Fang, 2020. "Saddle point approximation approaches for two-stage robust optimization problems," Journal of Global Optimization, Springer, vol. 78(4), pages 651-670, December.
    13. Thevenin, Simon & Ben-Ammar, Oussama & Brahimi, Nadjib, 2022. "Robust optimization approaches for purchase planning with supplier selection under lead time uncertainty," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1199-1215.
    14. Xie, Chen & Wang, Liangquan & Yang, Chaolin, 2021. "Robust inventory management with multiple supply sources," European Journal of Operational Research, Elsevier, vol. 295(2), pages 463-474.
    15. Jiankun Sun & Jan A. Van Mieghem, 2019. "Robust Dual Sourcing Inventory Management: Optimality of Capped Dual Index Policies and Smoothing," Manufacturing & Service Operations Management, INFORMS, vol. 21(4), pages 912-931, October.
    16. Shin, Youngchul & Lee, Sangyoon & Moon, Ilkyeong, 2021. "Robust multiperiod inventory model with a new type of buy one get one promotion: “My Own Refrigerator”," Omega, Elsevier, vol. 99(C).
    17. Amir Ardestani-Jaafari & Erick Delage, 2021. "Linearized Robust Counterparts of Two-Stage Robust Optimization Problems with Applications in Operations Management," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1138-1161, July.
    18. Guanglin Xu & Samuel Burer, 2018. "A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides," Computational Optimization and Applications, Springer, vol. 70(1), pages 33-59, May.
    19. Walid Ben-Ameur & Adam Ouorou & Guanglei Wang & Mateusz Żotkiewicz, 2018. "Multipolar robust optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 395-434, December.
    20. Borumand, Ali & Marandi, Ahmadreza & Nookabadi, Ali S. & Atan, Zümbül, 2024. "An oracle-based algorithm for robust planning of production routing problems in closed-loop supply chains of beverage glass bottles," Omega, Elsevier, vol. 122(C).

    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:orijoc:v:33:y:2021:i:2:p:685-705. 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.