EL3350 Nätverksoptimering 4,0 hp

Network Optimization

Teorin för nätverksoptimering ger möjlighet att fatta optimala beslut över nätverk och har en viktig roll i ingenjörsvetenskapen, med tillämpningar inom bland annat kommunikationsnätverk, signalbehandling, dataanalys, smarta elnät, intelligenta transportsystem och finans. Typiska tilllämpningar kan vara dirigering (routing), auktioner, kostnadsminimering av flöden, handelsresandeproblemet, generaliserad tilldelning, uppspännande träd och matchning.

Kursen ger en översikt av de fundamentala aspekterna av nätverksoptimering och dess tillämpningar, med fokus på linjära, olinjära och diskreta problem. Samspelet mellan diskreta och kontinuerliga problem uppmärksammas. Diskreta nätverksoptimeringsproblem diskuteras i detalj. För kontinuerliga problem kommer dualitet och iterativ kostnadsminskning att studeras och appliceras på de vanligaste linjära problemen så som kostnadsminimering av flöden och logistikproblem. Kända lösningsmetoderna så som "branch-and-bound" , " Lagrangian relaxation", " Dantzig -Wolf decomposition", heuristiska tekniker och lokala sökmetoder kommer att studeras.

Kursen kommer presentera utvalda tillämpningar med inverkan på samhället, t ex optimala tilldelning av accesspunkter i trådlösa nätverk, optimala strömmar i smarta elnät, schemaläggning i intelligenta transportsystem och integritetsbevarande optimering.

  • Utbildningsnivå

    Forskarnivå
  • Huvudområde

  • Betygsskala

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

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

EES/Reglerteknik

Examinator

Carlo Fischione <carlofi@kth.se>

Versionsinformation

Kursplan gäller från och med VT2014.