Parallelizing Subgradient Methods for the Lagrangian Dual in Stochastic Mixed-Integer Programming

References

• Ahmed S, Garcia R (2003) Dynamic capacity acquisition and assignment under uncertainty. Ann. Oper. Res. 124(1–4):267–283.Google Scholar
• Ahmed S, Garcia R, Kong N, Ntaimo L, Qiu F, Sen S (2015) SIPLIB: A stochastic integer programming test problem library. Accessed November 17, 2019, https://www2.isye.gatech.edu/∼sahmed/siplib/.Google Scholar
• Aravena I, Papavasiliou A (2015) A distributed asynchronous algorithm for the two-stage stochastic unit commitment problem. 2015 IEEE Power Energy Society General Meeting (IEEE, New York), 1–5.Google Scholar
• Bertsekas DP (1999) Nonlinear Programming, 2nd ed. (Athena Scientific, Belmont, MA).Google Scholar
• Bodur M, Dash S, Günlük O, Luedtke J (2016) Strengthened Benders cuts for stochastic integer programs with continuous recourse. INFORMS J. Comput. 29:77–91.Link, Google Scholar
• Boland N, Bakir I, Dandurand B, Erera A (2016) Scenario set partition dual bounds for multistage stochastic programming: A hierarchy of bounds and a partition sampling approach. Preprint, submitted January 28, http://www.optimization-online.org/DB_HTML/2016/01/5311.html.Google Scholar
• Bubeck S, Cesa-Bianchi N (2002) Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations Trends Machine Learn. 5(1):1–122.Google Scholar
• Carøe CC (1998) Decomposition in stochastic integer programming. Unpublished doctoral thesis, Department of Operations Research, University of Copenhagen, Copenhagen, Denmark.Google Scholar
• Carøe CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1–2):37–45.Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming, Graduate Texts in Mathematics, vol. 271 (Springer, Cham, Switzerland).Google Scholar
• Dey SS, Molinaro M, Wang Q (2018) Analysis of sparse cutting planes for sparse MILPS with applications to stochastic MILPS. Math. Oper. Res. 43(1):304–332.Link, Google Scholar
• Duchi JC, Agarwal A, Wainwright MJ (2012) Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Trans. Automatic Control 57(3):592–606.Google Scholar
• Ermoliev YM (1966) Methods of solution of nonlinear extremal problems. Cybernetics 2(4):1–14.Google Scholar
• Kelley JJ (1960) The cutting-plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8(4):703–712.Google Scholar
• Kim K, Zavala VM (2017) Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs. Math. Program. Comput. 10:225–266.Google Scholar
• Kim K, Petra CG, Zavala VM (2017) An asynchronous bundle-trust-region method for dual decomposition of stochastic mixed-integer programming. Technical Report ANL/MCS-8046-0917, Argonne National Laboratory, Lemont, IL.Google Scholar
• Lemarechal C (1978) Nonsmooth optimization and descent methods. IIASA Research Report RR-78-004, International Institute for Applied Systems Analysis, Laxenburg, Austria.Google Scholar
• Lubin M, Martin K, Petra CG, Sandikci B (2013) On parallelizing dual decomposition in stochastic integer programming. Oper. Res. Lett. 41(3):252–258.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
• Maggioni F, Pflug GC (2016) Bounds and approximations for multistage stochastic programs. SIAM J. Optim. 26(1):831–855.Google Scholar
• Maggioni F, Allevi E, Bertocchi M (2016) Monotonic bounds in multistage mixed-integer stochastic programming. Comput. Management Sci. 13(3):423–457.Google Scholar
• Necoara I, Nesterov Y, Glineur F (2017) Random block coordinate descent methods for linearly constrained optimization over networks. J. Optim. Theory Appl. 173(1):227–254.Google Scholar
• Nesterov Y (2009) Primal-dual subgradient methods for convex problems. Math. Programming 120(1):221–259.Google Scholar
• Nesterov Y, Shikhman V (2015) Quasi-monotone subgradient methods for nonsmooth convex minimization. J. Optim. Theory Appl. 165(3):917–940.Google Scholar
• Ntaimo L, Sen S (2005) The million-variable ‘march’ for stochastic combinatorial optimization. J. Global Optim. 32(3):385–400.Google Scholar
• Rahmanai R, Ahmed S, Crainic T, Gendreau M, Rei W (2018) The Benders dual decomposition method. Technical Report CIRRELT-2018-03, Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, Montreal.Google Scholar
• Ruszczyński A (2006) Nonlinear Optimization (Princeton University Press, Princeton, NJ).Google Scholar
• Ryan K, Ahmed S, Dey SS, Rajan D (2016) Optimization driven scenario grouping. Preprint, submitted March 10, http://www.optimization-online.org/DB_HTML/2016/03/5366.html.Google Scholar
• Sandikçi B, Ozaltin OY (2017) A scalable bounding method for multistage stochastic programs. SIAM J. Optim. 27(3):1772–1800.Google Scholar
• Shor N (1985) Minimization Methods for Non-Differentiable Functions (Springer-Verlag, Berlin).Google Scholar
• Xiao L (2010) Dual averaging methods for regularized stochastic learning and online optimization. J. Machine Learn. Res. 11(88):2543–2596.Google Scholar