Bounds for Multistage Stochastic Programs using Supervised Learning Strategies

Defourny, Boris; Ernst, Damien; Wehenkel, Louis

doi:10.1007/978-3-642-04944-6_6

Download

Paper published in a book (Scientific congresses and symposiums)

Bounds for Multistage Stochastic Programs using Supervised Learning Strategies

Defourny, Boris; Ernst, Damien; Wehenkel, Louis

2009 • In Watanabe, Osamu; Zeugmann, Thomas (Eds.) Stochastic Algorithms: Foundations and Applications

Peer reviewed

Permalink
https://hdl.handle.net/2268/27715

DOI
10.1007/978-3-642-04944-6_6

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

saga09_MSPLearning_preprint.pdf

Author preprint (187.48 kB)

Download

The original publication is available at www.springerlink.com .

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Stochastic Programming; Supervised Learning

Abstract :

[en] We propose a generic method for obtaining quickly good upper bounds on the minimal value of a multistage stochastic program. The method is based on the simulation of a feasible decision policy, synthesized by a strategy relying on any scenario tree approximation from stochastic programming and on supervised learning techniques from machine learning.

Disciplines :

Computer science

Author, co-author :

Defourny, Boris ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore)

Ernst, Damien ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation

Wehenkel, Louis ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation

Language :

English

Title :

Bounds for Multistage Stochastic Programs using Supervised Learning Strategies

Publication date :

2009

Event name :

Stochastic Algorithms: Foundations and Applications. Fifth International Symposium, SAGA 2009

Event organizer :

Hokkaido University

Event place :

Sapporo, Japan

Event date :

October 26-28, 2009

Audience :

International

Main work title :

Stochastic Algorithms: Foundations and Applications

Editor :

Watanabe, Osamu

Zeugmann, Thomas

Publisher :

Springer

ISBN/EAN :

9783642049439

Collection name :

Lecture Notes in Computer Sciences; 5792

Pages :

61-73

Peer reviewed :

Peer reviewed

Additional URL :

http://www.springerlink.com/content/1700016r11964778

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique

Funding text :

This paper presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office.

Available on ORBi :

since 08 November 2009

Statistics

Number of views

90 (18 by ULiège)

Number of downloads

