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

On Generating Lagrangian Cuts for Two-Stage Stochastic Integer Programs

Author

Listed:
  • Rui Chen

    (Department of Industrial and Systems Engineering, University of Wisconsin-Madison, Madison, Wisconsin 53706)

  • James Luedtke

    (Department of Industrial and Systems Engineering, University of Wisconsin-Madison, Madison, Wisconsin 53706)

Abstract

We investigate new methods for generating Lagrangian cuts to solve two-stage stochastic integer programs. Lagrangian cuts can be added to a Benders reformulation and are derived from solving single scenario integer programming subproblems identical to those used in the nonanticipative Lagrangian dual of a stochastic integer program. Although Lagrangian cuts have the potential to significantly strengthen the Benders relaxation, generating Lagrangian cuts can be computationally demanding. We investigate new techniques for generating Lagrangian cuts with the goal of obtaining methods that provide significant improvements to the Benders relaxation quickly. Computational results demonstrate that our proposed method improves the Benders relaxation significantly faster than previous methods for generating Lagrangian cuts and, when used within a branch-and-cut algorithm, significantly reduces the size of the search tree for three classes of test problems.

Suggested Citation

  • Rui Chen & James Luedtke, 2022. "On Generating Lagrangian Cuts for Two-Stage Stochastic Integer Programs," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2332-2349, July.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:4:p:2332-2349
    DOI: 10.1287/ijoc.2022.1185
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1185
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.1185?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. M. Avriel & A. C. Williams, 1970. "The Value of Information and Stochastic Programming," Operations Research, INFORMS, vol. 18(5), pages 947-954, October.
    2. Binyuan Chen & Simge Küçükyavuz & Suvrajeet Sen, 2011. "Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs," Operations Research, INFORMS, vol. 59(1), pages 202-210, February.
    3. Schütz, Peter & Tomasgard, Asgeir & Ahmed, Shabbir, 2009. "Supply chain design under uncertainty using sample average approximation and dual decomposition," European Journal of Operational Research, Elsevier, vol. 199(2), pages 409-419, December.
    4. Merve Bodur & Sanjeeb Dash & Oktay Günlük & James Luedtke, 2017. "Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 77-91, February.
    5. Guglielmo Lulli & Suvrajeet Sen, 2004. "A Branch-and-Price Algorithm for Multistage Stochastic Integer Programming with Application to Stochastic Batch-Sizing Problems," Management Science, INFORMS, vol. 50(6), pages 786-796, June.
    6. Lewis Ntaimo, 2013. "Fenchel decomposition for stochastic mixed-integer programming," Journal of Global Optimization, Springer, vol. 55(1), pages 141-163, January.
    7. Lemaréchal, C. & Nemirovskii, A. & Nesterov, Y., 1995. "New variants of bundle methods," LIDAM Reprints CORE 1166, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    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. Onur Tavaslıoğlu & Oleg A. Prokopyev & Andrew J. Schaefer, 2019. "Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function," Operations Research, INFORMS, vol. 67(6), pages 1659-1677, November.
    2. Pavlo Glushko & Csaba I. Fábián & Achim Koberstein, 2022. "An L-shaped method with strengthened lift-and-project cuts," Computational Management Science, Springer, vol. 19(4), pages 539-565, October.
    3. Francesca Maggioni & Elisabetta Allevi & Marida Bertocchi, 2016. "Monotonic bounds in multistage mixed-integer stochastic programming," Computational Management Science, Springer, vol. 13(3), pages 423-457, July.
    4. Lin, Cheng-Chang & Wu, Yi-Chen, 2013. "Optimal pricing for build-to-order supply chain design under price-dependent stochastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 31-49.
    5. Minjiao Zhang & Simge Küçükyavuz & Saumya Goel, 2014. "A Branch-and-Cut Method for Dynamic Decision Making Under Joint Chance Constraints," Management Science, INFORMS, vol. 60(5), pages 1317-1333, May.
    6. M. Fattahi & M. Mahootchi & S. M. Moattar Husseini, 2016. "Integrated strategic and tactical supply chain planning with price-sensitive demands," Annals of Operations Research, Springer, vol. 242(2), pages 423-456, July.
    7. Longinidis, Pantelis & Georgiadis, Michael C., 2014. "Integration of sale and leaseback in the optimal design of supply chain networks," Omega, Elsevier, vol. 47(C), pages 73-89.
    8. Rafiei, Rezvan & Huang, Kai & Verma, Manish, 2022. "Cash versus in-kind transfer programs in humanitarian operations: An optimization program and a case study," Socio-Economic Planning Sciences, Elsevier, vol. 82(PA).
    9. Zhen, Lu & Lee, Loo Hay & Chew, Ek Peng, 2011. "A decision model for berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 212(1), pages 54-68, July.
    10. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    11. Zhen, Lu & Zhuge, Dan & Wang, Shuaian & Wang, Kai, 2022. "Integrated berth and yard space allocation under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 1-27.
    12. Reinol Josef Compañero & Andreas Feldmann & Peter Samuelsson & Anders Tilliander & Pär Göran Jönsson & Rutger Gyllenram, 2023. "Appraising the value of compositional information and its implications to scrap-based production of steel," Mineral Economics, Springer;Raw Materials Group (RMG);Luleå University of Technology, vol. 36(3), pages 463-480, September.
    13. Quddus, Md Abdul & Shahvari, Omid & Marufuzzaman, Mohammad & Ekşioğlu, Sandra D. & Castillo-Villar, Krystel K., 2021. "Designing a reliable electric vehicle charging station expansion under uncertainty," International Journal of Production Economics, Elsevier, vol. 236(C).
    14. Zhicheng Zhu & Yisha Xiang & Bo Zeng, 2021. "Multicomponent Maintenance Optimization: A Stochastic Programming Approach," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 898-914, July.
    15. van der Laan, Niels & Romeijnders, Ward & van der Vlerk, M.H., 2017. "Higher-order total variation bounds for expectations of periodic functions and simple integer recourse approximations," Research Report 2017-014-EEF, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    16. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    17. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    18. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    19. Adam N. Elmachtoub & Paul Grigas, 2022. "Smart “Predict, then Optimize”," Management Science, INFORMS, vol. 68(1), pages 9-26, January.
    20. Yongpei Guan, 2011. "Stochastic lot-sizing with backlogging: computational complexity analysis," Journal of Global Optimization, Springer, vol. 49(4), pages 651-678, 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:orijoc:v:34:y:2022:i:4:p:2332-2349. 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.