Gäller från och med: Höstterminen 2014
Beslutad av: FN1/Anders Gustafsson
Datum för fastställande: 2013-08-26
Avdelning: Inst för elektro- och informationsteknik
Kurstyp: Ren forskarutbildningskurs
Undervisningsspråk: Engelska
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.
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.
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.
Item 2. Library of Congress catalog card number: 78-95301
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
Betygsskala: Underkänd, godkänd
Examinator:
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.
Kursansvarig: Michal Pioro, michal.pioro@eit.lth.se
Kursansvariga: