×

Distributionally robust simple integer recourse. (English) Zbl 1483.90102

Summary: The simple integer recourse (SIR) function of a decision variable is the expectation of the integer round-up of the shortage/surplus between a random variable with a known distribution and the decision variable. It is the integer analogue of the simple (continuous) recourse function in two-stage stochastic linear programming. Structural properties and approximations of SIR functions have been extensively studied in the seminal works of van der Vlerk and coauthors. We study a distributionally robust SIR function (DR-SIR) that considers the worst-case expectation over a given family of distributions. Under the assumption that the distribution family is specified by its mean and support, we derive a closed form analytical expression for the DR-SIR function. We also show that this nonconvex DR-SIR function can be represented using a mixed-integer second-order conic program.

MSC:

90C15 Stochastic programming
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bayraksan G, Love DK (2015) Data-driven stochastic programming using phi-divergences. In: Tutorials in operations research, INFORMS, pp 1-19
[2] Delage, E.; Ye, Y., Distributionally robust optimization under moment uncertainty with application to data-driven problems, Oper Res, 58, 595-612, (2010) · Zbl 1228.90064 · doi:10.1287/opre.1090.0741
[3] Mohajerin Esfahani, Peyman; Kuhn, Daniel, Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations, Mathematical Programming, 171, 115-166, (2017) · Zbl 1433.90095 · doi:10.1007/s10107-017-1172-1
[4] Jiang, R.; Guan, Y., Data-driven chance constrained stochastic program, Math Program, 158, 291-327, (2016) · Zbl 1346.90640 · doi:10.1007/s10107-015-0929-7
[5] Haneveld, WKKlein; Stougie, L.; Vlerk, M., On the convex hull of the simple integer recourse objective function, Ann Oper Res, 56, 209-224, (1995) · Zbl 0835.90056 · doi:10.1007/BF02031708
[6] Haneveld, WKKlein; Stougie, L.; Vlerk, M., An algorithm for the construction of convex hulls in simple integer recourse programming, Ann Oper Res, 64, 67-81, (1996) · Zbl 0854.90110 · doi:10.1007/BF02187641
[7] Haneveld, WKKlein; Stougie, L.; Vlerk, M., Simple integer recourse models, Math Program Ser B, 108, 435-473, (2006) · Zbl 1130.90377 · doi:10.1007/s10107-006-0718-4
[8] Louveaux, FV; Vlerk, MH, Stochastic programming with simple integer recourse, Math Program, 61, 301-325, (1993) · Zbl 0792.90053 · doi:10.1007/BF01582153
[9] Popescu, I., Robust mean-covariance solutions for stochastic optimization, Oper Res, 55, 98-112, (2007) · Zbl 1167.90611 · doi:10.1287/opre.1060.0353
[10] Postek K, Ben-Tal A, Den Hertog D, Melenberg B (2015) Exact robust counterparts of ambiguous stochastic constraints under mean and dispersion information. Available at Optimization Online
[11] Romeijnders, W.; Morton, DP; Vlerk, MH, Assessing the quality of convex approximations for two-stage totally unimodular integer recourse models, INFORMS J. Comput., 29, 211-231, (2017) · Zbl 1371.90095 · doi:10.1287/ijoc.2016.0725
[12] Romeijnders, W.; Schultz, R.; Vlerk, MH; Haneveld, WKK, A convex approximation for two-stage mixed-integer recourse models with a uniform error bound, SIAM J Optim, 26, 426-447, (2016) · Zbl 1332.90185 · doi:10.1137/140986244
[13] Romeijnders, W.; Stougie, L.; Vlerk, MH, Approximation in two-stage stochastic integer programming, Surv Oper Res Manag Sci, 19, 17-33, (2014)
[14] Romeijnders, W.; Vlerk, MH; Haneveld, WKK, Convex approximations for totally unimodular integer recourse models: a uniform error bound, SIAM J Optim, 25, 130-158, (2015) · Zbl 1358.90088 · doi:10.1137/130945703
[15] Romeijnders, W.; Vlerk, MH; Haneveld, WKKlein, Total variation bounds on the expectation of periodic functions with applications to recourse approximations, Math Program, 157, 3-46, (2016) · Zbl 1353.90099 · doi:10.1007/s10107-014-0829-2
[16] Scarf, H.; Arrow, KJ (ed.); Karlin, S. (ed.); Scarf, HE (ed.), A min-max solution of an inventory problem, 201-209, (1958), Palo Alto
[17] Schultz, R.; Infanger, G. (ed.), Risk aversion in two-stage stochastic integer programming, 165-187, (2011), New York · Zbl 1246.90111
[18] Shapiro, Alexander, Distributionally Robust Stochastic Programming, SIAM Journal on Optimization, 27, 2258-2275, (2017) · Zbl 1373.90089 · doi:10.1137/16M1058297
[19] Shapiro, A.; Ahmed, S., On a class of minimax stochastic programs, SIAM J Optim, 14, 1237-1249, (2004) · Zbl 1073.90027 · doi:10.1137/S1052623403434012
[20] Shapiro A, Dentcheva D, Ruszczynski A (2014) Lectures on stochastic programming: modeling and theory, 2nd edn. SIAM Publishers, Philadelphia · Zbl 1302.90003
[21] Vlerk, MH, Convex approximations for a class of mixed-integer recourse models, Ann Oper Res, 177, 139-150, (2010) · Zbl 1201.90143 · doi:10.1007/s10479-009-0591-7
[22] Wiesemann, W.; Kuhn, D.; Sim, M., Distributionally robust convex optimization, Oper Res, 62, 1358-1376, (2014) · Zbl 1327.90158 · doi:10.1287/opre.2014.1314
[23] Xie, W.; Ahmed, S., On deterministic reformulations of distributionally robust joint chance constrained optimization problems, SIAM J Optim, 28, 1151-1182, (2018) · Zbl 1390.90412 · doi:10.1137/16M1094725
[24] Zackova, J., On minimax solutions of stochastic linear programming problems, Casopis pro pestovani matematiky, 091, 423-430, (1966) · Zbl 0161.17102
[25] Zymler, S.; Kuhn, D.; Rustem, B., Distributionally robust joint chance constraints with second-order moment information, Math Program, 137, 167-198, (2013) · Zbl 1286.90103 · doi:10.1007/s10107-011-0494-7
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.