×

Analyzing the quality of the expected value solution in stochastic programming. (English) Zbl 1254.90142

Summary: Stochastic programs are usually hard to solve when applied to real-world problems; a common approach is to consider the simpler deterministic program in which random parameters are replaced by their expected values, with a loss in terms of quality of the solution. The value of the stochastic solution – VSS – is normally used to measure the importance of using a stochastic model. But what if VSS is large, or expected to be large, but we cannot solve the relevant stochastic program? Shall we just give up? In this paper we investigate very simple methods for studying structural similarities and differences between the stochastic solution and its deterministic counterpart. The aim of the methods is to find out, even when VSS is large, if the deterministic solution carries useful information for the stochastic case. It turns out that a large VSS does not necessarily imply that the deterministic solution is useless for the stochastic setting. Measures of the structure and upgradeability of the deterministic solution such as the loss using the skeleton solution and the loss of upgrading the deterministic solution will be introduced and basic inequalities in relation to the standard VSS are presented and tested on different cases.

MSC:

90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ariyawansa, K. A., & Zhu, Y. (2010, under review). A preliminary set of applications leading to stochastic semidefinite programs and chance-constrained semidefinite programs. Mathematical and Computer Modeling. Technical Report No. 8, Department of Mathematics, Washington State University. · Zbl 1217.90140
[2] Birge, J. R. (1982). The value of the stochastic solution in stochastic linear programs with fixed recourse. Mathematical Programming, 24, 314–325. · Zbl 0502.90065 · doi:10.1007/BF01585113
[3] Birge, J. R., & Louveaux, F. (1997). Introduction to stochastic programming. New York: Springer. · Zbl 0892.90142
[4] Garver, L. L. (1963). Power generation scheduling by integer programming-Development of Theory. IEEE Transactions on Power Apparatus and Systems, 81, 730–735.
[5] Higle, J. L., & Wallace, S. W. (2003). Sensitivity analysis and uncertainty in linear programming. Interfaces INFORMS, 33(4), 53–60. · doi:10.1287/inte.33.4.53.16370
[6] Kall, P., & Wallace, S. W. (1994). Stochastic programming. Chichester: Wiley. · Zbl 0812.90122
[7] Ko, Y.-B., & Vaidya, N. H. (2000). Location-Aided Routing (LAR) in mobile ad hoc networks. Wireless Network, 6(4), 307–321. · Zbl 1120.68317 · doi:10.1023/A:1019106118419
[8] Maggioni, F., Potra, F., Bertocchi, M., & Allevi, E. (2009). Stochastic second-order cone programming in mobile ad hoc networks. Journal of Optimization, Theory and Applications, 143, 309–328. · Zbl 1177.90396 · doi:10.1007/s10957-009-9561-0
[9] Maggioni, F., Wallace, S. W., Bertocchi, M., & Allevi, E. (2010). Sensitivity analysis in stochastic second-order cone programming for mobile ad hoc networks. Procedia Social and Behavioral Sciences, 2, 7704–7705. · doi:10.1016/j.sbspro.2010.05.188
[10] Maggioni, F., Kaut, M., & Bertazzi, L. (2009). Stochastic optimization models for a single-sink transportation problem. Computational Management Science, 6, 251–267. · Zbl 1170.90325 · doi:10.1007/s10287-008-0086-z
[11] Prékopa, A. (1995). Stochastic programming. Dordrecht: Kluwer Academic. · Zbl 0834.90098
[12] Wallace, S. W. (2000). Decision making under uncertainty: is sensitivity analysis of any use? Operation Research, 48(1), 20–25. · doi:10.1287/opre.48.1.20.12441
[13] Williams, H. P. (1985). Model building in mathematical programming. New York: Wiley. ISBN 0-471-99788-9. · Zbl 0558.90064
[14] Thapalia, B. K., Wallace, S. W., Kaut, M., & Crainic, T. G. (2010, to appear). Single source single-commodity stochastic network design. In Stochastic single-commodity network design; Biju K. Thapalia, Molde University College, PhD thesis 2010:2, pp. 33–55. · Zbl 1273.90036
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.