Optimering under osäkerhet

TMA136/MAM350, lp1, ht 2001, 5p

Kursansvariga

Ann-Brith Strömberg (föreläsare/examinator) <anstr@math.chalmers.se>, tel.: 772 5372, rum 5266, Ann-Briths hemsida

Fredrik Altenstedt (föreläsare/kursassistent) <alten@math.chalmers.se>, tel.: 772 5379, rum 5267, Fredriks hemsida

Maillista

Här kan du anmäla dig till kursens email-lista. Listan kommer användas för att förmedla information även till de vilka väljer att inte gå på samtliga föreläsningar.

Schemat har justerats enligt följande: v 36 måndag 15-17, onsdag 10-12 och torsdag 10-12. Övriga veckor måndagar 13-15, tisdagar 10-12 och onsdagar 10-12. (Salar enligt schemat nedan.)
Kopior av det material som delats ut vid föreläsningar finns i en tidskriftssamlare utanför Ann-Briths dörr (rum 5266). Det mesta finns också att ladda ner från denna sida.
Sal S4 ligger i MD-huset, våningsplan 3, huskropp 2 (i breda korridoren).

Beskrivning av kursen

En grundläggande kurs i optimering under osäkerhet (eller, stokastisk optimering). Den ger inblick i praktiska problemställningar som uppkommer vid kvantitativt beslutsfattande inom ekonomi, samhällsplanering och ingenjörsvetenskap inom vilka det är viktigt att beakta osäkerhet i indata; exempel ges via aktuella tidskriftsartiklar och projekt. Kursen ger kunskap om modellering av beslutsproblem med osäker information som stokastiska optimeringsproblem, illustrerar vikten och nyttan av att beakta denna typ av modellering samt presenterar exempel på metoder för att effektivt lösa de optimeringsproblem som uppkommer. Kursen ger också kunskap om och förståelse av den grundläggande matematiska teori som är relevant för denna typ av modeller. [Ladda ner kursinformation]

Kursstart

Introduktionsföreläsning äger rum måndagen den 3 september kl. 15.15-17.00 i sal MD10 (i Matematiskt Centrum).

Viss justering av föreläsningstider har gjorts i samband med första kurstillfället. Schemat nedan är justerat (010903 kl. 19.00)

Du som vill läsa kursen men inte kan närvara vid första kurstillfället bör kontakta Ann-Brith eller Fredrik så snart som möjligt.

Litteratur

Valda delar ur

[KW] Kall, P. och Wallace, S.W.: Stochastic Programming (uppdaterad upplaga jämfört med bok publicerad av Wiley, 1994).
[HV] Klein Haneveld, W.K. och van der Vlerk, M.H.: Stochastic Programming (Lecture Notes, University of Groningen, 2000).
[BL] Birge, J.R. och Louveaux, F: Introduction to Stochastic Programming (Springer, 1997).
[NS] Nash, S.G. och Sofer, A.: Linear and Nonlinear Programming (McGraw-Hill, 1996).
[ IU] Inlämningsuppgifter.
[LP] Introduktion till linjärprogrammering.

samt följande vetenskapliga artiklar och utdrag ur böcker:

