Decomposição estocástica. Stochastic Cutting Plane. Resultados de convergência. Exemplo.

Referências:

J.L. Higle e S. Sen. Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming (Nonconvex Optimization and Its Applications), Springer-Verlag, 1996.

Débora:

David P. Morton e Javier Salmerón. A Stochastic Program for Optimizing Military Sealfit Subject to Attack (177 Kb), Workshop on Decision-Making Under Uncertainty, Norway, 2001.

Eduardo:

Shabbir Ahmed. Convexity and Decomposition of Mean-Risk Stochastic Programs (183 Kb), Mathematical Progamming, vol. 106, pp. 433-446, 2006.

Jéssica:

Petri Hilli, Matti Koivu, Teemu Pennanen e Antero Ranne. A Stochastic Programming Model for Asset Liability Management of a Finnish Pension Company (518 Kb), Annals of Operations Research (to appear).

Marina:

M. I. Kusy e W. T. Ziemba. A Bank Asset and Liability Management Model (3644 Kb), Operations Research, vol. 34, no. 3, pp. 356-376, 1986.

Rafael:

M. Pereira, N. Campodónico e R.Kelman. Application of Stochastic Dual DP and Extensions to Hydrothermal Scheduling (136 Kb), PSRI Technical Report 012/99, 1999.

Decomposição estocástica. O método de Kelley (cutting plane). Otimização sucessiva da média amostral. Estudo de convergência.

Referências:

J.L. Higle e S. Sen. Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming (Nonconvex Optimization and Its Applications), Springer-Verlag, 1996.

Método da média amostral (SAA). Estimadores para cota inferior, cota superior e GAP. Testes de otimalidade.

Referências:

Anton J. Kleywegt, Alexander Shaprio e Tito Homem-de-Melo. The Sample Average Approximation Method for Stochastic Discrete Optimization (247 Kb), SIAM Journal on Optimization, vol. 12, no. 2, pp. 479-502, 2001. University of Wisconsin-Madison, 2002.

Jeff Linderoth, Alexander Shapiro e Stephen Wright. The Empirical Behavior of Sampling Methods for Stochastic Programming (341 Kb), Optimization Technick Report 02-01, Computer Sciences Department, University of Wisconsin-Madison, 2002.

Andrzej Ruszczynski e Alexander Shapiro. Stochastic Programming (Hanbooks in Operations Research and Management Series), Elsevier Publishing Company, 2003.

Alexander Shapiro e Tito Homem-de-Mello. A Simulation-Based Approach to Two-Stage Stochastic Programming with Recourse (1288 Kb), Mathematical Programming, vol. 81, pp. 301-325, 1998.

Alexander Shapiro, Tito Homem-de-Mello e Joocheol Kim. Conditioning of Convex Piecewise Linear Stochastic Programs (150 Kb), Mathematical Programming, Series A, vol. 94, pp. 1-19, 2002.

Métodos de amonstragem interior e exterior. Revisão de probabilidade e estatística: desigualdade de Chebyshev, a lei fraca dos grandes números, a lei forte dos grandes números, o teorema central do limite, a fórmula de aproximação normal, estimadores não visados, intervalos de confiança.

Os métodos L-shaped clássico e multicut.

Referências:

John R. Birge. Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs (1775 Kb), Operations Research, vol. 33, no. 5, pp. 989-1007, 1985.

John R. Birge e Roger J.-B. Wets. Designing Approximation Schemes for Stochastic Optimization Problems, in Particular for Stochastic Programs with Recourse (520 Kb), Mathematical Programming Study, vol. 27, pp. 54-102, 1986.

M. A. H. Dempster e R. T. Thompson. EVPI-based Importance Sampling Solution Procedures for Multistage Stochastic Linear Programmes on Parallel MIMD Archiectures (321 Kb), Annals of Operations Research, vol. 90, pp. 161-184, 1999.

N. C. P. Edirisinghe e W. T. Ziemba. Implementing Bounds-Based Approximations in Convex-Concave Two-Stage Stochastic Programming (382 Kb), Mathematical Programming, vol. 75, pp. 295-325, 1996.

Peter Kall. Approximations to Stochastic Programs with Complete Fixed Recourse (100 Kb), Numerische Mathematik, vol. 22, pp. 333-339, 1974.

R. M. van Slyke e R. J.-B. Wets. L-Shaped Linear Programs with Applications to Optimial Control and Stochastic Programming (336 Kb), SIAM J. Appl. Math., vol. 17, no. 4, pp. 638-663, 1969.

Pontos e raios extremos. O teorema de resolução de Minkowski. O método de decomposição de Benders: o modelo básico.

Referências:

J. F. Benders. Partitioning Procedures for Solving Mixed-Variables Programming Problems (387 Kb), Numerische Mathematik, vol. 4, pp. 238-252, 1962.

