Abstract
Infrastructure-planning models are challenging because of their combination of different time scales: while planning and building the infrastructure involves strategic decisions with time horizons of many years, one needs an operational time scale to get a proper picture of the infrastructure’s performance and profitability. In addition, both the strategic and operational levels are typically subject to significant uncertainty, which has to be taken into account. This combination of uncertainties on two different time scales creates problems for the traditional multistage stochastic-programming formulation of the problem due to the exponential growth in model size. In this paper, we present an alternative formulation of the problem that combines the two time scales, using what we call a multi-horizon approach, and illustrate it on a stylized optimization model. We show that the new approach drastically reduces the model size compared to the traditional formulation and present two real-life applications from energy planning.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Actually, \(y_\mathrm{Pa (n)}\) in the root node represents the currently installed capacity—which we assume to be zero.
The PVWatts™ calculator was developed by the National Renewable Energy Laboratory and is available from http://www.nrel.gov/rredc/pvwatts/.
References
Christiansen DS, Wallace SW (1998) Option theory and modeling under uncertainty. Ann Oper Res 82: 59–82
De Jonghe C, Hobbs B, Belmans R (2011) Integrating short-term demand response into long-term investment planning, Cambridge working papers in economics, vol 1132. Faculty of Economics, University of Cambridge, Cambridge
Dupačová J, Consigli G, Wallace SW (2000) Scenarios for multistage stochastic programs. Ann Oper Res 100:25–53
Fleten S-E, Jørgensen T, Wallace SW (1998) Real options and managerial flexibility. Telektronikk 94(3/4):62–66
Groissböck M, Stadler M, Edlinger T, Siddiqui A, Heydari S, Perea E (2011) The first step for implementing a stochastic based energy management system at campus Pinkafeld. Technical Report C-2011-1, Center for Energy and innovative Technologies, Hofamt Priel, Austria
Hellemo L, Midthun K, Tomasgard A, Werner A (2013) Multi-stage stochastic programming for natural gas infrastructure design with a production perspective. In: Gassmann, HI, Wallace, SW, Ziemba, WT (eds) Stochastic programming: applications in finance, energy, planning and logistics, World Scientific Series in Finance. World Scientific, Singapore
Høyland K, Wallace SW (2001) Generating scenario trees for multistage decision problems. Manag Sci 47(2):295–307
King AJ, Wallace SW, Lium A-G, Crainic TG (2012) Service network design, chapter 5, Springer series in operations research and financial engineering. Springer. doi:10.1007/978-0-387-87817-1_5
Lium A-G, Crainic TG, Wallace SW (2009) A study of demand stochasticity in stochastic network design. Transport Sci 43(2):144–157. doi:10.1287/trsc.1090.0265
Midthun KT (2007) Optimization models for liberalized natural gas markets. PhD thesis, Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, Trondheim, Norway
Midthun KT, Bjørndal M, Tomasgard A (2009) Modeling optimal economic dispatch and system effects in natural gas networks. Energy J 30:155–180
Myklebust J (2010) Techno-economic modelling of value chains based on natural gas—with consideration of CO2 emissions. PhD thesis, Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology
Pérez-Valdés G, Kaut M, Nørstebø V, Midthun K (2012) Stochastic MIP modeling of a natural gas-powered industrial park. Energy Procedia 26:74–81. doi:10.1016/j.egypro.2012.06.012. Proceedings of the 2nd Trondheim Gas Technology Conference
Römisch W (2009) Scenario reduction techniques in stochastic programming. In: Stochastic Algorithms: Foundations and Applications. Lecture Notes in Computer Science, vol 5792, pp 1–14. Springer, Berlin
Schütz P, Tomasgard A, Ahmed S (2009) Supply chain design under uncertainty using sample average approximation and dual decomposition. Eur J Oper Res 199(2):409–419. doi:10.1016/j.ejor.2008.11.040
Singh KJ, Philpott AB, Wood RK (2009) Dantzig-Wolfe decomposition for solving multistage stochastic capacity-planning problems. Oper Res 57(5):1271–1286. doi:10.1287/opre.1080.0678
Sönmez E, Kekre S, Scheller-Wolf A, Secomandi N (2013) Strategic analysis of technology and capacity investments in the liquefied natural gas industry. Eur J Oper Res 226(1):100–114. doi:10.1016/j.ejor.2012.10.042
Thapalia BK, Crainic TG, Kaut M, Wallace SW (2012) Single-commodity network design with random edge capacities. Eur J Oper Res 220(2):394–403. doi:10.1016/j.ejor.2012.01.026
Thapalia BK, Crainic TG, Kaut M, Wallace SW (2012b) Single source single-commodity stochastic network design. Comput Manag Sci 9(1):139–160. doi:10.1007/s10287-010-0129-0. Special issue on ‘Optimal decision making under uncertainty’
Acknowledgments
The research presented in this paper has been supported by the project ‘Energy Efficiency and Risk Management in Public Buildings’ (EnRiMa), funded by the European Commission via the 7th Framework Programme (FP7), project number 260041. Part of the presented work also builds on research performed in the Ramona project (The Research Council of Norway, project number 175967) on production assurance and security of supply for natural gas transport.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kaut, M., Midthun, K.T., Werner, A.S. et al. Multi-horizon stochastic programming. Comput Manag Sci 11, 179–193 (2014). https://doi.org/10.1007/s10287-013-0182-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10287-013-0182-6