A study of progressive hedging for stochastic integer programming
Tóm tắt
Motivated by recent literature demonstrating the surprising effectiveness of the heuristic application of progressive hedging (PH) to stochastic mixed-integer programming (SMIP) problems, we provide theoretical support for the inclusion of integer variables, bridging the gap between theory and practice. We provide greater insight into the following observed phenomena of PH as applied to SMIP where optimal or at least feasible convergence is observed. We provide an analysis of a modified PH algorithm from a different viewpoint, drawing on the interleaving of (split) proximal-point methods (including PH), Gauss–Seidel methods, and the utilisation of variational analysis tools. Through this analysis, we show that under mild conditions, convergence to a feasible solution should be expected. In terms of convergence analysis, we provide two main contributions. First, we contribute insight into the convergence of proximal-point-like methods in the presence of integer variables via the introduction of the notion of persistent local minima. Secondly, we contribute an enhanced Gauss–Seidel convergence analysis that accommodates the variation of the objective function under mild assumptions. We provide a practical implementation of a modified PH and demonstrate its convergent behaviour with computational experiments in line with the provided analysis.
Tài liệu tham khảo
Birge, J.R., Louveaux, F.: Introduction to stochastic programming. Springer, Berlin (2011)
Montero, L., Bello, A., Reneses, J.: A review on the unit commitment problem: approaches, techniques, and resolution methods. Energies 15(4), 1296 (2022)
Parvez, I., Shen, J., Cheng, C., Parvez, I., Shen, J., Khan, M., Cheng, C.: Modeling and solution techniques used for hydro generation scheduling. Water 11(7) (2019)
Turan, H., Kahagalage, S., El Sawah, S., Jalalvand, F.: A multi-objective simulation-optimization for a joint problem of strategic facility location, workforce planning, and capacity allocation: a case study in the royal australian navy. Expert Syst. Appl. 186, 115751 (2021)
Fadaki, M., Abareshi, A., Lee, P., Far, S.: Multi-period vaccine allocation model in a pandemic: a case study of covid-19 in Australia. Trans. Res. Part E: Logist. Trans. Rev. 161, 102689 (2022)
Shone, R., Glazebrook, K., Zografos, K.: Applications of stochastic modeling in air traffic management: methods, challenges and opportunities for solving air traffic problems under uncertainty. Eur. J. Oper. Res. 292(1), 1–26 (2021)
Badilla Veliz, F., Watson, J.-P., Weintraub, A., Wets, R.J.-B., Woodruff, D.L.: Stochastic optimization models in forest planning: a progressive hedging solution approach. Ann. Oper. Res. 232, 259–274 (2015)
Fan, Y., Schwartz, F., Voß, S., Woodruff, D.L.: Stochastic programming for global supply chain planning under uncertainty: an outline. In: Bektaş, T., Coniglio, S., Martinez-Sykora, A., Voß, S. (eds.) Computational Logistics, pp. 437–451. Springer, Cham (2017)
Ahmed, S., Garcia, R., Kong, N., Ntaimo, L., Parija, G., Qiu, F., Sen, S.: SIPLIB: A stochastic integer programming test problem library (2015). http://www.isye.gatech.edu/sahmed/siplib
Rockafellar, R.T., Wets, R.J.-B.: Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1), 119–147 (1991)
Watson, J.-P., Woodruff, D.L.: Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems. CMS 8(4), 355–370 (2011)
Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2011)
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317, p. 733. Springer, Berlin (1998)
Burachik, R.S., Rubinov, A.: Abstract convexity and augmented Lagrangians. SIAM J. Optim. 18(2), 413–436 (2007)
Boland, N.L., Eberhard, A.C.: On the augmented Lagrangian dual for integer programming. Math. Program. 150(2, Ser. A), 491–509 (2015)
Feizollahi, M.J., Ahmed, S., Sun, A.: Exact augmented Lagrangian duality for mixed integer linear programming. Mathematical Programming, 1–23 (2016)
Oliveira, F., Christiansen, J., Dandurand, B., Eberhard, A.: Combining penalty-based and gauss-seidel methods for solving stochastic mixed-integer problems. Int. Trans. Operat. Res. 27(1), 494–524 (2018)
Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2), 95–110 (1956)
Boland, N., Christiansen, J., Dandurand, B., Eberhard, A., Linderoth, J., Luedtke, J., Oliveira, F.: Combining progressive hedging with a frank-wolfe method to compute Lagrangian dual bounds in stochastic mixed-integer programming. SIAM J. Optim. 28(2), 1312–1336 (2018)
Boland, N.L., Eberhard, A.C., Engineer, F., Tsoukalas, A.: A new approach to the feasibility pump in mixed integer programming. SIAM J. Optim. 22(3), 831–861 (2012)
Geißler, B., Morsi, A., Schewe, L., Schmidt, M.: Penalty alternating direction methods for mixed-integer optimization: a new view on feasibility pumps. SIAM J. Optim. 27(3), 1611–1636 (2017)
Tseng, P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109, 475–494 (2001)
Roshchina, V.: Exact calculus of fréchet subdifferentials for hadamard directionally differentiable functions. Nonlinear Anal. 69, 1112–1124 (2008)
Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Nashua, NH (1999)
Bonettini, S.: Inexact block coordinate descent methods with application to non-negative matrix factorization. IMA J. Numer. Anal. 31(4), 1431–1452 (2011)
Boland, N., Christiansen, J., Dandurand, B., Eberhard, A., Oliveira, F.: A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems. Math. Progr. 175, 503–536 (2018)
Beer, G. (1993) Topologies on closed and closed convex sets. mathematics and its applications, vol. 268, Kluwer Academic Publishers Group, Dordrecht , p. 340
IBM Corporation: IBM ILOG CPLEX V22.1. IBM Corporation. Last accessed 27 Jun 2022. https://www.ibm.com/docs/en/icos/22.1.0
COmputational INfrastructure for Operations Research. Last accessed 29 March, 2020. http://www.coin-or.org/
National Computing Infrastructure (NCI): NCI Website. National Computing Infrastructure (NCI). Last accessed 19 November 2016. http://www.nci.org.au
Bodur, M., Dash, S., Günlük, O., Luedtke, J.: Strengthened benders cuts for stochastic integer programs with continuous recourse. Technical Report RC25452, IBM Research Report, 2014. Available as Optimization Online 2014-03-4263 (2014)
Ntaimo, L., Sen, S.: The million-variable “march’’ for stochastic combinatorial optimization. J. Global Optim. 32(3), 385–400 (2005)
Ahmed, S., Garcia, R.: Dynamic capacity acquisition and assignment under uncertainty. Ann. Oper. Res. 124, 267–283 (2003)
Ahmed, S., Tawarmalani, M., Sahinidis, N.V.: A finite branch-and-bound algorithm for two-stage stochastic integer programs. Math. Program. 100(2(Ser. A)), 355–377 (2004)