A. M. Geoffrion. Generalized Benders Decomposition (307 Kb), Journal of Optimization and Applications, vol. 10, no. 4, pp. 237-260, 1972.

Um exemplo multi-estágio: planejamento financeiro (levando Jacob ao MIT).

Uma demonstração do lema de Farkas a partir do teorema de separação para conjuntos convexos. Usando o lema de Farkas para caracterizar estruturas de recursos completas e estruturas não extremamente baratas.

Um algoritmo numérico para SLPwR com recurso simples, ditribuição contínua e h(ω) = ω. Exemplo.

Um algoritmo numérico para SLPwR com recurso simples, ditribuição discreta e h(ω) = ω.

A desigualdade de Edmudson-Madansky no caso n-dimensional e a interpolação polinomial lagrangeana. A importância da independência: exemplo. Revisão de probabilidade condicional. Obtendo cotas mais refinadas via partição.

O tamanho da forma extensa de SLPwR. Cotas para a função de recurso: as desigualdades de Jensen e Edmudson-Madansky. Interpretação em termos de distribuições. Exemplo.

Referências:

John R. Birge e Roger J.-B. Wets. Computing Bounds for Stochastic Programming Problems by Means of a Generalized Moment Problem (205 Kb), Mathematics of Operations Research, vol. 12, no. 1, pp. 149-162, 1987.

N. C. P. Edirisinghe e W. T. Ziemba. Bounds for Two-Stage Stochastic Programs with Fixed Recourse (320 Kb), Mathematics of Operations Research, vol. 19, no. 2, pp. 292-313, 1994.

Albert Madansky. Inequalities for Stochastic Linear Programming Problems (696 Kb), Management Science, vol. 6, no. 2, pp. 197-204, 1960.

O. L. Mangasarian e J. B. Rosen. Inequalities for Stochastic Linear Programming Problems (1125 Kb), Operations Research, vol. 12, no.1, pp. 143-154, 1964.

Estruturas com recurso simples: funções de déficit, funções de excesso e suas propriedades.

O teorema da dualidade em programação linear. Propriedades da função de recurso no caso de estruturas com recurso fixo e distribuições discretas: finitude, linearidade por partes, diferenciabilidade qtp.

Estruturas de recurso relativamente completas, completas, extremamente baratas e simples.

Referências:

R. T. Rockafellar e R. J.-B. Wets. Stochastic Convex Programming: Relatively Complete Recourse and Induced Feasibility (196 Kb), SIAM J. Control and Optimization, vol. 14, no. 3, pp. 574-589, 1976.

Roger J.-B. Wets. Stochastic Programs with Fixed Recourse: The Equivalent Deterministic Program (511 Kb), SIAM Review, vol. 16, no. 3, pp. 309-339, 1974.

Admissibilidade no caso de recurso fixo: lema de Farkas, cone polar, matriz polar.

Referências:

Achiya Dax. An Elementary Proof of Farkas' Lemma (56 Kb), SIAM Review, vol. 39, no. 3, pp. 503-507, 1997.

Capítulo 3 de Peter Kall e Stein W. Wallace. Stochastic Programming (1411 Kb), John Willey & Sons, 1994.

Paul Olsen When is a Multistage Stochastic Programming Well-Defined? (160 Kb), SIAM J. Control and Optimization, vol. 14, no.3, pp. 518-527, 1976.

R. J.-B. Wets e Christoph Witzgall Toward an Algebraic Characterization of Convex Polyhedral Cones (124 Kb), Numerische Mathematik, vol. 12, pp. 134-138, 1968.

Problemas de recurso com dois estágios: admissibilidade.

Referências:

David W. Walkup e Roger J.-B. Wets. Stochastic Programs with Recourse (819 Kb), SIAM Journal of Applied Mathematics, vol. 15, no. 5, pp. 1299-1314, 1967.

David W. Walkup e Roger J.-B. Wets. Stochastic Programs with Recourse II: On the Continuity of the Objective (151 Kb), SIAM Journal of Applied Mathematics, vol. 17, no. 1, pp. 98-103, 1969.

R. J.-B. Wets. Programming Under Uncertainty: The Equivalent Convex Program (272 Kb), SIAM Journal of Applied Mathematics, vol. 14, no. 1, pp. 89-105, 1966.

R. J.-B. Wets. Programming Under Uncertainty: The Solution Set (134 Kb), SIAM Journal of Applied Mathematics, vol. 14, no. 5, pp. 1143-1151, 1966.

Equivalência entre a forma extensa e a forma em dois estágios de programas estocásticos. O problema de localização simples: as escolhas das variáveis de primeiro e segundo estágios dependem do contexto.

Referências:

