Generating Lagrangian Cuts Using Normalized Dual Problems in Multistage Stochastic Mixed-Integer Programming

Abstract

Based on recent advances in Benders decomposition and two-stage stochastic integer programming, we present a framework to generate Lagrangian cuts in multistage stochastic mixed-integer linear programming by solving normalized dual problems. This framework can be incorporated into existing solution methods, such as stochastic dual dynamic integer programming. We show how different normalizations can be applied in order to generate cuts satisfying specific properties with respect to the convex hull of the epigraph of the value functions (e.g., having a maximum depth or being facet defining). We provide computational results to evaluate the efficacy and performance of this approach, showing that compared with existing techniques from the literature, significantly better lower bounds can be obtained. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: The research of C. Füllner was funded by the Deutsche Forschungsgemeinschaft [Grant 445857709]. A research visit of C. Füllner at the Georgia Institute of Technology was funded by the Karlsruhe House of Young Scientists. The research of X. A. Sun was partially funded by the National Science Foundation [CAREER Award 2316675]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1039 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.1039 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .