Beslutsproblem
Optimeringsmetodik kan med framgång användas för att föreslå lösningar till beslutsproblem som är av en kvantitativ natur. Många problem inom schemaläggning och resursallokering, som exempelvis planering av transporter, tidtabelläggning eller personalplanering, kan formuleras som diskreta optimeringsproblem och lösas med metodik anpassad därefter.
En inneboende egenskap hos många sådana problem av praktisk relevans är att de är mycket beräkningskrävande genom att de är NP-svåra, har ett stort antal beslutsvariabler och en matematisk struktur som i praktiken gör dem svårlösta. Denna egenskap behöver ställas i kontrast till att många NP-svåra problem av måttlig storlek i praktiken kan lösas förhållandevis effektivt och snabbt.
Matematiska modeller och lösningsalgoritmer
De första metoderna för att lösa diskreta optimeringsproblem härrör från mitten av 1900-talet, och sedan dess har fronten för hur stora och komplexa problem man kan lösa ständigt flyttats framåt, både tack vare effektivare datorer och - framförallt - tack vare utvecklingen av effektiva och problemstrukturanpassade algoritmer. Att applicera optimeringsmetodik på ett beslutsproblem involverar väsentligen två komponenter, en modell för att beskriva problemet och en algoritm som kan beräkna lösningar till modellen.
För att lösa diskreta problem i form av linjära heltalsmodeller finns effektiva kommersiella verktyg, såsom Gurobi och CPLEX, som fungerar bra för problem upp till en viss komplexitet och storlek. Det finns även etablerade strategier för att angripa vissa typer av problem som de kommersiella lösarna inte klarar att lösa på rimlig tid. För riktigt svåra och outforskade problem krävs att man hittar nya sätt att utnyttja problemets matematiska struktur för att alls kunna beräkna en lösning till problemet. I detta forskningsprojekt arbetar vi med att ta fram matematiska modeller och lösningsalgoritmer för sådana problem inom schemaläggning och resursallokering.
Organisation
Projektet är finansierat av Centrum för industriell informationsteknologi (CENIIT) och genomförs på avdelningen för Optimeringslära, Matematiska institutionen, Linköpings universitet (LiU). Projektledare är Elina Rönnberg, universitetslektor. Nedan beskrivs de delprojekt som är relaterade till projektet.
