Optimisation of Flight Compositions for Golf Trips

We present a binary integer programming model for a Golf Trip Flight Composition Problem (GTFCP), which addresses the challenge of assigning participants to golf flights across multiple days while maximising the diversity of player pairings. The problem incorporates practical constraints including flight capacity limits, couple preferences, and player incompatibilities. We propose an optimised formulation that reduces the variable and constraint count compared to a naive linearization approach, achieved through the use of aggregated togetherness variables and a bidirectional coupling mechanism. We evaluate six solution methods - an exact GLPK (GNU Linear Programming Kit) solver, a deterministic greedy algorithm, a randomised greedy algorithm, local search, simulated annealing, and a genetic algorithm implemented in R - across a structured benchmark comprising 32 test instances in six experimental series. The model finds applications in tournament organisation, team-building events, and social scheduling where balanced interpersonal interaction is desired.