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 :

Belgian Network DYSCO; FNRS-FRS

Available on ORBi :

since 08 November 2009

Statistics

Number of views

73 (18 by ULiège)

Number of downloads

165 (7 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

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)