It is never too late to start optimizing

Last week was hackathon day at cVation, a good chance to play around with new tech or ideas. But while it is fun to try new stuff, it is also sometimes fun to revisit something old. I had the chance to do both as I used the Group Seat Reservation Knapsack Problem (GSR-KP), to introduce a small team to the wonderful world of combinatorial optimization.

The GSR-KP considers a train with a certain number of seats (assumed to be on a single line), to be filled by reservation requests each having several persons travelling together for a pre-determined part of the train’s route. All members of the reservation must be placed adjacently and cannot change seats while travelling.

The goal of the problem is to choose which reservations to include, such that the utilization of the train (determined as occupied seats per station) is as high as possible.

To solve the problem, we used LocalSolver, a mathematical optimization solver based on local search and constraint programming paradigms.

During the hackathon we had time to implement two different models and pit them against each other to see which model would give the best results on instances from the original research paper.

The trickiest aspect of modelling the GSR-KP is that the reservations are not allowed to share seats within the train (obviously), so determining whether a set of reservations fit inside the train without overlapping is not trivial. An aspect of constraint programming is that there are multiple ways a problem can be modelled.

The first model represented the fitting problem by assigning seats to all included reservations and imposed the constraint that no included reservation could share seats or have seats outside the train.

The second considered the reservations in sequence, such that each reservation would be placed as far to the back of the train as possible without overlapping with the previous reservations of the sequence. This allowed the entire problem to modeled as permutations of a subset of the reservations, which happens to be exactly how the LocalSolver List variable works.

The model started as ideas on the whiteboard and was quickly implemented in LocalSolvers api. See both below.

I wish I could say that my previous experience in optimization would lead me to have the superior model design, but unfortunately that was not the case. I take comfort in that my co-workers seemed to genuinely enjoy themselves working with mathematical programming (and beating me). It is never too late to start optimizing.

If this has piqued your interest, the GSR-KP is described in detail in “The Off-Line Group Seat Reservation Problem”, a paper I co-authored some 10 years ago.

The problem instances can be found here.