Kursplan för Storskalig optimering

Grundläggande kunskaper i linjär och diskret optimering. Rekommenderas att ha läst TMA947 Nonlinear optimization.

Kursens syfte är att ge studenterna en inblick i några av de viktigaste principerna för effektiv lösning av praktiska, storskaliga optimeringsproblem, från modellering till metodkonstruktion. Efter en inledande serie föreläsningar ägnas kursens huvudsakliga verksamhet åt projektarbeten, vari studenterna utnyttjar dessa principer för att effektivt lösa några relevanta optimeringsproblem.

• självständigt analysera och föreslå modellerings- och lösningsprinciper för en uppsjö av typer av optimeringsproblem;
• och ha tillräckliga kunskaper för att kunna använda dessa principer i praktisk verksamhet med hjälp av mjukvaror för optimering.

Storskaliga optimeringsproblem har i princip alltid en inneboende struktur som kan - och skall - utnyttjas för att medge att de löses effektivt. Kursen behandlar ett antal grundläggande principer med vars hjälp storskaliga optimeringsproblem kan lösas. Tekniken kallas allmänt dekomposition-koordination och utnyttjar bland annat konvexitets- och dualitetsteori. Delar av denna teori behandlas i kursen Olinjär optimering (TMA947) men studeras här med ett större djup. Kursen innehåller tre viktiga praktiska moment: en övning i modellering och lösning av ett designproblem, samt två projektarbeten i vilka storskaliga optimeringsproblem löses med hjälp av dualitetsteori och tekniker som gås igenom vid föreläsningarna. 

Kortfattat innehåll: komplexitet, unimodularitet och konvexitet, minimala uppspännande träd, kappsäcksproblem, lokaliseringsproblem, generaliserad tillordning, handelsresandeproblem, nätverkskonstruktion, övertäckningsproblem. Dekomposition/koordinering, restriktion, projektion, fixering av variabler, omgivningar,(Lagrange)relaxering, linjärisering, linjesökning, koordinerande masterproblem. Plansnittning, Lagrange-heuristiker, kolumngenerering, Dantzig-Wolfe-dekomposition, Benders-dekomposition, lokal sökning, moderna trädsökningsmetoder.

Föreläsningar. En modelleringsövning inkluderande muntlig presentation och diskussion. Två projekt inkluderande muntliga och skriftliga presentationer samt oppositioner.

Se kurshemsidan.

Skriftligt och muntligt redovisade projektuppgifter, opposition; muntlig tentamen för överbetyg.