Sports leagues scheduling. Models, combinatorial properties, and optimization algorithms. (Q2468955)

In this book (originating from a Ph. D. thesis) different aspects of scheduling sports leagues are studied. The basic scheduling problem for a sports league consists in determining a schedule for an even number of teams such that each team plays against each other team a certain number of times. In order to schedule these games, so-called rounds are available, where each team has to play one game in each round. For each round one has to determine which teams play against each other and for each pairing it has to be decided which team is the home team. Additionally, several constraints have to be satisfied. After stating basic problems in the area of sports league scheduling (like round robin tournaments, decomposition approaches) constraints from real world problems (e.g., regions, forbidden rounds for games, fairness constraints, breaks, opponent strenghts) are introduced. Integer linear programming models are presented and compared by some computational experiments. The next chapter deals with the aspect of strength groups and schedules in which for each team the opponents in consecutive rounds belong to different strength groups. Construction schemes are presented for various scenarios based on graph theoretical considerations. Then a very general problem is studied. For each game costs are given which depend on the round in which the game is scheduled. The objective is to find a feasible schedule with minimum total costs. A branch-and-bound algorithm is developed which uses an IP formulation and a branching scheme based on home away pattern sets. Finally, the IP is reformulated as a set partitioning model where the variables correspond to complete schedules for each round. Since its number is exponential, a branch-and-price algorithm is proposed. Computational results are presented for both algorithms.