Annonceinfo

Studerende knækker årtier gammelt matematisk problem

Thomas Dueholm Hansen, ph.d.-studerende ved Aarhus Universitet, har løst et problem i lineær programmering, der har plaget matematikere i årevis.

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

Fakta

POLYEDER

  • Et polyeder er en lukket geometrisk figur sammensat af et antal polygonale flader, som udgør overfladen på et legeme i rummet.
  • Det er typisk meget svært at forestille sig, hvordan et polyeder ser ud i mere end tre dimensioner, hvilket må siges at være en af hovedårsagerne til den manglende forståelse af 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.

Fakta

VIDSTE DU

George B. Dantzig var en amerikansk videnskabsmand. Fra 1966 professor i operationsanalyse og datalogi ved Stanford University, USA.

Dantzig opstillede matematiske modeller til løsning af optimeringsproblemer i matematik, økonomi og teknik; han er kendt som skaberen af simplexmetoden (1947), som er den fundamentale teknik til løsning af optimeringsproblemer, der kan formuleres ved hjælp af lineær programmering.

Kilde: Den Store Danske

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
citatDet 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

Om undersøgelsen

Thomas Dueholms baggrund er inden for algoritmisk spilteori, og de startede arbejdet med at se på såkaldte paritets-spil. Det viste sig senere, at der var tætte forbindelser til lineær programmering.

Thomas Dueholms forskning er foregået i regi af Carlsbergfondets Center for Algorithmic Game Theory

Partnerartikel

Artiklen bringes i samarbejde med: Det Naturvidenskabelige Fakultet, Aarhus Universitet

Seneste artikler fra Det Naturvidenskabelige Fakultet, Aarhus Universitet

Seneste fra Miljø & Naturvidenskab

Annonceinfo

Det læser andre lige nu

Annonceinfo

Annonceinfo

Abonner på vores nyhedsbrev

Når du tilmelder dig, deltager du i konkurrencen om lækre præmier.

Mest sete video

Annonceinfo

Seneste kommentarer