DTU-speciale ender i kommercielt software

Et knaldhårdt optimeringsproblem i DTU-studerenes speciale endte som en del af en kommerciel softwarepakke. Skoler og gymnasier sparer penge ved at optimere elevernes valgfag, som klares med tunede algoritmer.

Man skulle ikke tro, det var så vanskeligt at fordele nogle skoleelever på en række valgfag.

Men Sune Høj Kjeldsen og Sune Binzer, som studerer datalogi på DTU, fandt ud af, at problemet i virkeligheden hører til den hårdeste slags nødder: de såkaldte NP-hårde problemer, der er de mest krævende indenfor kompleksitetsanalyse.

I dagligdags termer er et NP-hårdt problem et matematisk problem, som der ikke findes nogen nem løsningsmetode til, hverken i praksis eller teoretisk. I stedet kan man benytte et sjus, som ligger tilstrækkeligt tæt på den bedste løsning. Det er altså ikke den optimale løsning der findes, men en løsning som er god nok i sammenhængen.

Sune Høj Kjeldsen forklarer:

»Manuelt er det svært at finde en god løsning på det. For skoler, som skal fordele elever på valgfag efter deres ønsker, kan det betyde et langt og besværligt stykke manuelt arbejde.«

Men det er heller ikke så nemt at bokse med, rent datalogisk:

»For det første er det ikke et problem, som er beskrevet i litteraturen. Det, der er svært ved det, er, at det er NP-hårdt. Der findes ikke nogen hurtige algoritmer, som kan løse problemet optimalt.«

Problemet skreg på en datalogisk løsning. Det praktiske aspekt i problemstillingen var en vigtig faktor, forklarer Sune Høj Kjeldsen.

»Først lavede vi en grundig analyse af, hvad gymnasierne ønskede. På den måde kunne vi få sat kravene ned. Så lavede vi en matematisk model, som vi kastede ind i en standard solver, der kan løse problemer, for at undersøge hvor svært det var, og fandt at dets kompleksitet var NP-hårdt.«

Tommelfingerregler for viderekomne

Det betød, at de to studerende skulle finde løsnings-algoritmen i såkaldte meta-heuristikker, en slags tommelfingerregler for viderekomne. Det er en samling af forskellige løsningsmetoder, som ifølge Sune Høj Kjeldsen er fleksible, hurtige og finder nær-optimale løsninger.

Det endelige resultat var af en sådan kvalitet, at algoritmen nu er en del af softwarepakken Lectio, et administrationsprogram fra firmaet Macom A/S, som benyttes af skoler og gymnasier.

Den færdige algoritme finder løsninger på elevfordelingen, som er
tæt på optimale løsninger. En fordel ved de studerenes løsning er, at det tager under to minutter at løse problemet på en pc. Det gør, at gymnasier og skoler kan eksperimentere med forskellige parametre, så de kan finde den løsning, der passer dem bedst. Resultatet er ganske simpelt, at skolerne kan bruge færre ressourcer. Eksempelvis kunne en skole i Gladsaxe reducere antallet af såkaldte valgblokke fra syv til fire.

Det praktiske aspekt i specialet har været drivkraften bag indsatsen.

»Det har været et superfedt projekt, og det har været meget lærerigt for os. Det er så forskelligt at arbejde med et praktisk end et teoretisk problem. Specielt fordi problemet kan ændre sig hele tiden, når man snakker med ti skoler, for den næste skole vil have det lidt anderledes. Det skal være generelt nok til, at det kan tilfredsstille alle,« fortæller Sune Høj Kjeldsen, som sammen med sin makker Sune Binzer forsvarer specialet på DTU den 20. august kl 13.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk

Følg forløbet

Kommentarer (0)

Log ind eller opret en konto for at skrive kommentarer

Pressemeddelelser

Affecto Denmark reaches highest Microsoft Partner level

Affecto Denmark, a leading provider of data-driven solutions, has reached the highest level in the Microsoft partner ecosystem: Managed Partner.
22. jun 2017

Innovate your business with Affecto's IoT Explorer Kit

Are you unsure if Internet of Things fits your business strategy?
31. maj 2017

Big Data Lake Summit: Fast and Trusted Insights

If you want to outpace, outsmart and outperform your competition in a digital world, you need trusted data that can be turned into actionable business insights at speed.
24. apr 2017