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

References

• Ahmed S, Cabral FG, da Costa BFP (2022) Stochastic Lipschitz dynamic programming. Math. Programming 191:755–793.Crossref, Google Scholar
• Balas E, Ivanescu PL (1964) On the generalized transportation problem. Management Sci. 11(1):188–202.Link, Google Scholar
• Bansal A, Küçükyavuz S (2026) Integer L-shaped and Lagrangian cuts revisited: A unified perspective. Oper. Res. Lett. 66:107427.Crossref, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing. SIAM Rev. 59(1):65–98.Crossref, Google Scholar
• Brandenberg R, Stursberg P (2021) Refined cut selection for Benders decomposition: Applied to network capacity expansion problems. Math. Methods Oper. Res. 94:383–412.Crossref, Google Scholar
• Cadoux F (2010) Computing deep facet-defining disjunctive cuts for mixed-integer programming. Math. Programming 122:197–223.Crossref, Google Scholar
• Chen R, Luedtke J (2022) On generating Lagrangian cuts for two-stage stochastic integer programs. INFORMS J. Comput. 34(4):2332–2349.Link, Google Scholar
• Conforti M, Wolsey LA (2019) “Facet” separation with one linear program. Math. Programming 178:361–380.Crossref, Google Scholar
• Cornuéjols G, Lemaréchal C (2006) A convex-analysis perspective on disjunctive cuts. Math. Programming 106:567–586.Crossref, Google Scholar
• Deng H, Xie W (2024) On the ReLU Lagrangian cuts for stochastic mixed integer programming, Preprint, submitted November 9, https://arxiv.org/abs/2411.01229.Google Scholar
• Dowson O, Kapelevich L (2021) SDDP.jl: A Julia package for stochastic dual dynamic programming. INFORMS J. Comput. 33(1):27–33.Link, Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Crossref, Google Scholar
• Fischetti M, Salvagnin D, Zanette A (2010) A note on the selection of Benders’ cuts. Math. Programming 124:175–182.Crossref, Google Scholar
• Füllner C (2024) On approximating non-convex value functions in stochastic dual dynamic programming and related decomposition methods. PhD thesis, Karlsruher Institut für Technologie, Karlsruhe, Germany.Google Scholar
• Füllner C, Rebennack S (2022) Non-convex nested Benders decomposition. Math. Programming 196:987–1024.Crossref, Google Scholar
• Füllner C, Sun XA, Rebennack S (2024) On Lipschitz regularization and Lagrangian cuts in multistage stochastic mixed-integer linear programming. Preprint, submitted August 7, https://optimization-online.org/?p=27295.Google Scholar
• Füllner C, Sun XA, Rebennack S (2026) Generating Lagrangian cuts using normalized dual problems in multistage stochastic mixed-integer programming. https://doi.org/10.1287/ijoc.2024.1039.cd, https://github.com/INFORMSJoC/2024.1039.Google Scholar
• Glomb L, Liers F, Rösel F (2026) A novel Pareto-optimal cut selection strategy for Benders decomposition. Math. Programming Comput. 18:211–257.Crossref, Google Scholar
• Hosseini M, Turner J (2025) Deepest cuts for Benders decomposition. Oper. Res. 73(5):2591–2609.Link, Google Scholar
• Kelley JE (1960) The cutting-plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8(4):703–712.Crossref, Google Scholar
• Lemaréchal C, Nemirovskii A, Nesterov Y (1995) New variants of bundle methods. Math. Programming 69(1–3):111–147.Crossref, Google Scholar
• Magnanti T, Wong R (1981) Accelerating benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Papadakos N (2008) Practical enhancements to the Magnanti–Wong method. Oper. Res. Lett. 36:444–449.Crossref, Google Scholar
• Pereira MVF, Pinto LMVG (1991) Multi-stage stochastic optimization applied to energy planning. Math. Programming 52(1–3):359–375.Crossref, Google Scholar
• Rahmaniani R, Ahmed S, Crainic TG, Gendreau M, Rei W (2020) The Benders dual decomposition method. Oper. Res. 68(3):878–895.Link, Google Scholar
• Seo K, Joung S, Lee C, Park S (2022) A closest Benders cut selection scheme for accelerating the Benders decomposition algorithm. INFORMS J. Comput. 34(5):2804–2827.Link, Google Scholar
• Seranilla BK, Löhndorf N (2024) Multistage stochastic facility location under facility disruption uncertainty. Preprint, submitted May 13, https://optimization-online.org/?p=26395.Google Scholar
• Sherali HD, Lunday BJ (2013) On generating maximal nondominated Benders cuts. Ann. Oper. Res. 210:57–72.Crossref, Google Scholar
• Stursberg PM (2019) On the mathematics of energy system optimization. PhD thesis, TU München, Munich, Germany.Google Scholar
• Trigeiro WW, Thomas LJ, McClain JO (1989) Capacitated lot sizing with setup times. Management Sci. 35(3):353–366.Link, Google Scholar
• Zou J, Ahmed S, Sun XA (2019) Stochastic dual dynamic integer programming. Math. Programming 175:461–502.Crossref, Google Scholar