[BeN00] Ben-Tal, A. och Nemirovski, A.: "Robust solutions of linear programming problems contaminated with uncertain data", Mathematical Programming 88(3):411-424 (2000).
[Car+94] Carino, D.R.; Kent, T.; Myers, D.H.; Stacy, C.; Sylvanus, M.; Turner, A.L.; Watanabe, K. och Ziemba, W.T.: "The Russell-Yasuda Kasai model: An asset/liability model for a Japanese insurance company using multistage stochastic programming", Interfaces 24(1):29-49 (1994).
[Hoy+97] Hoyland, K.; Ranberg, E.; Wallace, S.W. och Westgaard, S.: "Kapitalforvaltning i et livselskap", Okonomi og Ledelse 2:71-84 (1997).
[Dup+91] Dupacova, J.; Gaivoronski, A.; Kos, Z. och Szantai, T.: "Stochastic programming in water management: A case study and a comparison of solution techniques", European Journal of Operational Research 52:28-44 (1991).
[RoU00] Rockafellar, R.T. och Uryasev S.: "Optimization of conditional value-at-risk", The Journal of Risk 2(3):21-41 (2000).
[Ury00] Uryasev, S.: "Conditional value-at-risk: Optimization algorithms and applications", Financial Engineering News no. 14:1-5, February (2000).
[Pol87] Polyak, B.T.: Kapitel 4 och 5.5 (Influence of noise) ur: "Introduction to Optimization" , (Optimization Software, 1987).
[BeT00] Bertsekas, D.P. och Tsitsiklis, J.N.: "Gradient convergence in gradient methods with errors", SIAM Journal on Optimization 10(3):627-642 (2000).

Examination

Lösning och skriftlig redovisning av ett antal inlämningsuppgifter
Muntlig presentation av en inlämningsuppgift
Modellering, lösning (m.h.a. programvara) och muntlig presentation av ett praktikfall
Muntlig presentation av en vetenskaplig artikel
För överbetyg ges en muntlig tentamen

Schema (kan komma att justeras ytterligare)

Vecka	Dag	Tid	Sal	Ungefärligt innehåll	Läsanvisning	Lärare	Övrigt
v 36	måndag	13.15-15.00	MD10	Asset-liability management via stochastic programming for a Swedish life insurance company		FA	Lic-seminarium
	måndag	15.15-17.00	MD10	Introduktion, repetition av LP, känslighetsanalys, dualitet	[NS] 4-6, [LP]	ABS	Kursstart & upprop. [Föreläsning 1 OH-bilder]
	onsdag	10.00-11.45	MD3	Optimalitet, dekomposition	[KW] 1.7 & 1.3, [BeN00]	FA	[Föreläsning 2 OH-bilder]
	torsdag	10.00-11.45	MD3	Illustrativa exempel från jordbruk och byggsektor	[BL] 1.1.a-d, [KW] 1.1, [HV] 1 & 2.1	ABS	[Föreläsning 3 OH-bilder] [Föreläsning 3 Figurer] [Inlämningsuppgifter I]
v 37	måndag	13.15-15.00	MD3	Stokastiska variabler, fördelningar, utfallsrum, scenarier och -träd, diskretisering, deterministisk ekvivalent	[KW] 1.3-6 & 2.1-6	FA	[Föreläsning 4 OH-bilder]
	tisdag	10.00-11.45	S4	Utility-funktioner	[HV] 2	FA
	onsdag	10.00-11.45	MD3	Tvåstegsmodeller med recourse, optimalitet	[HV] 3, [KW] 3	ABS	[Inlämningsuppgifter II] [Föreläsning 6 OH-bilder (en aning justerade)]
v 38	måndag	13.15-15.00	MD3	Algoritmer för linjära recourse-problem	-"-	ABS	[Föreläsning 7 OH-bilder (en aning justerade)]
	tisdag	10.00-11.45	S4	Värdet av den stokastiska lösningen & varianter, gränser m.m.	[HV] 3, [KW] 3, [BL] 4	FA	[Föreläsning 8 OH-bilder (en aning justerade)]
	onsdag	10.00-11.45	MD3	Finansiell planering, scenariegenerering	[BL] 1.2, [Car+94], [Hoy+97]	FA	[Föreläsning 9 OH-bilder (en aning justerade)]
v 39	måndag	13.15-15.00	MD3	Handledning eller föreläsning		FA	Sista dag för skriftlig redov. av inlämn.I
	tisdag	10.00-11.45	S4	Modellering med probabilistiska bivillkor, modellering av risk inom finans, robust optimering	[HV] 5.1-4, [Dup+91], [RoU00], [Ury00], [BeN00]	FA	[Föreläsning 10 OH-bilder (justerade)]
	onsdag	10.00-11.45	MD3	Fallstudie i finansiell planering för Livia		FA
