DTU-speciale ender i kommercielt software

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.