AU kursuskatalog arkiv

Blandet heltalsoptimering Q3+Q4 ( forår 2011 - 10 ECTS )

Rammer for udbud

• Uddannelsessprog: dansk
• Niveau: Kandidatkursus.  
• Semester/kvarter:  3. + 4. kvarter (Forår 2011).
• Timer per uge: 4.  
• Deltagerbegrænsning:
• Undervisningssted: Århus
• Hovedområde: Det Naturvidenskabelige Fakultet
• Udbud ID: 30360

Formål

 Mange praktiske problemer der opstår i anvendelser indenfor operationsanalyse kan formuleres som blandede heltalsoptimeringsproblemer. Dette har betydet, at der er blevet udviklet software, der kan løse sådanne problemer.
Antallet af anvendelser af blandet heltalsoptimering er enormt, og blandet heltalsoptimering har blandt andet været succesfuldt anvendt i forskellige områder af økonomi, management, industri og indenfor ingeniørbranchen. Kursets formål er at formidle den fundamentale teori bag blandet heltalsoptimering og de basale teknikker, der bruges i state-of-the-art software til at løse blandede heltalsoptimeringsproblemer.

Indhold

 Eksempler på blandede heltalsoptimeringsproblemer og anvendelser; ideele formuleringer af blandede heltalsmængder; total unimodularitet; gitre og gitter-punkt-frie mængder; gitter-punkt-frie mængder og relakseringer; split snit; separering af split snit; snit fra en basis; mixed integer Gomory snit, Chvátal-Gomory snit, disjunkte snit,
mixed-integer afrundingssnit og lift-and-project snit; dualitet i blandet heltalsoptimering; branch-and-bound algoritmer;
branch-and-cut algoritmer; en sofware pakke til blandet heltalsoptimering : Eksempler på computer programmer til
at løse blandede heltalsoptimeringsproblemer; design af computer programmer til at løse konkrete blandede
heltalsoptimeringsproblemer.   

Faglige forudsætninger

 Matematisk programmering. 

Underviser

Kent Andersen.

Undervisnings- og arbejdsform

2 x 2 timers forelæsninger pr. uge. 

Engelsk.

Litteratur

Bertsimas D., Weismantel R. (2005) Optimization over Integers, Dynamic Ideas.

Udbyder

Institut for Matematiske Fag.

Tilmelding til undervisning

På selvbetjeningen https://mit.au.dk fra den 1. til den 15. november 2010.

Læringsmål

Ved kursets afslutning forventes den studerende på kurset at kunne:

• Forklare vigtigheden af tætte relakseringer af blandede heltalsmængder og forklare hvordan man konstruerer tættere relakseringer af en blandet heltalsmængde givet en eksisterende relaksering.
• Udlede valide uligheder for en blandet heltalsmængde.
• Modellere praktiske problemstillinger som blandede heltalsoptimeringsproblemer.
• Forklare hvordan eksisterende software til løsning af blandede heltalsoptimeringsproblemer virker, og hvordan man kan løse konkrete blandede heltalsoptimeringsproblemer med eksisterende software.

Bedømmelse

• Mundtlig, bedømt efter 7-skala med ekstern censur
5 xxxxx

Eksamen består af to afleveringsopgaver, en efter hvert kvarter, og en mundlig eksamen af 20 minutter efter det anden kvarter. Hver afleringsopgave har et arbejdsomfang af cirka 20 timer. Mundtlig eksamen er uden forberedelsestid. Alle eksamensdele er med en ekstern censor. En enkelt karakter gives efter den danske 7-trin karakterskala baseret på de skriftlige afleveringsopgaver og den mundtlige eksamen.