Heltalsprogrammering

Kursen är indelad i två modulerModul 1 (6,0 hp): Matematisk teori för heltalsoptimering.  I modulen ges fördjupade kunskaper om optimering. Särskild vikt läggs vid heltalsprograms egenskaper och tekniker för att lösa dessa. Metoder som behandlas är dynamisk programmering, trädsökning och plansnittning.  Olika familjer av plansnitt studeras och används både för att lösa och ge starkare formuleringar av heltalsproblem. Heuristiker för att hitta bra övre och undre gränser för målfunktionen behandlas, till exempel giriga tekniker samt linjärprograms- eller Lagrangerelaxation. Begreppen konvext hölje och fullständig unimodularitet behandlas. En introduktion till komplexitetsteori ges med exempel på problem i olika komplexitetsklasserModul 2 (1,5 hp): Laborationer.  I modulen används datorstöd för att implementera och tillämpa någon teknik för heltalsoptimering.