Meddelanden från Åbo Akademi
   | Meddelanden från Åbo Akademi |
   | nr 1 | 21.1.2011 |
Meddelandens pärm

Tänk dig att ett problem har en mängd lösningar som motsvarar antalet atomer i tio miljoner universum och att du ska hitta den bästa metoden att lösa det. Galet? Kanske. Omöjligt? Bara nästan.

Ny modell för att lösa enorma problem

***BILD***
Håller farten uppe. Doktorand Axel Nyberg och professor Tapio Westerlund har arbetat fram en förbättrad modell för att lösa kvadratiska tillämpningsproblem men ska ännu göra förbättringar på prototypen.

Det är ett målmedvetet arbete som fört doktorand Axel Nyberg och professor Tapio Westerlund vid spetsforskningsenheten i optimering och systemteknik fram till en ny och förbättrad modell som löser kvadratiska tilldelningsproblem till globalt optimum. Det måste det vara. Att göra det på ren tur är som att vinna sju rätt på lotto femtio gånger i rad.

– Det är skönt i och med att det är något vi jobbat med ganska länge. Det var bara för någon vecka sen som jag konstaterade att det här problemet är hopplöst. Jag trodde vi hade löst det då jag satte datorn att snurra över helgen, men när jag kom tillbaks till jobbet var vi inte ens nära. Sedan med den här modellen satte jag bara igång datorn på fredagen och tänkte inte mera på det förrän på måndagen då jag såg att det hade lösts på fyra och en halv timme, säger Axel Nyberg.

– Men det är roligt. Det här är den första prototypen av den här typen av problem som vi har löst så det går säkert ännu att göra förbättringar.

Det är ingen liten prestation att lösa nya problem inom kvadratiska tillämpningsproblem, på engelska kallat Quadratic Assignment Problem (QAP). Kvadratiska tilldelningsproblem introducerades ursprungligen 1957 och sysselsätter ännu ett mycket stort antal forskare runtom i världen. Det finns en hemsida, QAPLIB, som ger information om nya metoder och upprätthåller ett bibliotek med testproblem där forskare kan försöka testa sina modeller.

Nybergs och Westerlunds modell har ännu inte publicerats, men professor Peter Hahn vid University of Pennsylvania som upprätthåller sidan kommer att införa lösningarna på QAPLIB så småningom.

– Det är så många som jobbat med de här problemen och det finns en massa formuleringar av dem, så de olösta problemen som finns på QAPLIB blir allt svårare att lösa, säger Tapio Westerlund.

– Men vi har faktiskt redan lyckats lösa fyra av de återstående problemen till globalt optimum – något som alltså ingen tidigare lyckats med.

Ofattbar bredd på problemen
Kvadratiska tilldelningsproblem hör till de mest utmanande och flitigast studerade problemen inom kombinatorisk optimering och har mycket breda tillämpningsområden. QAP är matematiska modeller som kan användas för att hitta de bästa lösningarna för en mängd olika problemställningar inom till exempel logistik eller för att planera var olika komponenter ska sitta på ett kretskort så att det sammanlagda avståndet mellan komponenterna blir så litet som möjligt.

Och en hel del annat.

– Sådana här modeller kan också användas i till exempel sjukhus. Då man vet hur många av patienterna som ska vidare till olika avdelningar kan man räkna ut var de olika avdelningarna ska placeras så man slipper skuffa runt patienterna så mycket, säger Axel Nyberg.

Det låter rätt simpelt men när man flyttar upp problemet på en abstrakt nivå och skapar en matematisk modell som innehåller alla lösningar blir bredden på problemen enorm. Antalet möjliga kombinationer är så stort att man inte kan gå igenom alla alternativ.

– Små problem med få variabler löser du hur enkelt som helst med dagens datorer. Men så fort du ökar antalet variabler förstoras problemet, säger Axel Nyberg.

Smidiga formuleringar
För att göra de komplexa modellerna praktiskt användbara gäller det att få dem i sådan form att de kan lösas effektivt med en eller flera datorer. Metoden är att arbeta fram förbättrade matematiska formuleringar och förenkla problemen genom att ta fram övre och undre gränser i jakten på den optimala lösningen. På så sätt kan man utesluta lösningar som inte är möjliga.

Tapio Westerlund säger att det tagit flera dagar att lösa vissa problem i QAPLIB och nämner som exempel ett fall där kanadensiska och amerikanska forskare kopplat samman tusen datorer för att i parallell form lösa ett av problemen... på sju dygn.

Den nya modellen bygger på en smidigare formulering.

– Mycket av forskningen inom optimeringsområdet går ut på att söka matematiskt stringenta modeller. Men det tar ofta lång tid att hitta sådana modellformer med vilka man snabbt och effektivt kan få fram de garanterat bästa lösningarna, säger Tapio Westerlund.

– Att lösa stora kombinatoriska problem är mycket utmanande. Ett av de problem som vi lyckats lösa innehåller faktiskt så många kombinationer att det vi är ute efter i princip motsvarar att söka en atom i tio miljoner universa. Så det är lite som att söka en nål i en höstack... men större. Det vi lyckats göra är att utesluta vissa lösningar och visa att det finns multipla lösningar. Så i stället för att söka en atom i tio miljoner universa söker vi nu en himlakropp av jordens storlek i samma sökrymd. Trots reduktionen är antalet möjliga lösningar fortfarande mycket stort – ett 38-siffrigt tal – men tack vare reduktionen har vi lyckats säkerställa att vår slutliga lösning faktiskt är den allra bästa.

TEXT & FOTO: Nicklas Hägen