v 40	måndag	13.15-15.00	MD3	Muntliga redovisningar		studenter
	tisdag	10.00-11.45	S4	Muntliga redovisningar		studenter
	onsdag	10.00-11.45	MD3	Muntliga redovisningar		studenter
v 41	måndag	13.15-15.00	MD3	Algoritmer: Stokastisk kvasigradient	[KW] 3.9, [Pol87], [BeT00]	ABS	Sista dag för skriftlig redov. av inlämn.II
	tisdag	10.00-11.45	S4	Muntliga redovisningar		studenter
	onsdag	10.00-11.45	MD3	Stokastiska heltalsmodeller + Muntliga redovisningar	[BL] 3.3, [HV] 4.1-3	ABS + studenter	[Föreläsning 13 OH-bilder (en aning justerade)]
v 42	måndag	13.15-15.00	MD3	Muntliga redovisningar		studenter
	tisdag	10.00-11.45	S4	Kursutvärdering		alla
	onsdag	10.00-11.45	MD3	Muntliga redovisningar		studenter	Sista dag för skriftlig redovisning av fallstudier

Ett schema med bokade datorsalar finns här.

Muntlig presentation av artiklar

För att få godkänt på kursen skall man medverka vid presentationen av en vetenskaplig artikel. En till tre personer presenterar tillsammans; men eftersom det finns 13 artiklar att välja bland och antalet kursdeltagare är ca 25 så är inte friheten total vad gäller antalet medlemmar i varje grupp. Varje artikel skall presenteras vid ett visst kurstillfälle, se artikellista och schema. Utifrån detta kan ni välja artikel att presentera. Presentationen skall vara ca 20-30 minuter lång, inklusive frågestund. En kopia av vardera artikel finns i tidskriftssamlaren utanför Fredriks dörr (rum 5267) och en kopia av schemat sitter på Ann-Briths dörr (rum 5266). Om ni bestämmer er för en viss artikel så skriv upp era namn på listan. Artiklarna och listan kommer också att finnas med vid nästa föreläsning.

Hjälp till inlämningsuppgift I

För att lösa uppgifterna behöver ni använda t.ex. modelleringsspråket AMPL, tillsammans med en lämplig lösare, som t.ex. Cplex eller någon hos NEOS server for optimization (klicka vidare på lämplig lösare och sedan på "www-form", lägg in dina modell- och data-filer, skicka iväg problemet och vänta på lösningen).

Eventuellt kan ni använda Cplex direkt: Quick guide to Cplex.

Vissa av uppgifterna kan ev. lösas m.h.a. Matlab's Optimization toolbox (skriv matlab i kommandofönstret).

Nedan finns lite instruktioner om AMPL.

Ny, korrigerad version av AMPL-hjälpen!!!

Papperet finns i PS-format och i DVI-format . De filer som refereras till i papperet finns även som zip-fil och tar-fil för dem som vill köra på andra ställen. Om man vill köra på andra ställen behöver man även programvara som finns att hämta hos netlib. Notera att programvaran minos ej klarar heltaliga variabler. För dessa problem måste lp-solve eller cplex användas. Lp-solve respektive cplex används i ampl genom att ge kommandot options solver lpsolve eller options solver ampl_cplex.

Mer information om ampl finns på AMPL's hemsida, där det även finns en artikel som beskriver en äldre version av språket. Dessutom finns ett antal exempel här.

Hjälp till inlämningsuppgift II

Om modellerna i Inlämningsuppgifter II blir för stora att lösa med ovanstående versioner av AMPL, kan man pröva att skicka dem till NEOS server for optimization, (Klicka vidare på lämplig lösare och sedan på "www-form". Lägg in dina modell- och data-filer, skicka iväg problemet och vänta på lösningen.)

