Linear and Combinatorial Optimization, VT-1 2008.

The course in Linear and Combinatorial Optimization is given in VT-1, Spring term, 2008. The information below will continuously be updated during the course. If you have any questions, please contact Fredrik Kahl, fredrik@maths.lth.se.

Lectures:

Wednesday 8-10, MA5 and Friday 13-15, MA5.

Take-home exam:

The take-home exam can be picked up from 3 to 7 March at the secretary on the 5th floor (MH building). It should be returned within one week from the time you collected it.

Various material:

What is combinatorial optimization (in Swedish)?
Course plan for 2008.
Lecture notes 2008 (pdf): F1, F2-F3, F4, F5, F6, F7, F8, F9, F10, F11, F12, F13.
Homework for 2008: Inl 1. Deadline: 30 January. Inl 2. Deadline: 15 February. Matlab file: inl2.m. Inl 3. Deadline: 22 February. Inl 4 (pdf) (due on February 29). Corresponding matlab files: Inl 4 tar.gz, Inl 4 zip.
NOTE: All hand-in exercises should be done individually.
Computer laboratory exercises.
Lab 1: Wednesday 6/2-2008 kl 15-17 (MH:140).
Lab 2: Wedndesday 20/2-2008 kl 15-17 (MH:140).
Laboratory guide for 2008: Lab 1.ps, Lab 1.pdf, Lab 2.ps, Lab 2.pdf. Corresponding matlab files: Lab 1, Lab 2 tar.gz, Lab 2 zip.
Excerpt on algorithm complexity (handed out at lecture)
Excerpts on dynamic programming (handed out at lecture)
Excerpt on simulated annealing (handed out at lecture)
Excerpt on genetic algorithms (handed out at lecture).

Literature:

B Kolman, R. E. Beck: Elementary Linear Programming with Applications. Acdemic Press 1995. ISBN 0-12-417910.
Lecture notes.

Other references:

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:

För er som vill ha mer information om och kring matlab.

Pärt-Enander, Sjöberg: Användarhandledning för MATLAB. Uppsala Universitet. Se även deras hemsida.
För studenter finns matlab att få direkt - kolla hos LTH:s datordriftgruppen.
Anders Holtsberg utvecklade för några år sedan en kort matlab och maple introduktion.
K. Sigmon: Matlab Primer (Postscript, 256 K) (3d ed) (beskriver version 4, något föråldrad, men fortfarande användbar speciellt för beräkningar.)
Här är Matlabs hemsida.
Här finns massor av information om Matlab (och ett par andra program).

Laborationer

I kursen ingår två obligatoriska laborationer.

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

Övningsförslag ur kursboken

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

Examination

Examination på kursen bygger på fyra moment:

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

För slutbetyg på kursen krävs godkänt på inlämningsuppgifter, laborationer och hemtentamen samt godkänd tentamensdiskussion.

Other courses:

For those of you who are interested in more about optimization and related topics, I can recommend:

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.

Links to other pages on linear and combinatorial optimization

Global Optimization.
FAQ on Linear Programming.
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.).
The SDPpack Home Page Ett paket för semidefinit programmering.
SDPSOL En del av samma paket.
PCx Linear Programming Code En effektiv LP-lösare.
Handelsresandeoptimering med genetiska algoritmer.
Dopplertomografi med lokalsökning.

Här kan man läsa om dagens matematiker.

Fredrik Kahl
Department of Mathematics (LTH)
Lund Institute of Technology / Lund University
Box 118, 221 00 LUND

Room: 346
Direct Phone: +46 46 22 244 51
Dept. Phone: +46 46 22 285 37
Fax: +46 46 22 240 10
e-mail: fredrik@maths.lth.se
www: http://www.maths.lth.se/matematiklth/personal/fredrik/