Diskret modellering

Kursen är indelad i två moment.

Moment 1 (4,5 hp): Teori.

Momentet behandlar teorin för diskret modellering, från problemställning och val av modell, via specifik modellformulering och implementation, till utvärdering av modellens lämplighet och effektivitet.

Momentet inleds med allmän teori för uppställande av heltalsprogram utifrån en problembeskrivning, och allmän teori för SAT-formuleringar av optimerings- och beslutsproblem. I anslutning till detta behandlas komplexitetsteori och den generella teorin för polynomiell reduktion från ett problem till ett annat. Heltalsformuleringar och SAT-formuleringar sätts sedan i relation till olika klasser av grafmodeller, särskilt flödesproblem, matchningar, kortaste vägen, graffärgning, och handelsresandeproblemet. Både exakta och heuristiska metoder studeras med avseende på effektivitet. Därefter studeras storskaliga konkreta exempel på tillämpad diskret modellering, och en introduktion till informationssökning inom området diskret modellering ges. Teorimomentet avslutas med en introduktion till simulering med hjälp av slumpmässiga scenarier.

Moment 2 (3 hp): Laborationer.

Momentet behandlar implementation av diskreta modeller, och jämförelser mellan olika formuleringar vad gäller deras beräkningsmässiga effektivitet. Vidare implementeras simuleringsmetoder för diskreta modeller.