FEL3350 Nätverksoptimering 4,0 hp

1. Introduktion till nätverksoptimering (L1)

- baseras på kap 1 i kursboken

- grundläggande terminologi och notation

- diskutera exempel på nätverksoptimering

- grunderna i linjär nätverksoptimering

2. "Shortest path problems" (L2)

- baseras på kap 2 i kursboken

- exempel på tillämpningsområden

- vanliga verktyg för att lösa problemet

- lösningsalgoritmernas prestanda

3. Maximala flödesproblem (L3)

- baseras på kap 3 i kursboken

- exempel på tillämpningsområden

- vanliga verktyg för att lösa problemet

4. Kostnadsminimering av flöden (L4)

-baseras på kap 4 i kursboken

- ekvivalenta varianter

- utveckla resultat inom dualitet i samband med problemet

5. Auktionsalgoritmer för kostnadsminimering av flöden (L5)

- baseras på kap 7 i kursboken

- steg för algoritmdesign

- varianter av auktionsalgoritmer

6. Flödesargument för begränsning av blandningstider för Markovkedjor (mixing time) (L6)

- introduktion av konceptet blandningstider för Markovkedjor

- begränsningar av konduktansen och relationen till egenvärden

- varuflöden och "method of canonical path"

7. "Accelerated dual descent" för flödesoptimering (L7)

- Newtons metod

- Approximativ Newtons metod baserad på nätverkets struktur

Efter slutförd kurs kommer deltagaren:

- känna till grunderna för linjär, icke-linjär, och diskret optimering

-känna till de viktigaste aspekterna av nätverksoptimering

- analysera på djupet de viktigaste problemen med nätverksoptimering

- kunna tillämpa nätverksoptimering i praktiska ingenjörsproblem

- utveckla ett forskningsprojekt

D. P. Bertsekas, Network Optimization Continuous and Discrete Models, Athena Scientific, Belmont, Mass., USA, 1998.

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

För att bli godkänd på kursen måste minst 70% av poängen uppnås enligt följande kategorier:

- Närvaro: godkänd om man har deltagit på minst två av sju föreläsningar

- Hemuppgifter: godkänd om man har klarat två av fem hemuppgifter

- Projekt: godkänt projekt

- Sluttenta: godkänd tentamen

Carlo Fischione

• Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
• Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
• Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.