Diskret modellering 7,5 hp

Om kursen

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 matchningar och handelsresandeproblemet. Därutöver studeras Hamiltoncykler, Eulercykler, tillordningsproblem och stabila matchningar.
Både exakta och heuristiska metoder studeras med avseende på effektivitet. Vidare behandlas artificiell intelligens genom en kort introduktion till genetiska algoritmer, särskilt för handelsresandeproblemet.
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. För att hantera problem där lösning till optimalitet inte är genomförbar implementeras simuleringsmetoder för diskreta modeller. Vidare behandlas metoder från området artificiell intelligens, som genetiska algoritmer och simulated annealing.