187 (8 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Frauendorfer, K.: Barycentric scenario trees in convex multistage stochastic programming. Mathematical Programming 75, 277-294 (1996)
Dempster, M.: Sequential importance sampling algorithms for dynamic stochastic programming. Annals of Operations Research 84, 153-184 (1998)
Dupacova, J., Consigli, G., Wallace, S.: Scenarios for multistage stochastic programs. Annals of Operations Research 100, 25-53 (2000)
Høyland, K., Wallace, S.: Generating scenario trees for multistage decision problems. Management Science 47(2), 295-307 (2001)
Shapiro, A.: Monte Carlo sampling methods. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10, pp. 353-425. Elsevier, Amsterdam (2003)
Casey, M., Sen, S.: The scenario generation algorithm for multistage stochastic linear programming. Mathematics of Operations Research 30, 615-631 (2005)
Hochreiter, R., Pflug, G.: Financial scenario generation for stochastic multistage decision processes as facility location problems. Annals of Operations Research 152, 257-272 (2007)
Pennanen, T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Mathematical Programming 116, 461-479 (2009)
Heitsch, H., Römisch, W.: Scenario tree modeling for multistage stochastic programs. Mathematical Programming 118(2), 371-406 (2009)
Shapiro, A.: On complexity of multistage stochastic programs. Operations Research Letters 34(1), 1-8 (2006)
Shapiro, A.: Inference of statistical bounds for multistage stochastic programming problems. Mathematical Methods of Operations Research 58(1), 57-68 (2003)
Golub, B., Holmer, M., McKendall, R., Pohlman, L., Zenios, S.: A stochastic programming model for money management. European Journal of Operational Research 85, 282-296 (1995)
Kouwenberg, R.: Scenario generation and stochastic programming models for asset liability management. European Journal of Operational Research 134, 279-292 (2001)
Hilli, P., Pennanen, T.: Numerical study of discretizations of multistage stochastic programs. Kybernetika 44, 185-204 (2008)
Billingsley, P.: Probability and Measure, 3rd edn. Wiley, Chichester (1995)
Vapnik, V.: Statistical Learning Theory. Wiley, Chichester (1998)
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd edn. Springer, Heidelberg (2009)
Wahba, G., Golub, G., Heath, M.: Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21, 215-223 (1979)
Efron, B., Tibshirani, R.: An introduction to the bootstrap. Chapman and Hall, London (1993)
Thénié, J., Vial, J.P.: Step decision rules for multistage stochastic programming: A heuristic approach. Automatica 44, 1569-1584 (2008)
Küchler, C., Vigerske, S.: Numerical evaluation of approximation methods in stochastic programming (2008) (submitted)
Cover, T.: Estimation by the nearest neighbor rule. IEEE Transactions on Information Theory 14, 50-55 (1968)
Akaike, H.: Information theory and an extension of the maximum likelihood principle. In: Proceedings of the Second International Symposium on Information Theory, pp. 267-281 (1973)
Schwartz, G.: Estimating the dimension of a model. Annals of Statistics 6, 461-464 (1978)
Rissanen, J.: Stochastic complexity and modeling. Annals of Statistics 14, 1080-1100 (1986)
James, G., Radchenko, P., Lv, J.: DASSO: connections between the Dantzig selector and Lasso. Journal of the Royal Statistical Society: Series B 71, 127-142 (2009)
Chapelle, O., Vapnik, V., Bengio, Y.: Model selection for small sample regression. Machine Learning 48, 315-333 (2002)
Huber, P.: Projection pursuit. Annals of Statistics 13, 435-475 (1985)
Buja, A., Hastie, T., Tibshirani, R.: Linear smoothers and additive models. Annals of Statistics 17, 453-510 (1989)
Friedman, J.: Multivariate adaptive regression splines (with discussion). Annals of Statistics 19, 1-141 (1991)
Girosi, F., Jones, M., Poggio, T.: Regularization theory and neural networks architectures. Neural Computation 7, 219-269 (1995)
Williams, C., Rasmussen, C.: Gaussian processes for regression. In: Advances in Neural Information Processing Systems 8 (NIPS 1995), pp. 514-520 (1996)
Smola, A., Schölkopf, B., Müller, K.R.: The connection between regularization operators and support vector kernels. Neural Networks 11, 637-649 (1998) (Pubitemid 28400264)
Puterman,M.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, Chichester (1994)
Bertsekas, D., Tsitsiklis, J.: Neuro-Dynamic Programming. Athena Scientific, Belmont (1996)
Sutton, R., Barto, A.: Reinforcement Learning, an introduction. MIT Press, Cambridge (1998)
Bagnell, D., Kakade, S., Ng, A., Schneider, J.: Policy search by dynamic programming. In: Advances in Neural Information Processing Systems 16 (NIPS 2003), pp. 831-838 (2004)
Lagoudakis, M., Parr, R.: Reinforcement learning as classification: leveraging modern classifiers. In: Proceedings of the Twentieth International Conference on Machine Learning (ICML 2003), pp. 424-431 (2003)
Ernst, D., Geurts, P., Wehenkel, L.: Tree-based batch mode reinforcement learning. Journal of Machine Learning Research 6, 503-556 (2005)
Langford, J., Zadrozny, B.: Relating reinforcement learning performance to classification performance. In: Proceedings of the Twenty-Second International Conference on Machine Learning (ICML 2005), pp. 473-480 (2005)
Fern, A., Yoon, S., Givan, R.: Approximate policy iteration with a policy language bias: solving relational Markov Decision Processes. Journal of Artificial Intelligence Research 25, 85-118 (2006)