EL3350 Nätverksoptimering 4,0 hp

Network Optimization

  • Utbildningsnivå

    Forskarnivå
  • Huvudområde

  • Betygsskala

    P, F

Det finns inget planerat kurstillfälle.

Lärandemål

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

Kursens huvudsakliga innehåll

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

Kursupplägg

7 föreläsningar (2 timmar per föreläsning), 5 övningslektioner (1 timmer per session), 5 hemuppgifter, hemtentamen och ett forskningsprojekt.

Behörighet

Litteratur

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

Examination

  • EXA1 - Examination, 4,0, betygsskala: P, F

Krav för slutbetyg

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

Ges av

EECS/Reglerteknik

Examinator

Carlo Fischione <carlofi@kth.se>

Versionsinformation

Kursplan gäller från och med VT2014.
Examinationsinformation gäller från och med VT2019.