Lagrangian Dual Decision Rules for Multistage Stochastic Mixed-Integer Programming

References

• Ahmed S, Cabral FG, da Costa BFP (2022) Stochastic Lipschitz dynamic programming. Math. Program. 191(2):755–793.Crossref, Google Scholar
• Ahmed S, King AJ, Parija G (2003) A multi-stage stochastic integer programming approach for capacity expansion under uncertainty. J. Global Optim. 26(1):3–24.Crossref, Google Scholar
• Alonso-Ayuso A, Escudero LF, Ortuno MT (2003) BFC, a branch-and-fix coordination algorithmic framework for solving some types of stochastic pure and mixed 0–1 programs. Eur. J. Oper. Res. 151(3):503–519.Crossref, Google Scholar
• Angulo G, Ahmed S, Dey SS (2016) Improving the integer L-shaped method. INFORMS J. Comput. 28(3):483–499.Link, Google Scholar
• Bampou D, Kuhn D (2011) Scenario-free stochastic programming with polynomial decision rules. 50th IEEE Conf. Decision Control Eur. Control Conf. (IEEE, Piscataway, NJ), 7806–7812.Google Scholar
• Barty K, Carpentier P, Girardeau P (2010) Decomposition of large-scale stochastic optimal control problems. RAIRO Oper. Res. 44(3):167–183.Crossref, Google Scholar
• Bodur M, Luedtke J (2017) Mixed-integer rounding enhanced Benders decomposition for multiclass service system staffing and scheduling with arrival rate uncertainty. Management Sci. 63:2073–2091.Link, Google Scholar
• Bodur M, Luedtke JR (2022) Two-stage linear decision rules for multi-stage stochastic programming. Math. Program. 191:347–380.Crossref, Google Scholar
• Brown DB, Smith JE, Sun P (2010) Information relaxations and duality in stochastic dynamic programs. Oper. Res. 58(4-part-1):785–801.Google Scholar
• Buhmann MD (2000) Radial basis functions. Acta Numerica 9:1–38.Crossref, Google Scholar
• Carøe CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1–2):37–45.Crossref, Google Scholar
• Cen Z (2012) Solving multi-stage stochastic mixed integer linear programs by the dual dynamic programming approach. INRIA Research Report RR-7868, INRIA, Le Chesnay-Rocquencourt, France.Google Scholar
• Cerisola S, Latorre JM, Ramos A (2012) Stochastic dual dynamic programming applied to nonconvex hydrothermal models. Eur. J. Oper. Res. 218(3):687–697.Crossref, Google Scholar
• Chen X, Sim M, Sun P, Zhang J (2008) A linear decision-based approximation approach to stochastic programming. Oper. Res. 56(2):344–357.Link, Google Scholar
• Chen X, Zhu S, Jiang L, Zhu Z (2015) On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks. J. Lightwave Tech. 33(17):3719–3729.Crossref, Google Scholar
• Chen ZL, Li S, Tirupati D (2002) A scenario-based stochastic programming approach for technology and capacity planning. Comput. Oper. Res. 29(7):781–806.Crossref, Google Scholar
• Daryalal M, Bodur M (2022) Stochastic RWA and lightpath rerouting in WDM networks. INFORMS J. Comput., ePub ahead of print June 13, https://doi.org/10.1287/ijoc.2022.1179.Google Scholar
• Dentcheva D, Römisch W (2004) Duality gaps in nonconvex stochastic optimization. Math. Program. 101(3):515–535.Crossref, Google Scholar
• Fan Y, Liu C (2010) Solving stochastic transportation network protection problems using the progressive hedging-based method. Networks Spatial Econom. 10(2):193–208.Crossref, Google Scholar
• Ferland R, Latour A, Oraichi D (2006) Integer-valued GARCH process. J. Time Ser. Anal. 27(6):923–942.Crossref, Google Scholar
• Flach B, Barroso L, Pereira M (2010) Long-term optimal allocation of hydro generation for a price-maker company in a competitive market: Latest developments and a stochastic dual dynamic programming approach. IET Generation Transmission Distribution 4(2):299–314.Crossref, Google Scholar
• Flatabø N, Haugstad A, Mo B, Fosso OB (1998) Short-term and medium-term generation scheduling in the Norwegian hydro system under a competitive power market structure. Internat. Conf. Electrical Power System Oper. Management, Zurich, 1–8.Google Scholar
• Friedman J, Hastie T, Tibshirani R (2001) The Elements of Statistical Learning, Springer Series in Statistics, vol. 1 (Springer, New York).Google Scholar
• Gade D, Hackebeil G, Ryan SM, Watson JP, Wets RJB, Woodruff DL (2016) Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs. Math. Program. 157(1):47–67.Crossref, Google Scholar
• Gade D, Küçükyavuz S, Sen S (2014) Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs. Math. Program. 144(1–2):39–64.Crossref, Google Scholar
• Georghiou A, Wiesemann W, Kuhn D (2015) Generalized decision rule approximations for stochastic programming via liftings. Math. Program. 152(1–2):301–338.Crossref, Google Scholar
• Giorgetti A, Paolucci F, Cugini F, Castoldi P (2015) Dynamic restoration with GMPLS and SDN control plane in elastic optical networks. J. Optical Commun. Networking 7(2):A174–A182.Crossref, Google Scholar
• Guan Y, Ahmed S, Nemhauser GL (2009) Cutting planes for multistage stochastic integer programs. Oper. Res. 57(2):287–298.Link, Google Scholar
• Gul S, Denton BT, Fowler JW (2015) A progressive hedging approach for surgery planning under uncertainty. INFORMS J. Comput. 27(4):755–772.Link, Google Scholar
• Hajizadeh E, Mahootchi M (2018) Optimized radial basis function neural network for improving approximate dynamic programming in pricing high dimensional options. Neural Comput. Appl. 30(6):1783–1794.Crossref, Google Scholar
• Helber S, Sahling F, Schimmelpfeng K (2013) Dynamic capacitated lot sizing with random demand and dynamic safety stocks. OR Spectrum 35(1):75–105.Crossref, Google Scholar
• Helseth A, Mo B, Fodstad M, Hjelmeland MN (2015) Co-optimizing sales of energy and capacity in a hydropower scheduling model. 2015 IEEE Eindhoven PowerTech (IEEE, Piscataway, NJ), 1–6.Crossref, Google Scholar
• Higle J, Sen S (1996) Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming, Nonconvex Optimization and its Applications, vol. 8 (Springer-Verlag, Boston).Crossref, Google Scholar
• Jaumard B, Daryalal M (2017) Efficient spectrum utilization in large scale RWA problems. IEEE/ACM Trans. Networking 25(2):1263–1278.Crossref, Google Scholar
• Keller PW, Mannor S, Precup D (2006) Automatic basis function construction for approximate dynamic programming and reinforcement learning. ICML’06 Proc. 23rd Internat. Conf. Machine Learning (Association for Computing Machinery, New York), 449–456.Google Scholar
• Kim K, Petra CG, Zavala VM (2019) An asynchronous bundle-trust-region method for dual decomposition of stochastic mixed-integer programming. SIAM J. Optim. 29(1):318–342.Crossref, Google Scholar
• Kiwiel KC (1995) Approximations in proximal bundle methods and decomposition of convex programs. J. Optim. Theory Appl. 84(3):529–548.Crossref, Google Scholar
• Küçükyavuz S, Sen S (2017) An introduction to two-stage stochastic mixed-integer programming. Batta R, Peng J, eds. Leading Developments from INFORMS Communities, INFORMS TutORials in Operations Research (INFORMS, Catonsville, MD), 1–27.Link, Google Scholar
• Kuhn D, Wiesemann W, Georghiou A (2011) Primal and dual linear decision rules in stochastic and robust optimization. Math. Program. 130(1):177–209.Crossref, Google Scholar
• Laporte G, Louveaux FV (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3):133–142.Crossref, Google Scholar
• Listes O, Dekker R (2005) A scenario aggregation-based approach for determining a robust airline fleet composition for dynamic capacity allocation. Transportation Sci. 39(3):367–382.Link, Google Scholar
• Löhndorf N, Wozabal D, Minner S (2013) Optimizing trading decisions for hydro storage systems using approximate dual dynamic programming. Oper. Res. 61(4):810–823.Link, Google Scholar
• Løkketangen A, Woodruff DL (1996) Progressive hedging and tabu search applied to mixed integer (0, 1) multistage stochastic programming. J. Heuristics 2(2):111–128.Crossref, Google Scholar
• Lubin M, Martin K, Petra CG, Sandıkçı B (2013) On parallelizing dual decomposition in stochastic integer programming. Oper. Res. Lett. 41(3):252–258.Crossref, Google Scholar
• Lulli G, Sen S (2004) A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems. Management Sci. 50(6):786–796.Link, Google Scholar
• Lulli G, Sen S (2006) A heuristic procedure for stochastic integer programs with complete recourse. Eur. J. Oper. Res. 171(3):879–890.Crossref, Google Scholar
• Mo B, Gjelsvik A, Grundt A, Karesen K (2001) Optimisation of hydropower operation in a liberalised market with focus on price modelling. 2001 IEEE Porto Power Tech Proc., vol. 1, Cat. No.01EX502 (IEEE, Piscataway, NJ), 6.Crossref, Google Scholar
• Nemirovski A, Juditsky A, Lan G, Shapiro A (2009) Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4):1574–1609.Crossref, Google Scholar
• Newham N, Wood A (2007) Transmission investment planning using SDDP. Australasian Universities Power Engrg. Conf. (IEEE, Piscataway, NJ), 1–5.Google Scholar
• Norkin VI, Pflug GC, Ruszczyński A (1998) A branch and bound method for stochastic global optimization. Math. Program. 83(1–3):425–450.Crossref, Google Scholar
• Nowak MP, Römisch W (2000) Stochastic Lagrangian relaxation applied to power scheduling in a hydro-thermal system under uncertainty. Ann. Oper. Res. 100(1–4):251–272.Crossref, Google Scholar
• Orlowski S, Wessäly R, Pióro M, Tomaszewski A (2010) SNDlib 1.0–Survivable network design library. Networks 55(3):276–286.Crossref, Google Scholar
• Pereira MV, Pinto LM (1991) Multi-stage stochastic optimization applied to energy planning. Math. Program. 52(1–3):359–375.Crossref, Google Scholar
• Philpott A, Wahid F, Bonnans J (2020) MIDAS: A mixed integer dynamic approximation scheme. Math. Program. 181:19–50.Crossref, Google Scholar
• Powell WB (2009) What you should know about approximate dynamic programming. Naval Res. Logist. 56(3):239–249.Crossref, Google Scholar
• Qi Y, Sen S (2017) The ancestral Benders’ cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming. Math. Program. 161(1–2):193–235.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
• Rajagopalan S, Singh MR, Morton TE (1998) Capacity expansion and replacement in growing markets with uncertain technological breakthroughs. Management Sci. 44(1):12–30.Link, Google Scholar
• Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400–407.Crossref, Google Scholar
• Rockafellar RT, Wets RJ (1976) Stochastic convex programming: Relatively complete recourse and induced feasibility. SIAM J. Control Optim. 14(3):574–589.Crossref, Google Scholar
• Rockafellar RT, Wets RJB (1991) Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1):119–147.Link, Google Scholar
• Romeijnders W, Schultz R, van der Vlerk MH, Klein Haneveld WK (2016) A convex approximation for two-stage mixed-integer recourse models with a uniform error bound. SIAM J. Optim. 26(1):426–447.Crossref, Google Scholar
• Rosa CH, Ruszczyński A (1996) On augmented Lagrangian decomposition methods for multistage stochastic programs. Ann. Oper. Res. 64(1):289–309.Crossref, Google Scholar
• Ruszczyński A (1986) A regularized decomposition method for minimizing a sum of polyhedral functions. Math. Program. 35(3):309–333.Crossref, Google Scholar
• Sandıkçı B, Ozaltın OY (2014) A scalable bounding method for multi-stage stochastic integer programs. Chicago Booth Research Paper 14-21, University of Chicago, Chicago.Google Scholar
• Sandıkçı B, Kong N, Schaefer AJ (2013) A hierarchy of bounds for stochastic mixed-integer programs. Math. Program. 138(1):253–272.Crossref, Google Scholar
• Sen S, Higle JL (2005) The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: set convexification. Math. Program. 104:1–20.Crossref, Google Scholar
• Sen S, Sherali H (2006) Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Math. Program. 106:203–223.Crossref, Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2009) Lectures on Stochastic Programming: Modeling and Theory (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Shapiro A, Nemirovski A (2005) On complexity of stochastic programming problems. Jeyakumar V, Rubinov A, eds. Continuous Optimization, Applied Optimization, vol. 99 (Springer, Boston), 111–146.Crossref, Google Scholar
• Sherali H, Zhu X (2007) On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables. Math. Program. 108:597–616.Crossref, Google Scholar
• Simmons JM, Rouskas GN (2020) Routing and wavelength (spectrum) assignment. Mukherjee B, Tomkos I, Tornatore M, Winzer P, Zhao Y, eds. Springer Handbook of Optical Networks, Springer Handbooks (Springer, Cham, Switzerland), 447–484.Crossref, Google Scholar
• Singh KJ, Philpott AB, Wood RK (2009) Dantzig-Wolfe decomposition for solving multistage stochastic capacity-planning problems. Oper. Res. 57(5):1271–1286.Link, Google Scholar
• Takriti S, Birge JR, Long E (1996) A stochastic model for the unit commitment problem. IEEE Trans. Power Systems 11(3):1497–1508.Crossref, Google Scholar
• Tanner M, Ntaimo L (2008) Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs. J. Global Optim. 58:365–384.Google Scholar
• van der Laan N, Romeijnders W (2021a) A converging Benders’ decomposition algorithm for two-stage mixed-integer recourse models. Working paper, University of Groningen, Groningen, Netherlands.Google Scholar
• van der Laan N, Romeijnders W (2021b) A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models. Math. Program. 190(1):761–794.Crossref, Google Scholar
• Watson JP, Woodruff DL (2011) Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems. Comput. Management Sci. 8(4):355–370.Crossref, Google Scholar
• Xiong Y, Li Y, Zhou B, Wang R, Rouskas GN (2018) SDN enabled restoration with triggered precomputation in elastic optical inter-datacenter networks. J. Optical Commun. Networks 10(1):24–34.Crossref, Google Scholar
• Zhang M, Küçükyavuz S (2014) Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs. SIAM J. Optim. 24:1933–1951.Crossref, Google Scholar
• Zou J (2017) Large scale multistage stochastic integer programming with applications in electric power systems. PhD thesis, Georgia Institute of Technology, Atlanta.Google Scholar
• Zou J, Ahmed S, Sun XA (2019) Stochastic dual dynamic integer programming. Math. Program. 175:461–502.Crossref, Google Scholar