Professor Humberto Bortolossi

Seminário de Otimização Estocástica 2006.1

2006.1

Parte das notas deste seminário foi usada para gerar o texto do minicurso “Uma Introdução à Otimização sob Incerteza” ministrado na III Bienal da Sociedade Brasileira de Matemática realizada na Universidade Federal de Goiás em novembro de 2006. Este texto está disponível como um arquivo PDF: iii-bienal-sbm-texto.pdf (674 Kb). As transparências do minicurso também estão disponíveis: iii-bienal-sbm-aula-1.pdf (1960 Kb), iii-bienal-sbm-aula-2.pdf (740 Kb), iii-bienal-sbm-aula-3.pdf (429 Kb) e iii-bienal-sbm-aula-4.pdf (1406 Kb).

 

JUNHO

13/06/2006

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.

10/06/2006

PRÓXIMOS SEMINÁRIOS

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.

09/06/2006

A ÁRVORE DE OTIMIZAÇÃO ESTOCÁSTICA EM 1998

08/06/2006

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.

06/06/2006
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.

01/06/2006

Métodos de amostragem 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.


MAIO

25/05/2006

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.

25/05/2006
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.

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

16/05/2006
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.

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

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

09/05/2006
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.

02/05/2006
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.


ABRIL

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

25/04/2006
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.

20/04/2006
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.

18/04/2006
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.

11/04/2006
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.

06/04/2006
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.

04/04/2006
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.


MARÇO

30/03/2006

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.

28/03/2006
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.

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

21/03/2006
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).

16/03/2006
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.

14/03/2006
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.

06/03/2006

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.