Linjär och Kombinatorisk Optimering, LP3 2001.

Kursen i Linjär och Kombinatorisk optimering ges under lp3 våren 2001. Nedanstående information är delvis tagen från läsåret 1999. Mycket av informationen kommer att uppdateras under kursens gång. Hör av dig till kursledaren kalle@maths.lth.se om du har några frågor. Föreläsningar sker måndagar 8.15 samt tisdagar 8.15 i sal MH:234. Laborationer sker i sal MH:233. För mer information läs reklambladet eller titta på materialet nedan.

Lab 1 sker ons 7/2 kl 10-12 eller fre 9/2 kl 10-12 i sal MH:233.

Lab 2 sker tis 20/2 kl 10-12 eller ons 21/2 kl 10-12 i sal MH:233.

Utdelat material och kortfattade komihåg.

• Vad är kombinatorisk optimering.
• Kursplan för 2001.
• Delar av föreläsningsanteckningar 2001 (ps): F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11, F12, F13, F14,.
• Delar av föreläsningsanteckningar 2001 (pdf): F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11, F12, F13, F14.
• Delar av föreläsningsanteckningar 1999: F1, F2, F3, F4, F5, F6, F8, F9, F10, F11, F12, F13,
• Delar av föreläsningsanteckningar 1997: F1, F2, F3, F4, F5, F6, F9, F10, F11, F12, F13.
• Laborationer. Lab 1 sker ons 7/2 kl 10-12 eller fre 9/2 kl 10-12 i sal MH:233. Lab 2 sker tis 20/2 kl 10-12 eller ons 21/2 kl 10-12 i sal MH:233.
• Laborationshandledning för 2001: Lab 1. Lab 2. Tillhörande matlabkod: Lab 1 (tar.gz), Lab 1 (zip). Lab 2 (tar.gz), Lab 2 (zip).
• Inlamningsuppgifter för 2001: Inl 1, Inl 2. lp_exhaustive.m. Inl 3. inl3a.m. inl3b.m. Inl 4. Tillhörande matlabkod: Inl 4.
• Stenciler om algoritmkomplexitet.
• Stenciler om simulerad stelning.
• Stenciler om genetiska algoritmer.
• Stenciler om neurala nätverk.
• Stenciler om tabusökning.
• Matlabfiler till kombinatorisk optimering.

Vad händer sen?

• Artificiella neural networks (FYS228): Institutionen för teoretisk fysik har mycket erfarenhet av neurala nätverk. Dessa har en viss anknytning till optimering. I kursen ingår bland annat Linear discriminant methods, Multilayer Perceptrons, The Boltzmann machine, Feed-back networks, The mean field approximation, Optimization problems, Robust statistics.

Litteratur:

• B Kolman, R. E. Beck: Elementary Linear Programming with Applications. Acdemic Press 1995. ISBN 0-12-417910.
• Föreläsningsanteckningar.

• Papadimitriou and Steiglitz: Combinatorial Optimization, Prentice Hall, 1982.
• Aarts and Korst: Simulated Annealing and Boltzmann Machines, John Wiley & Sons, 1989.
• Migdalas, Göthe-Lundgren: Kombinatorisk Optimering, Matematiska Institutionen, LiTH, 1994.
• Vajda: The theory of Games and Linear Programming, Methuen's monographs on physical subjects, 1956.
• Goldberg: Genetic Algorithms, Addison-Wesley, 1989.
• Luenberger: Linear and nonlinear programming, Addison-Wesley, 1984.
• Duffin, Peterson and Zener: Geometric Programming - Theory and Application, John Wiley & Sons, 1967.
• Grötschel, Lovasz and Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer Verlag, 1993.

Matlab:

• Användarhandledning till matlab. Kort handledning finns att tillgå från avdelingen för matematisk statistik. Kontakta Aurelia.
• Enander, Sjöberg: Användarhandledning för MATLAB 5. Uppsala Universitet. Finns att beställa för 150 kronor + moms + frakt från Uppsala Universitet. Se även deras hemsida.

Laborationer

1. Simplexmetoden för att lösa linjärprogrammeringsproblem.
2. Transportproblemet, maximalt-flöde-minsta-snitt, algoritimer för kombinatorisk optimering.

Övningsförslag ur kursboken

1. 1.1: 4.
2. 1.3: 33, 37.
3. 1.5: 1, 6.
4. 2.1: 1, 9, 19, 21.
5. 2.3: 3, 20.
6. 3.1: 1, 3, 7.
7. 3.2: 1, 5, 9, 11.
8. 3.3: 1.
9. 3.4: 1, 9.
10. 3.5: 1, 3, 10, 11, 12.
11. 3.6: 1, 5.
12. 4.1: 1.
13. 4.2: 1, 3, 5.
14. 4.3: 1, 3.
15. 5.1: 9, 11, 15.
16. 5.3: 1, 5.
17. 5.4: 1, 3, 7.

Föreläsningssprogram

Examination

Examination på kursen bygger på fyra moment:

1. 4 inlämningsuppgifter.
2. 2 laborationer.
3. En hemtenta. Vi diskuterar senare i kursen tider för denna.
4. Om hemtentan är godkänd bestäms en tid för diskussion av tentamen.

Länkar till hemsidor om linjär och kombinatorisk optimering

1. Global Optimering.
2. Vanliga frågor om linjärprogrammering.
3. Boyd's research group index. Stephen Boyd är en av experterna inom området konvex optimering. Han har många värdefulla referenser, bland annat till fritt tillängliga lösare för Linjär programmerings problem och vissa utvidgningar av LP, (kvadratisk programmering, semidefinit programmering, etc.).
4. The SDPpack Home Page Ett paket för semidefinit programmering.
5. SDPSOL En del av samma paket.
6. PCx Linear Programming Code En effektiv LP-lösare.
7. Handelsresandeoptimering med genetiska algoritmer.
8. Myror i optimering
9. Dopplertomografi med lokalsökning.

Här kan man läsa om dagens matematiker och om populära matematiska konstanter.