Detaljerad information för diarienr 2005-929  
 
 
Besl. instans: NT
Ämnesområde: Matematik & teknisk matematik
Beslutsdat: 2005-11-10
Namn: Linusson, Svante
Titel: Professor Kön: Man
Univ./Institution: Kungliga Tekniska Högskolan - Skolan för teknikvetenskap, SCI
Projekttitel: Kombinatoriska optimeringsproblem med slumpvikter
Project title: Combinatorial Optimization Problems with Random Weights
Värdhögskola: Kungl Tekniska Högskolan
SCB-klassificering: Diskret matematik, Matematisk statistik, Optimeringslära, systemteori
Beviljat(SEK): Bidragsform/Finansieringskälla   2006 2007 2008
  Projektbidrag/
Vetenskapsrådet, naturvetenskaplig-teknikvetenskaplig forskning
  270000 270000 270000
Beskrivning: Jag vill utföra analyser av vissa optimeringsproblem när de ingående data inte är kända från början utan är slumpvariabler. Antag till exempel att vi har n arbetsuppgifter som skall göras och n maskiner som kan utföra dessa uppgifter och vi låter a(i,j) vara kostnaden för att maskin nummer i utför arbetsuppgift j. Dessa tal skrivs upp i en matris. Ett välstuderat matematiskt optimeringsproblem är att fördela arbetsuppgifterna till maskinerna så att den totala kostnaden blir så liten som möjligt. Det handlar om att matcha ihop arbetsuppgifter med maskiner. Ett annat sätt att visualisera problemet är t.ex. då n=8 med att tänka på ett schackbräde där det står tal a(i,j) på varje ruta på brädet. Att ställa ut ett torn på ruta (i,j) tolkas då som maskin i skall göra uppgift j. Ställer vi 8 torn som inte kan slå varandra på brädet kan det ses som en fullständig matchning av maskiner och arbetsuppgifter. Sedan två decennier har forskare funderat på vad som händer om man inte känner till talen a(i,j) exakt i förväg utan bara har uppskattningar inom ett visst interval eller med en viss sannolikhetsfördelning. Problemet som jag studerat är att försöka avgöra hur stort det förväntade värdet på den minsta totalsumman blir, det vill säga det genomsnittliga värdet av optimum om man gör många experiment. En fascinerande förmodan (=kvalificerad gissning) av fysikern Parisi säger att i det fallet då slumpvariablerna har en viss naturlig fördelning (exponentialfördelningen, som till exempel modellerar utstrålningen av radioaktiva partiklar), så är det förväntade värdet exakt 1+1/4+1/9+1/16+...+1/n^2. En så enkel formel för ett rätt krångligt formulerat problem väcker alltid matematikers intresse. Problemet med stokastiska (slumpmässiga) matchningar har studerats av många forskare från flera olika discipliner: fysik, matematik, optimeringslära och matematisk statistik. Johan Wästlund och jag lyckades visa denna förmodan av Parisi (och mycket annat i samband med detta) våren 2003, för vilket vi tilldelades Wallmarkska priset av KVA 2005. Våra resultat är inte tillämpade på så sätt att det går att bättre optimera problemet. Man kan snarare se det som att vi bevisat att det lönar sig att optimera problemet. Detta är grundforskning och min drivkraft är att bättre förstå det vackra samspelet mellan kombinatorik, sannolikhetslära och optimering. Jag har fortsatt att undersöka närliggande frågor efter detta och jag ansöker nu om forskningsmedel för att fortsätta forska kring mer allmänna problem i denna riktning. Det går att visa många intressanta sanningar om t.ex. sannolikheten att en viss ruta är med i den minimala matchningen. Det har genom detta bland annat öppnat sig en ny väg för att bevisa Parisis förmodan och andra satser på ett mycket kortare sätt under förutsättning att man kan uppnå tillräcklig förståelse om kopplingen mellan detta problem och ett annat där sannolikheterna är enkla att räkna ut (och de är faktiskt lika, men beviset bygger för närvarande på tidigare resultat). Matematiker nöjer sig sällan med att något är bevisat, man fortsätter att söka bättre bevis som skall ge ökad förståelse och insikt. Vi kan också från våra gamla och nya resultat återbevisa och förstärka redan kända satser om t.ex. längden på minimala stigen mellan två noder i den fullständiga grafen. Man kan utifrån tidigare arbeten göra många ytterligare förmodanden om betydligt generellare optimeringsproblem som skulle ge metoder för att räkna ut den minimala kostnaden för ett maximalt flöde för vissa parametrar. Det kan (om förmodandena är sanna) också ge ny insikt om det så kallade handelsresandes problem med slumpavstånd mellan städerna. Handelsresandes problem är ett av de mesta kända och viktigaste optimeringsproblemen. I populärversionen är det en handelsresande som skall besöka vissa städer och som vill göra det med så kort totalrutt som möjligt.