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.
