lu.se

Forskar­utbildnings­kurser

Lunds tekniska högskola | Lunds universitet

Detaljer för kursplan för kurs EIT090F giltig från och med HT 2014

Utskriftsvänlig visning

Allmänt
  • Engelska
  • Varannan vårtermin
Syfte
  • Målsättningen med kursen är att kursdeltagarna skall erhålla grundläggande kunskaper inom området heltalsprogrammering som är en fundamental optimeringsmetod för att lösa verkliga ingenjörsmässiga optimeringsproblem. De fundamentala optimeringsmetoderna illustreras genom tillämpning på representativa problem inom nätverksdesign, t.ex. modeller av flöden med flera varutyper. Studenterna kommer även att bli bekanta med GUROBI, en effektiv programvara för att lösa optimeringsproblem. Studenter med bakgrund från andra områden än kommunikationsnätverk kommer att få möjlighet att utveckla optimeringsmodeller inom sina egna områden.
Innehåll
  • 1. Introduktion. Ett illustrativt exempel: design av nätverk med flera varutyper (multi-commodity flow networks). Enkla samt svåra versioner av problemet.
    2. Linjärprogrammering (LP). Grundläggande notation och egenskaper hos LP problem. Fundamenten inom Simplex metoden.
    3. Blandad heltalsprogrammering (MIP) och dess relation till LP. Branch-and-bound algoritmen för problem med binära variabler. Tillämpning på problem inom vägval och nätverkstopologidesign. Utvidgning till generella formuleringar av MIP. Insikt i effektiviteten av B&B.
    4. Modellering av icke-lineäritet. Konvexa och konkava målfunktioner samt väsentliga skillnaderna mellan dem. Stegvisa kostnadsfunktioner.
    5. Den generella formen av ett optimeringsproblem. Relaxation: linjär relaxation, koncept i dualitetsteorin. Dualitet i konvex programmering. Dualitetsgapet samt dualitet inom LP.
    6. Dualitet inom MIP och Lagrangesk relaxation (LR). Dual separering och kolumngenerering (tillämpning: flödesallokeringsproblem)
    7. Plansnittningsmetoden. Giltiga olikheter och branch-and-cut (B&C) metoden. Branch-and-price (B&P) metoden.
    8. Heuristik for kombinatorisk optimering. Sökning i närområdet. Stokastisk heuristisk: simulerad anlöpning med tillämpning på handelsresandeproblemet samt evolutionära algoritmer (tillämpning på modulär flödesallokering).
    9. NP-fullständighet. Separationsteoremet.
    10. Tillämpning: design av trådlösa nätverk.
Kunskap och förståelse
  • För godkänd kurs skall doktoranden
  • modellera optimeringsproblem som uppstår i tekniska tillämpningar och lösa dessa. Doktoranden ska visa förmåga att formulera modeller baserade på linjär och heltalsprogrammering. Vidare skall doktoranden visa förståelse för Simplex-metoden och branch-and-bound algoritmen, tillsammans med dess utvidgningar såsom kolumngenerering och det plansnittningsmetoden. Slutligen ska doktoranden förstå begränsningarna hos effektiva beräkningsmetoder av de studerade problemen.
Färdighet och förmåga
  • För godkänd kurs skall doktoranden
  • självständigt kunna konstruera modeller för optimeringsproblem och tillämpa optimeringspaket GUROBI (eller liknande) för att lösa dem, ha full förståelse av lösningsprocessen och kunna bedöma resultatens rimlighet. Doktoranden skall också kunna utveckla egna räkneövningar med det specifika målet att lära ut enskilda koncept och färdigheter till elever.
Värderingsförmåga och förhållningssätt
  • För godkänd kurs skall doktoranden
  • kritiskt kunna utvärdera resultat, särskilt med avseende på förenklande antaganden som behövs för att skapa en lätthanterlig modell. Studenten skall vara väl insatt i begränsningarna av befintliga teoretiska modeller i form av beräkningseffektivitet, och kunna bedöma giltigheten och riktigheten av de formulerade optimeringsmodellerna.
Undervisningsformer
  • Föreläsningar
  • övningar
  • Projekt
  • Litteraturkurs som självstudier
  • Självstudierna fyller två funktioner. Studenterna skall dels utöka teoristudierna inom MIP och lösa individuella tilldelade uppgifter som illustrerar teorin. Dels skall studenterna sammanställa en rapport angående den huvudprojektuppgiften som skall lösas med hjälp av GUROBI.
Examinationsformer
  • Skriftlig tentamen
  • Skriftlig rapport
  • Inlämningsuppgifter
  • Underkänd, godkänd
Förkunskapskrav
Förutsatta förkunskaper
  • Deltagarna skall vara väl bekanta med teknisk högskolematematik såsom en- och flervariabelanalys, analytisk geometri, linjära ekvationssystem samt dataprogrammering.
Urvalskriterier
Litteratur
  • Wolsey, L.A.: Integer Programming. J. Wiley, 1998. ISBN 0471283665.
    Lasdon, L.: Optimization Theory for Large Systems. MacMillan, 1972.
    Pioro, M.: Network Optimization Techniques, Chapter 18 in Serpedin, E., Chen, T. and Rajan, D. (eds.), Signal Processing, Communications, and Networking. CRC Press, 2012. ISBN 9781439855133.
  • Item 2. Library of Congress catalog card number: 78-95301
Övrig information
  • Kursansvarig: Michal Pioro, michal.pioro@eit.lth.se
Kurskod
  • EIT090F
Administrativ information
  •  -08-26
  • FN1/Anders Gustafsson

Alla publicerade kurstillfällen för kursplanen

Inga matchande kurstillfällen hittades.

0 kurstillfällen.


Utskriftsvänlig visning