×

Variable neighborhood search for a two-stage stochastic programming problem with a quantile criterion. (English. Russian original) Zbl 1437.90113

Autom. Remote Control 80, No. 1, 43-52 (2019); translation from Avtom. Telemekh. 2019, No. 1, 54-66 (2019).
Summary: We consider a two-stage stochastic programming problem with a bilinear loss function and a quantile criterion. The problem is reduced to a single-stage stochastic programming problem with a quantile criterion. We use the method of sample approximations. The resulting approximating problem is considered as a stochastic programming problem with a discrete distribution of random parameters. We check convergence conditions for the sequence of solutions of approximating problems. Using the confidence method, the problem is reduced to a combinatorial optimization problem where the confidence set represents an optimization strategy. To search for the optimal confidence set, we adapt the variable neighborhood search method. To solve the problem, we develop a hybrid algorithm based on the method of sample approximations, the confidence method, variable neighborhood search.

MSC:

90C15 Stochastic programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Birge, J. and Louveaux, F., Introduction to Stochastic Programming, New York: Springer-Verlag, 1997. · Zbl 0892.90142
[2] Shapiro, A., Dentcheva, D., and Ruszczyński, A., Lectures on Stochastic Programming, Philadelphia: Society for Industrial and Applied Mathematics (SIAM), 2009. · Zbl 1183.90005 · doi:10.1137/1.9780898718751
[3] Beraldi, P. and Ruszczyński, A., A Branch and Bound Method for Stochastic Integer Problems under Probabilistic Constraints, Optim. Method. Software, 2002, vol. 17, no. 3, pp. 359-382. · Zbl 1064.90030 · doi:10.1080/1055678021000033937
[4] Kibzun, A.I. and Kan, Y.S., Stochastic Programming Problems with Probability and Quantile Functions, Chichester: Wiley, 1996. · Zbl 0885.90088
[5] Kibzun, A.I., Comparison of Two Algorithms for Solving a Two-Stage Bilinear Stochastic Programming Problem with Quantile Criterion, Appl. Stoch. Model. Business Industry, 2015, vol. 31, no. 6, pp. 862-874. · Zbl 1406.90085 · doi:10.1002/asmb.2115
[6] Artstein, Z. and Wets, R.J.-B., Consistency of Minimizers and the SLLN for Stochastic Programs, J. Convex Anal., 1996, vol. 2, pp. 1-17. · Zbl 0837.90093
[7] Pagnoncelli, B.K., Ahmed, S., and Shapiro, A., Sample Average ApproximationMethod for Chance Constrained Programming: Theory and Applications, J. Optim. Theory Appl., 2009, vol. 142, pp. 399-416. · Zbl 1175.90306 · doi:10.1007/s10957-009-9523-6
[8] Ivanov, S.V. and Kibzun, A.I., On the Convergence of Sample Approximations for Stochastic Programming Problems with Probabilistic Criteria, Autom. Remote Control, 2018, vol. 79, no. 2, pp. 216-228. · Zbl 1391.90443 · doi:10.1134/S0005117918020029
[9] Ivanov, S.V. and Kibzun, A.I., Sample Average Approximation in the Two-Stage Stochastic Linear Programming Problem with Quantile Criterion, Tr. Inst. Mat. Mekh. UrO RAN, 2017, vol. 23, no. 3, pp. 134-143.
[10] Guigues, V., Juditsky, A., and Nemirovski, A., Non-Asymptotic Confidence Bounds for the Optimal Value of a Stochastic Program, Optim. Method. Software, 2017, vol. 32, no. 5, pp. 1033-1058. · Zbl 1386.90091 · doi:10.1080/10556788.2017.1350177
[11] Lepp, R., Approximate Solution of Stochastic Programming Problems with Recourse, Kybernetika, 1987, vol. 23, no. 6, pp. 476-482. · Zbl 0637.90071
[12] Lepp, R., Approximation of the Quantile Minimization Problem with Decision Rules, Optim. Method. Software, 2002, vol. 17, no. 3, pp. 505-522. · Zbl 1064.90031 · doi:10.1080/1055678021000033991
[13] Benati, S. and Rizzi, R., A Mixed Integer Linear Programming Formulation of the Optimal Mean/Valueat-Risk Portfolio Problem, Eur. J. Oper. Res., 2007, vol. 176, no. 1, pp. 423-434. · Zbl 1137.91426 · doi:10.1016/j.ejor.2005.07.020
[14] Norkin, V.I., Kibzun, A.I., and Naumov, A.V., Reducing Two-Stage Probabilistic Optimization Problems with Discrete Distribution of Random Data to Mixed-Integer Programming Problems, Cybernet. Syst. Anal., 2014, vol. 50, no. 5, pp. 679-692. · Zbl 1308.90117 · doi:10.1007/s10559-014-9658-9
[15] Ruszczyński, A., Probabilistic Programming with Discrete Distributions and Precedence Constrained Knapsack Polyhedra, Math. Program., 2002, vol. 93, pp. 195-215. · Zbl 1065.90058 · doi:10.1007/s10107-002-0337-7
[16] Mladenović, N. and Hansen, P., Variable Neighborhood Search, Comput. Oper. Res., 1997, vol. 24, no. 11, pp. 1097-1100. · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[17] Hansen, P., Mladenović, N., and Pérez, J.A.M., Variable Neighbourhood Search: Methods and Applications, Ann. Oper. Res., 2010, vol. 175, no. 1, pp. 367-407. · Zbl 1185.90211 · doi:10.1007/s10479-009-0657-6
[18] Hansen, P. and Mladenović, N., Variable Neighborhood Search, in Handbook of Heuristics, Mart´ı, R., Pardalos, P., and Resende, M., Eds., Cham: Springer, 2016. · Zbl 0889.90119
[19] Hansen, P., Mladenović, N., Todosijević, R., and Hanafi, S., Variable Neighborhood Search: Basics and Variants, EURO J. Comput. Optim., 2017, vol. 5, no. 5, pp. 423-454. · Zbl 1390.90586 · doi:10.1007/s13675-016-0075-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.