EIT090F

Tillfällig

Heltalsprogrammering

7.5

Ren forskarutbildningskurs

7201 (Inst för elektro- och informationsteknik)

 -08-26

FN1/Anders Gustafsson

Engelska

Varannan vårtermin

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.

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.

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.

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.

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.

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.

Skriftlig tentamen

Skriftlig rapport

Inlämningsuppgifter

Underkänd, godkänd

Deltagarna skall vara väl bekanta med teknisk högskolematematik såsom en- och flervariabelanalys, analytisk geometri, linjära ekvationssystem samt dataprogrammering.

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

Kursansvarig: Michal Pioro, michal.pioro@eit.lth.se

EIT090F

 -08-26

FN1/Anders Gustafsson