Constraint Programming in the Wild

Recently, I was tasked with solving a technical challenge involving airplane booking. The question focused on selecting alternative seats when a customer's preferred seating gets purchased by another vendor before the customer clicks the "purchase" button. The goal was to choose alternative seating that maintains adjacency if the customer had booked adjacent seats. Additionally, the alternatives needed to stay within the same budget class and include window seating, avoid any seats that are already purchased, and not move more than 10 rows from the initial selection. The ask was to generate all possible alternatives.

A quick check using LLM revealed that this leads to possible nCr(seats_in_booking, number_of_seats) * seats_in_booking! alternatives. This quickly escalates in large airplanes; for a configuration of 4 seats in a 100-seat airplane, there are over 94 million possible arrangements.

Initially, I thought we could generate all possible candidates and then reject those that do not meet the requirements. Essentially, we would permute all seating options and perform early rejection. The code for this approach would look like:

def candidates(initial_arrangement):
    for seat_i in available_seats:
        for seat_i_plus_1 in available_seats:
            # ...
            candidate_arrangement = (seat_i, ...)
            yield candidate_arrangement

def is_valid(arrangement, initial_arrangement):
    # function to check if arrangement is valid
    # and meets all requirements

solution = [
  c for c in candidates(initial_arrangement)
  if is_valid(c, initial_arrangement)
]

But if you stare at this longer, it became clear that this is a classic constraint programming problem. We have a finite selection—e.g., V (seats_in_booking, such as seat_1_of_booking, etc.)— and we need to choose D (possible seats, like A1, B1, and so on). We need to choose such that, they meet some requirements. We can express this as:

seat_i choose from {available seats}
seat_i_plus_1 choose from {available seats}
...

such that,

initial_seat_i.row > seat_i.row - 10
initial_seat_i.row < seat_i.row + 10
initial_seat_i.budget_class = seat_i.budget_class
initial_seat_i.is_window = seat_i.is_window

for pairs of previously adjacent customer seats (initial_seat_pair_j1, initial_seat_pair_j2)
  ~ is_adjacent(seat_j1, seat_j2) = true

Once we express the problem in a mathematical or optimization formulation, we can use industrious-grade libraries. Established libraries can easily solve these problems using various solver and pruning techniques, that are much more memory efficient, and performant (cpu clock time). It also provides the benefit of succinctly defined requirements that are semantically readable in code, making them easily adjustable for future modifications — e.g., through the builder pattern, etc.

meghss

Constraint Programming in the Wild