Hybrid Sökning och Deklarativ Sökning

Tidsperiod:

1 januari 2026 – 31 december 2029

Projektledare:

Pierre Flener

Finansiär:

Vetenskapsrådet

Bidragstyp:

Projektbidrag

Budget:

4 100 000 SEK

Ett optimeringsproblem söker värden på obekanta variabler givet bestämda villkor på dem samt en funktion över dem som skall max/minimeras. T.ex. i handelsresandeproblemet är rutten obekant, villkoret är att varje stad besöks exakt en gång och ruttens längd skall minimeras.Viktiga optimeringsproblem är schemaläggning av vårdpersonal för att uppfylla kollektivavtal och personliga önskningar samt minimera kostnader, att planera produktion givet tillgång och efterfrågan så att utsläpp minimeras, osv.Global sökning görs oftast av generella program (lösare). De ges en problemspecifikation (modell) och garanterar att man till slut hittar en optimal lösning. De är dock ofta för långsamma i praktiken. Med lokal sökning ger man upp garantin av optimalitet: man börjar med en gissning och genomför successivt små förändringar av gissningen enligt någon strategi, i hopp om att hitta en optimal lösning. Lokal sökning är välbeprövad och används ofta i praktiken.Traditionellt kräver lokal sökning att man utvecklar ett komplext program för varje individuellt problem, vilket ger bristande kodåteranvändning. Det är också svårt att uppdatera koden när problemet förändras och att prova varianter av strategin.Forskning har utvecklat lokalsökningslösare. De ges en modell, precis som vid global sökning. De kräver ofta att man programmerar en speciell sökstrategi men kan innebära mycket kortare utvecklingstid och även lösningstid, eftersom skräddarsydd lokalsökning är svårt att få korrekt och välfungerande.Målet är att finna principer för lokalsökningslösare som är lättare att använda samt ger kortare lösningstid och lösningar av bättre kvalité:1. Den lokala sökningen kombineras automatiskt med global sökning på ett smart sätt.2. Strategin beskrivs med en deklarativ specifikation snarare än med ett program. Det skulle leda till att bättre beslut kan fattas snabbare, vilket kan minska slöseriet av resurser som råvaror och tid – ett steg mot en grönare och lyckligare planet.