Referee assignment in sport leagues

Abstract. Optimization in sports is a field of increasing interest. Com-binatorial optimization techniques have been applied e.g. to game schedul-ing and playoff elimination. A common problem usually found in sports management is the assignment of referees to games already scheduled. There are a number of rules and objectives that should be taken into ac-count when referees are assigned to games. We address a simplified ver-sion of a referee assignment problem common to many amateur leagues of sports such as soccer, baseball, and basketball. The problem is for-mulated by integer programming and its decision version is proved to be NP-complete. To tackle real-life large instances of the referee assignment problem, we propose a three-phase heuristic approach based on a con-structive procedure, a repair heuristic to make solutions feasible, and a local search heuristic to improve feasible solutions. Numerical results on realistic instances are presented and discussed.