Kursplan för Storskalig optimering

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

Storskaliga optimeringsproblem har ofta inneboende strukturer som kan utnyttjas för att lösa dessa problem effektivt. Kursen behandlar ett antal grundläggande principer med vars hjälp storskaliga optimeringsproblem kan lösas. Tekniken kallas allmänt dekomposition–koordinering (eller, distribuerad algoritm–konsensus) och utnyttjar bland annat konvexitets- och dualitetsteori. Kursen innehåller viktiga praktiska moment: övningar i modellering och lösning av optimeringsproblem med komplicerande villkor och/eller variabler, samt 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, enkla/svåra optimeringsproblem, linjära optimeringsproblem med heltalsvillkor, unimodularitet, konvexitet. Dekomposition–koordinering, restriktion, relaxering, gränser för optimalvärdet, projektion, fixering av variabler, dualisering, omgivningar, heuristiker, lokala sökmetoder. Lagrangedualitet, subgradientmetoder, (ergodisk) konvergens, återskapande av heltaliga lösningar, Lagrangeheuristiker, plansnittning, kolumngenerering, koordinerande masterproblem, Dantzig–Wolfe-dekomposition, Benders-dekomposition.

Föreläsningar. Modelleringsövningar inkluderande muntlig presentation och diskussion. Projektarbete inkluderande muntliga och skriftliga presentationer samt oppositioner. Handledning. Obligatorisk närvaro vid workshops.

Se kurshemsidan.

Skriftligt och muntligt redovisade projektuppgifter, som även kan ge bonuspoäng vid tentamen; opposition/recension; närvaro och aktivt deltagande vid workshops; en skriftlig tentamen.