Det er aldrig for sent at starte med at optimere

Flere gange om året afholder vi hackathons hvor vi i teams dykker ned i præcis de emner, udviklerne finder interessante. Her kan du læse et lille take-away fra hvad Tommy Biangslev Clausen tog med sig fra seneste hackathon dag.

Tommy Biangslev Clausen
Software engineer

Sidste fredag var det hackathon-dag hos cVation, en god mulighed for at lege med nye teknologier og ideer. Men selvom det er sjovt at prøve nye ting, er det også nogle gange sjovt at vende tilbage til noget ældre. Jeg havde muligheden for at gøre begge dele, da jeg brugte ”The Group Seat Reservation Knapsack Problem” (GSR-KP) til at introducere en lille gruppe for den kombinatoriske optimerings vidunderlige verden.


I GSR-KP betragter vi en togrejse med et antal stop undervejs og grupper af rejsende som ønsker at booke plads på en del af togets rejse. Rejsende fra samme gruppe skal sidde ved siden af hinanden og må ikke skifte plads undervejs på deres rejse. Toget har et fast antal sæder, så ikke alle reservationer kan forventes at blive opfyldt.

Målet med problemet er at udnytte togets kapacitet (talt som bookede sæder pr. station) så godt som muligt. GSR-KP er i høj grad et kombinatorisk problem og den sværeste del af modelleringen er at fange at reservationerne ikke må dele sæder undervejs på rejsen. Det er ikke helt trivielt at bestemme om et sæt af reservationer rent faktisk kan være i toget uden overlappende sæder undervejs. For at løse problemet brugte vi LocalSolver, en solver til matematisk programmering som er baseret på constraint programming og lokalsøgning. Constraint programming udmærker sig ved muligheden for at opbygge matematiske modeller på en naturlig (logisk) måde, og der kan derfor være mange forskellige måder at modellere et problem på.

Til hackaton havde vi tid til at formulere to forskellige modeller og sætte dem op mod hinanden, for at se hvilken model som gav de bedste resultater på forskellige probleminstanser fra litteraturen.

Den første model repræsenterede pladsproblemet ved at tildele sæder til alle de valgte reservationer og indføre de begrænsninger at alle sæder skal være indenfor toget og ingen reservationer kan dele sæder undervejs.

Den anden model betragtede reservationerne i sekvens, sådan at alle reservationer bliver placeret så langt tilbage i toget som muligt, uden at overlappe med tidligere reservationer i sekvensen. På den måde bliver problemet et spørgsmål om at udvælge en delmængde af alle reservationer og finde en rette permutation imellem dem. Det er tilfældigvis sådan LocalSolvers List-variabel virker, så vi kunne modellere problemet med en enkelt variabel og nogle rekursive udtryk til at beskrive reservationernes indbyrdes placering i toget.


Modellen startede som ideer på whiteboardet og blev hurtigt implementeret i LocalSolvers api. Se begge dele nedenfor.

Jeg ville gerne kunne sige at min tidligere erfaring med optimering gjorde at min model klarede sig markant bedre end den anden, men det var desværre ikke tilfældet.

De to modeller klarede sig bedst på nogenlunde lige mange instanser og det gav en skarp konkurrence i løbet af dagen. Jeg trøster mig med at mine kolleger havde en spændende dag med kombinatorisk optimering (og med at besejre mig). Det er aldrig for sent at starte med at optimere...


Hvis dette har vagt din interesse, kan du læse mere om GSR-KP i ”The Off-line Group Seat Reservation Problem”, en videnskabelig artikel jeg var medforfatter på under min studietid. De probleminstanser vi har brugt (og som også er brugt i artiklen) er tilgængelige på David Pisingers hjemmeside her.

I tvivl om næste skridt?

Vi kan hjælpe jer med at afklare jeres forretningsidé eller teknologibehov. Eller yde værdifuld sparring omkring jeres nuværende IT situation og vejen videre.

Jeg vil gerne booke sparring