Janny M.Y. Leung e Thomas L. Magnanti. Valid Inequalities and Facets of the Capacitated Plant Location Problem (2.5 Mb), MIT, OR 149-86, 1986.

J. Kraru e P.M. Pruzan. The Simple Plant Location Problem: Survey and Synthesis. European Journal of Operations Research, vol. 12, pp. 36-81, 1983.

P. B. Mirchandani e R. L. Francis. Discrete Location Theory. John Wiley & Sons, 1990.

M. S. Daskin. Network and Discrete Location: Models, Algorithms and Applications. John Wiley & Sons, Inc., 1995.

Um exemplo (case study) de programação estocástica com dois estágios: planejando os custos de enfermagem em um hospital. O problema do caixeiro-viajante estocástisco.

Artigos:

Edward P. C. Kao e Maurice Queyranne. Budgeting Costs of Nursing in a Hospital (770 Kb), Management Science, vol. 31, no. 5, 1985.

Patrick Jaillet. A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers are Visited (489 Kb), Operations Research, vol. 36, no. 6, pp. 929-936, 1988.

Dimitris J. Bertsimas, Patrick Jaillet e Amedeo R. Odoni. A Priori Optimization (1 Mb), Operations Research, vol. 38, no. 6, pp. 1019-1033, 1990.

Revisitando o problema do fazendeiro: O problema é para um estágio ou para estágios? O que aconteceria se o fazendeiro pudesse mudar a divisão da terra em cada estágio? Abordagens via teoria dos jogos [transparências em http://www.professores.uff.br/hjbortol/arquivo/2005.2/sbpc/sbpc.pdf (1583 Kb)] e o princípio de otimalidade de Bellman.

Motivação para problemas de otimização estocástica com modelos de recurso em dois estágios: “goal programming”, “hard constraints”, “soft constraints”, funções de penalidade, estrutura de recurso, matriz de tecnologia, funções de penalidade via estruturas de recurso.

Revisão da teoria de convexidade: conjuntos convexos, funções convexas, convexidade implica em continuidade absoluta, epigrafos, unimodalidade.

O problema da mistura e o problema da produção, abordagens “Wait and See” e “Here and Now”: eliminar incertezas, incorporar riscos nas restrições “(chance constraints)”, aceitar inadmissibilidade penalizando déficits esperados.

Arquivos AMPL para os exercícios 1 a 5 (variantes do problema do fazendeiro) na página 18 de [BL]: ampl-hjb-fazendeiro.zip (10 Kb).

Planilha Maple para o exercício 7 (incorporando riscos ao problema do fazendeiro) na página 19 de [BL]: bl-c01-s01-e07.zip (7 Kb).

Planilha Maple com um exemplo onde VSS é maior do que EVPI (o exemplo 1 página 144 de [BL]): vss-gt-evpi.zip (4 Kb).

O problema do fazendeiro com variáveis aleatórias contínuas, o problema do jornaleiro (newsvendor problem).

Artigos:

Martin A. Koschat, Glorian L. Berk, Jeffrey A. Blatt, Nancy M. Kunz e Michael H. LePore. Newsvendors Tackle the Newsvendor Problem (151 Kb), Interfaces, Vol. 33, No. 3, May–June 2003.

Gary E Bolton e Elena Katok. Learning-by-Doing in the Newsvendor Problem A Laboratory Investigation of the Role of Experience and Feedback (276 Kb), Smeal College of Business, Penn State University, 2004.

David E. Bell. Incorporating the Customer’s Perspective into the Newsvendor Problem (50 Kb), Graduate School of Business Administration, Harvard University, 2001.

Nicholas C. Petruzzi e Maqbool Dada. Pricing and The Newsvendor Problem: A Review with Extensions (1079 Kb), Operations Research, vol. 47, no.2, pp. 183-194, 1999.

Exemplo: o problema do fazendeiro, a forma extensa de um problema de otimização estocástica, EVPI, VSS.

Referências:

M. Avriel e A. C. Williams. The Value of Information and Stochastic Programming (735 Kb), Operations Research, vol. 18, no. 5, pp. 947-954, 1970.

C. C. Huang, I. Vertinsky e W. T. Ziemba. Sharp Bounds on the Value of Perfect Information (1200 Kb), Operations Research, vol. 25, no. 1, pp. 128-139, 1977.

Referências:

[BL]	John R. Birge e François Louveaux. Introduction to Stochastic Programming. Springer Series in Operations Research, New York, NY, 1997.
[HV]	Willem K. Klein Haneveld e Maarten H. van der Vlerk. Stochastic Programming. Department of Econometrics & OR, University of Groningen, 2004.

Notas de aula: Jeff Linderoth, Peter Kall, Maarten H. van der Vlerk e John E. Mitchell.

WEB page: Stochastic Programming Community Home Page.