Tillämpad optimering I

Mål

Syftet med kursen är att ge kunskap om tillämpning av optimeringslära, med fokus på att tillämpa teorier och metoder i kombinatorisk optimering för att modellera och lösa optimeringsproblem inom transport- och kommunikationsområdet. Kursen syftar även till att ge praktisk färdighet i att sätt upp optimeringsmodeller och använda optimeringsmetoder. Efter kursen ska studenterna kunna

• beskriva ämnets koppling till utbildningsprogrammet
• redogöra för grundläggande teorier och metoder inom kombinatorisk optimering och heltalsprogrammering
• redogöra för klassiska optimeringsproblem och -modeller inom kommunikations- och transportområdet
• förklara begrepp inom problemkomplexitet och dess betydelse inom storskalig optimering
• använda ett modelleringssystem för optimeringsmodellering och problemlösning
• redogöra för samt tillämpa moderna heuristiker för att lösa storskaliga optimeringsproblem

Innehåll

Grundläggande begrepp inom kombinatorisk optimering; heltalsmodeller; koppling mellan kombinatorisk optimering, linjärprogrammering och heltalsprogrammering; trädsökning och plansnittning för heltalsprogrammering; klassiska problem inom kombinatorisk optimering: billigaste väg, minimum uppspännande träd, matchning, lokaliseringsproblem, handelsresandeproblemet, färgläggning; problemkomplexitet: komplexitetsklasser och dess teoretiska och praktiska betydelse inom kombinatorisk optimering; betydelse av val av heltalsmodellen inom storskalig optimering;problemrelaxation och relaxationsmetoder; tillämpning av heuristik och relaxationsmetoder; heuristiker: girighetsheuristik, lokal sökning, tabu sökning, simulated annealing.