Detaljer för kursplan för kurs EIT090F giltig från och med HT 2014 Utskriftsvänlig visning Kurskod:EIT090F Gäller från och med:Höstterminen 2014 Kursplanen är fastställd Allmänt Undervisningsspråk:Engelska Ges:Varannan vårtermin Kurshemsida: 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 Kommentarer: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 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 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. Kommentarer:Item 2. Library of Congress catalog card number: 78-95301 Övrig information Kursansvarig: Michal Pioro, michal.pioro@eit.lth.se Kurskod Kurskod:EIT090F Administrativ information Datum för fastställande: -08-26 Beslutad av:FN1/Anders Gustafsson Alla publicerade kurstillfällen för kursplanen Inga matchande kurstillfällen hittades. 0 kurstillfällen. Utskriftsvänlig visning