studiehandbok@lith
 

Tekniska högskolan vid Linköpings universitet

 
 
År : 2015
 
TA1014 Diskret optimering, 6 p / 9 hp
/Discrete Optimization/

För:  


OBS!

Doktorandkurs


 

Prel. schemalagd tid: 48
Rek. självstudietid: 192

  Utbildningsområde: Naturvetenskap

Ämnesgrupp: Matematik   Nivå (A-D):D

Huvudområde: Matematik, Tillämpad matematik   Nivå (G1,G2,A): A

  Mål:
Kursen avser att ge grundläggande kunskaper inom heltalsoptimering, vad gäller tillämpningsområden, teori och lösningsmetoder.
Efter avslutad kurs ska studenten:
  • kunna identifiera när optimeringsmodeller med heltaliga variabler uppstår och kunna använda vanligt förekommande principer för att formulera sådana modeller
  • känna till vikten av att formulera starka heltalsmodeller och hur sådana konstrueras
  • kunna använda de vanligaste metoderna för att finna uppskattningar av optimum med hjälp av relaxeringar
  • känna till viktiga heltalsproblem som är polynomiellt lösbara och som inte är det
  • kunna använda komplexitetsresultat som riktlinje för val och utformning av lösningsmetoder
  • känna till viktiga metodprinciper för några viktiga typer av polynomiellt lösbara kombinatoriska optimeringsproblem
  • kunna använda grundläggande metodprinciper för exakt eller approximativ lösning av heltalsproblem som inte är polynomiellt lösbara.


  Förkunskaper: (gäller studerande antagna till program som kursen ges inom, se 'För:' ovan)
Grundläggande kurser i matematik, optimeringslära och datalogi.

OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande.

  Organisation:
Seminarier där kursdeltagarna presenterar material från kurslitteraturen och redovisar lösningar till valda uppgifter, samt presenterar tillämpningar.

  Kursinnehåll:
Formulering av heltalsmodeller. Transformationer och stärkningar av modeller. Kombinatoriska optimeringsproblem: mängdövertäckning, mängduppdelning, matchning, kapningsproblem och handelsresandeproblem. Översikt av linjär optimering: grunder, geometri och lösningsmetoder. Översikt av nätverksoptimering. Klassiska lösningsmetoder: trädsökning, plansnittning och gruppteoretiska ansatser. Trädsökning och plansnittning: giltiga olikheter, snittgenerering, snitt för speciella strukturer. Trädsökning och kolumngenerering: Dantzig-Wolfe dekomposition och tillämpning på det generaliserade tillordningsproblemet. Metoder baserade på heuristiker, Lagrangerelaxation och Benders dekomposition. Lösning med kommersiell programvara. Utvalda praktiska tillämpningar.

  Kurslitteratur:
Applied Integer Programming: Modeling and Solution, D.-S. Chen, R.G. Batson and Y. Dang, Wiley, 2010. Kompletterande material om tillämpningar.

  Examination:
UPG1
Aktivt deltagande i seminarier (U,G)
9 hp
 
På kursen ges betyg Underkänd/Godkänd.



Undervisningsspråk är Engelska.
Institution: MAI.
Studierektor: Ingegerd Skoglund
Examinator: Torbjörn Larsson
Ansvarig programnämnd: Elektro&Fysik


Kursen bedrivs på ett sådant sätt att både mäns och kvinnors erfarenhet och kunskaper synliggörs och utvecklas.

Planering och genomförande av kurs skall utgå från kursplanens formuleringar. Den kursvärdering som ingår i kursen skall därför genomföras med kursplanen som utgångspunkt.

Om inget annat anges ovan gäller betygsskala enligt avsnitt a8.5 i de gemensamma bestämmelserna.

Kursplanen gäller för 2015 enligt beslut av ansvarig programnämnd/fakultetstyrelse.

Tekniska högskolan vid Linköpings universitet


Informationsansvarig: TFK , val@tfk.liu.se
Senast ändrad: 01/12/2016