Faglig innhold

Kurset presenterer teori og praksis knyttet til deterministiske algoritmer for å lokalisere globalt optimum for såkalte NP-hard optimaliseringsproblemer. Tilbakevendende temaer og metoder er (benytter engelske termer for økt treffsikkerhet i forhold til temaer) konvekse relakseringer, branch-and-bound, cutting planes, outer approximation og primal-dual tilnærminger. Fokus er på forbindelsen mellom ulike metoder. Utover i kurset vil disse metodene bli benyttet og illustrert til utvikling av algoritmer for lineære blandet heltallsproblemer, konvekse blandet heltallsproblemer, ikke-konvekse problemer, og ikke-konvekse blandet heltallsproblemer. Bredden i anvendelser for disse optimaliseringsformuleringene innen ingeniør-anvendelser vil også bli fremhevet.

Læringsutbytte

Kunnskaper:

Emnet vil gi en presentasjon av følgende temaer:

• Introduksjon til ulike klasser av optimaliseringsproblemer (Linær Programmering - LP, Blandet-Heltalls Linær Programmering - MILP, Konveks Ikke-lineær Programmering, Blandet-Heltalls Konveks Programmering - MICP, Ikke-konveks Ikke-lineær Programmering - NLP, og Ikke-konveks Blandet-Heltalls Programmering - MINLP
• Motivasjon for Global Optimalisering
• Bakgrunns-konsepter: Konveks Optimalisering, Optimalitets-kriterier for NLP problemer, Dualitets-teori og Beregnings-kompleksitet
• Metoder for å oppnå Global Informasjon: Intervall-analyse, Konvekse og Konkave Relaksasjoner
• MILP - Problem-formulering og Branch-and Bound baserte løsningsalgoritmer
• NLP - Løsning ved bruk av romlige Branch-and-Bound algoritmer
• MICP - Løsning ved bruk av Outer Approximation og Generalized Benders Decomposition
• MINLP - Løsning ved bruk av Branch-and-Bound baserte algoritmer, Ikke-konveks Generalized Benders Decomposition og Ikke-konveks Outer Approximation

Ferdigheter:

• Ha en forståelse av hvordan optimaliseringsproblemer kan formuleres og løses på en hensiktsmessig måte ved bruk av kommersiell programvare (for eksempel JuMP i Julia, eller GAMS)
• Ha en oversikt over funksjonaliteten til en rekke state-of-the-art algoritmer for å løse diverse problem-klasser. Vite hvilken algoritme som er passende for ulike typer av optimaliserings-problemer

Generell Kompetanse:

• Lære hvordan man kan benytte beregningsverktøy som støtte til å ta beslutninger for en rekke ingeniør-problemer

Læringsformer og aktiviteter

En hybrid læringsform vil bli benyttet hvor en betydelig grad av selv-studium kombineres med Q&A kollokvier med en eller flere faglærere og studenter som følger emnet. Som nevnt nedenfor vil videoer fra et liknende kurs ved MIT ble gjort tilgjengelig sammen med en lærebok og et betydelig sett av lysbilder som forklarer detaljene i pensum. Emnet vil også ha øvingsoppgaver med løsningsforslag.

Emnet undervises annethvert år, fra høst 2025.

Anbefalte forkunnskaper

Et introduksjonskurs i lineær optimalisering og et tilsvarende kurs i ikke-lineær optimalisering vil gi studenter en god start. Et introduksjonskurs i reell analyse ville være enda bedre, men forventes ikke av en gjennomsnitts student i dette emnet.

Forkunnskapskrav

Ingen

Kursmateriell

• Paul I. Barton: Mixed-Integer and Nonconvex Optimization, Department of Chemical Engineering, Massachusetts Institute of Technology (MIT), Cambridge, MA 02139, USA, 2011 (Lærebok)
• Paul I. Barton: Videoer fra forelesninger ved MIT, Våren 2021
• Sett med lysbilder som er knyttet til detaljer i læreboka