Fallstudier

Varje grupp (om 1-3 personer) skall analysera en av modellerna nedan, vilket innebär att några fall kommer att analyseras av fler än en grupp. Analysen skall skrivas ned i en utförlig rapport, som lämnas in senast onsdag i vecka 42. Varje fall skall presenteras muntligt av någon grupp, enligt schemat. Ett häfte med handledning för fallstudierna finns nu här.

Fall	Presenteras av	Analyseras även av
#1 (Multi-period production planning)	Mikael S o Tapani	??
#2 (Budgeting cost of nursing in a hospital)	Mikael W och Fredrik Ho	Cecilia, Nils, Walter och Reine
#3 (Growing maize and sorghum in Kilosa district)	Martin, Sara och Fredrik He	??
#4 (Product mix problem)	Fadia och Anna	??
#5 (Investment planning for electricity generation)	??	Joel och Gunnar

Muntlig presentation av en inlämningsuppgift eller fallstudie sker enligt följande schema. Du som ännu inte har anmält dig kan göra det på listan som sitter på Ann-Briths dörr.

Muntlig tentamen för överbetyg

I tentamens-stoffet ingår följande:

All kurslitteratur (framgår av läsanvisningarna ovan)
Förutom den artikel man själv presenterat; fem av de artiklar som presenterats under kursens gång, nämligen följande:
- Eppen, G.D.; Martin, R.K. & Schrage, L. (1989) ``A Scenario Approach to Capacity Planning,'' Operations Research 37(4):517-527
- Maatman, A.; Ruijs, A.; Schweigman, C. & van der Vlerk, M.H. (2001) ``Modeling Farmers' Response to Uncertain Rainfall in Burkina Faso: A Stochastic Programming Approach,'' Stochastic Programming e-Print Series: http://dochost.rz.hu-berlin.de/speps/
- Palmquist, J.; Uryasev, S. & Krokhmal, P. (1999) ``Portfolio Optimization with Conditional Value-at-Risk Objective and Constraints,'' Research report 99-14, ISE Dept., University of Florida http://www.ise.ufl.edu/uryasev/pubs.html\#t
- Shih, J.-S. & Frey, H.C. (1995) ``Coal Blending Optimization Under Uncertainty,'' European Journal of Operational Research 83:452-465
- Tsamasphyrou, P.; Renaud, A. & Carpentier, P. (2000) ``Transmission Network Planning Under Uncertainty with Benders Decomposition,'' in: Optimization, V.H. Nguyen, J.-J. Strodiot & P. Tossings, eds., Proceedings of the 9th Belgian-French-German Conference on Optimization, Namur, September 7-11, 1998, Springer, Berlin, pp.457-472
För den som presenterat någon av dessa fem artiklar ingår även artikeln:
- Escudero, L.F.; Kamesam, P.V.; King, A.J. & Wets, R.J-B (1993) ``Production Planning via Scenario Modeling,'' Annals of Operations Research 43:311-335

Kopior av ovanstående artiklar finns att hämta i tidskriftssamlare utanför Fredriks dörr; de kommer också att finnas med vid seminarierna i vecka 42.

Själva muntan går till så att man får ut tre uppgifter plus en av de fem artiklarna (slumpvis utvalda) att fundera över/läsa på/lösa under ca två timmar. Man får INTE ha med kurslitteraturen under dessa timmar. Sedan träffar man oss (Ann-Brith och Fredrik) under ungefär en timma, då man diskuterar uppgifterna och får svara på frågor om innehållet i den 'slumpade' artikeln plus sin egen artikel.

Tider och lokaler för muntan framgår av schemat men man kan lämpligtvis komma till våra tjänsterum (5266 och 5267) och "hämta ut" materialet.

Last modified: Tue Oct 16 12:31:12 MET DST 2001