Ph.d.-studerende Thomas Dueholm Hansen har i samarbejde med forskere fra München og Tel Aviv vist, at der ikke findes en hurtig variant af Dantzigs simplex-algoritme. Det har man ellers ment i årevis. (Foto: Aarhus Universitet.)

Thomas Dueholm har lavet et resultat i verdensklasse.

Det mener hans vejleder professor Peter Bro Miltersen på Datalogisk Institut, Aarhus Universitet. Et resultat der allerede nu diskuteres på kendte matematik-blogs.

Thomas Dueholm Hansen forklarer om sin forskning:

»Man har antaget, at der findes en hurtig variant af Dantzigs såkaldte simplex-algoritme, men man har endnu ikke kunnet bevise den. Vi viser, at varianten ikke er hurtigere,« siger Thomas Dueholm Hansen.

Thomas Dueholm har i sin forskning samarbejdet med kolleger fra München og Tel Aviv.

Det største uløste problem indenfor lineær programmering

Thomas Dueholm Hansen forklarer problemstillingen således:

Forestil dig at du har et polyeder, f.eks. en tolv-sidet terning, og at du ønsker at finde hjørnet længst mod øst.

Dette problem kan generaliseres til højere dimensioner, og er kendt under navnet lineær programmering.

Dantzig viste i 1947, hvordan en løsning kan findes ved at starte fra et vilkårligt hjørne og gentagne gange bevæge sig fra hjørne til hjørne, langs en kant, i den ønskede retning. I dag er der fundet adskillige algoritmer til at løse problemet, og de hurtigste programmer kan håndtere polyedre i millioner af dimensioner med millioner af "sider" (facetter).

For at løse så store lineære programmer er det nødvendigt at finde en sti langs kanterne i polyederet, der ikke bevæger sig gennem for mange hjørner.

Tidligere har man formodet, at der eksisterer en variant af Dantzig's simplex-algoritme, der altid opfylder dette, men hidtil har ingen kunnet bevise denne påstand.

Indtil for nylig var en stærk kandidat til en sådan variant altid at vælge en tilfældig forbedrende kant, idet det formodedes, at en kort sti ville blive fundet med høj sandsynlighed.

»Vi viser, at det desværre ikke er tilfældet. Det har vi gjort ved at konstruere lineære programmer, hvor denne variant af simplex-algoritmen bevæger sig gennem et antal hjørner, der næsten er eksponentielt i antallet af facetter,« siger Thomas Dueholm Hansen.

Positivt negativt resultat

Selvom resultatet er af negativ karakter, er resultat meget positivt for Thomas Dueholm Hansen og forskergruppen indenfor matematisk datalogi på Datalogisk Institut,

»Det er fantastisk, at det er lykkedes os at løse et fundamentalt problem, der er forblevet åbent gennem årtier i et så aktivt felt. På trods af at vores resultat er af negativ karakter, giver det en større forståelse af lineær programmering, der forhåbentligt på sigt vil lede til forbedrede algoritmer,« siger Thomas Dueholm Hansen.

Fantastisk start på forskerkarriere

Det er fantastisk, at det er lykkedes os at løse et fundamentalt problem, der er forblevet åbent gennem årtier i et så aktivt felt.

- Thomas Dueholm Hansen

Lineær programmering er af fundamental betydning for teoretisk datalogi og matematisk optimering.

Der er skrevet tusindvis af artikler om emnet, der findes tilsvarende mange industrielle anvendelser, og alle bachelorstuderende i datalogi og operationsanalyse undervises i emnet.

Vejleder Peter Bro Miltersen udtrykker stor respekt for resultatet;

»I 10 år har jeg på mit kursus i lineær programmering sagt, at dette var et af de største uløste problemer indenfor lineær programmering. Det er meget tilfredsstillende og også ret utroligt, at det nu bliver løst af en af mine studerende,« understreger Peter Bro Miltersen.

»Med dette resultat har jeg fået en fantastisk start på en forskerkarriere. Det er en stor fordel at have løst et problem som andre inden for mit felt kender til og er interesserede i,« siger Thomas Dueholm Hansen.

Artiklen er lavet i samarbejde med Det Naturvidenskabelige Fakultet, Aarhus Universitet