Thomas Dueholm Hansen har påvist, at et klassisk programmeringsproblem ikke kan løses på den måde, man antog. Datalogi-forskere verden over kan nu lede andre steder efter en løsning.

”Kan en randomiseret implementation af simplex-algoritmen løse lineære programmer i polynomiel tid?”

Næppe et spørgsmål som giver mening for andre end folk med god forstand på teoretisk datalogi. Men stiller man det til en international forsker med fingeren på pulsen inden for lineær programmering, vil navnet Thomas Dueholm Hansen sandsynligvis poppe op. Han har nemlig påvist, at svaret er ’nej’.

Den 28-årige ph.d.-prisvinder forsøger via en Skype-forbindelse fra Tel Aviv at gøre begribeligt, hvad det komplicerede spørgsmål dækker over:

– En algoritme er en fremgangsmåde for, hvordan man sætter en computer til at løse et problem. Og hvis problemet handler om en form for optimering, hvor noget skal minimeres, samtidig med at bestemte betingelser er opfyldt, så taler vi om algoritmer inden for lineær programmering, forklarer Thomas Dueholm Hansen.

Særlig metode aflivet

Allerede i 1947 lancerede den amerikanske matematiker George Dantzig sin såkaldte simplex-metode som en grundlæggende teknik til løsning af optimeringsproblemer, der kan formuleres ved hjælp af lineær programmering. Metoden har stor betydning i dag, hvor eksempelvis DSB trækker på den, når de udarbejder køreplaner.

Dantzig foreslog selv, at visse beregningsprocesser kunne foregå ud fra et tilfældighedsprincip, altså med en såkaldt randomiseret implementation (anvendelse) af algoritmen. Men helt frem til Thomas Dueholm Hansens banebrydende resultat i 2011 har det været et åbent spørgsmål, hvor effektiv den fremgangsmåde faktisk er.

– En effektiv algoritme skal køre i polynomiel tid. Det betyder groft sagt, at den tid, det tager at lave beregninger for at løse et problem, altid skal stå i et rimeligt forhold til den tid, det kræver at beskrive problemet og indsamle data, forklarer han.

Dataloger havde håbet, at den randomiserede implementation var effektiv, men de kunne ikke påvise det. Nu har Thomas Dueholm Hansen sammen med to kollegaer fra Israel og Tyskland vist, at det ikke er tilfældet.

Fra Tel Aviv til Stanford

Forskerne knækkede nødden med en ny synsvinkel. Mens andre har betragtet lineær programmering ud fra et geometrisk synspunkt, tog Thomas Dueholm Hansen udgangspunkt i såkaldte Markovbeslutningsprocesser.

– Selve vores konstruktion er nok så indviklet, at den ikke kommer til at indgå i almindelige datalogiforelæsninger, men resultatet er så simpelt, at det nok skal blive nævnt i forelæsninger verden over. Det er nemlig også rimelig fundamentalt, vurderer han. Med et toårigt postdoc-stipendium fra Det Frie Forskningsråd | Natur og Univers viderefører han nu sin grundforskning, først i Tel Aviv og derefter Stanford i Californien.