CONSTELLATION
Sport Schedule Constraints
Glossary: Division, League or Group
Glossary: Schedule SchemeCode
Glossary: Balanced Round Robin
Sport Schedule Requirements
Glossary: CONSTELLATION GRAPH
XY binding-constraints - Home-away constraints
Types of constrained teams in Constellation Graph
Constraints and preferences
CDL
Scheduling (production processes)
Advanced planning and scheduling
Sport Schedule Constraints  
Glossary > Sport Schedule Constraints
CONSTELLATION - TERMINOLOGY and NAMING CONVENTIONS by John Jan Popovic


Glossary > Sport Schedule Constraints
John Backus described the work of primitive coding—vanished, replaced by the magic of a system that let people communicate their wants and needs directly to the machine, in their own language.
--------------------------------------------------------------------------------------------------------
The main purpose of this paper is to clarify things, to eliminate ambiguities and misunderstandings in the natural language. The specification document must be complete, accurate and easily readable. This glossary explains some of the main terms, which occur more frequently at work preparing their calendars, including terms used in the system CONSTELLATION.

Many concepts were too vague and not well structured and ill-defined. We applied a rigid formalism during the lexical definition of glossary, having a conception of mathematics as a tool of interpretation of reality.
-------------------------------------------------------------------------------------------------

A clear separation of concerns emerges: we might call them the mathematical concerns about correctness and the engineering concerns about efficiency.
... the discovery how to separate them rigorously in our thinking is relatively young, and even when aware of this possibility, we often fall back into our old bad habits.
The purpose of abstraction is not to be vague, but to create a new semantic level in which one can be absolutely precise.
Correctness Concerns and, Among Other Things, Why They are Resented.
E. W. Dijkstra

On a regular basis sport event coordinators and organizers have a very hard time to not talk in terms of implementation details about a solution. They mostly lack shared concepts, methodology, and terminology.

We address the problem of scheduling the matches of a round robin competition for a sport league.
--------------------------------------------------------------------------------------
......................................................................................................................
Sport Event Scheduling
......................................................................................................................
A league/division comprises of even number n of teams, which compete in (n-1) consecutive rounds. Each team must play with each other.
Matches take place at the home stadium of one of the two competing teams.
Home and away games should be alternated as much as possible.

The problem is find a schedule scheme that minimizes the number of home/away breaks and satisfies a number of other binding constraints.
*) We call break, [after de Werra (1980) "break of HAHA rhythm" ], when a team plays two consecutive rounds at home, or two consecutive rounds away.

Constraints are split into hard (requirements) and soft ones (wishes): Hard constraints must necessarily be satisfied by the solution, soft ones instead can be violated and they contribute to the objective function.
For all the types of constraints defined, each single constraint can be declared either hard or soft. The soft ones are associated with an integer-valued positive penalty, and the sum of all penalties determines the objective function.
The hard ones are strictly enforced during the construction of the solution.
We have two groups of constraints. The first group, that we call ordinary constraints, regards general constraints on all teams. The second group of constraints are related to a grouping of the teams based on their strength, and we call them special constraints.

......................................................................................................................
2. Constraints
......................................................................................................................
=============================================
CONSTRAINTS
Constraints are split into hard (requirements) and soft ones (wishes):
Hard constraints must necessarily be satisfied by the solution, soft ones instead can be violated and they contribute to the objective_function.
For all the types of constraints defined below, each single constraint can be declared either hard or soft.
The soft ones are associated with an integer-valued positive penalty, and the sum of all penalties determines the objective_function. The hard ones are strictly enforced during the construction of the solution.
We have two groups of constraints. The first group, that we call ordinary constraints, regards general constraints on all teams. The second group of constraints are related to a grouping of the teams based on their strength, and we call them special constraints.

I. ORDINARY Constraints
Ordinary constraints we consider are of the following types (see also Schreuder, 1993).
Please note that ordinary constraints may be hard (requirements) or soft ones (wishes).

I.a Complementarity & team-binding: Teams t1 and t2 must have complementary schedules
(i.e. when t1 plays home t2 plays away, and vice versa).

I.b Non simultaneity & team-binding: Three or more teams t1, t2, and t3,... cannot be simultaneously in the same location
(i.e. two may be in one location and the third in the other location).

Constraints I.a and I.b are always easily defined in Constellation Graph and often I.e, while the constraints I.c, I.d and I.e must be defined externally via CCDL (Constellation Constraint Definition Language)

APRIORI FIXED SLOT NUMBERS
I.c Availability: Team t must play home (or away) at round n.

I.d Non Availability: Team t cannot play at round n (day, time). Riposo (bye) at round n.

I.e Mating exclusion: Team t1 cannot play home (or away, or both) with team t2 at round n.
Hard complementarity constraints are used if two teams share the same stadium
(e.g. the "San Siro" stadium in Milan is shared by Internazionale and A.C. Milan).
Soft complementarity instead is used if the stadia of two teams are located close to each other
and the clubs want to optimize the use of railways and highways for their supporters
(e.g. Feyenoord and Sparta have their stadia in Rotterdam).

The constraints I.c, I.d and I.e must be defined externally via CCDL (Constellation Constraint Definition Language) and are actually interpreted as constrained_slot_number(s) of the team.

-------------------------------------------
II. SPECIAL Constraints
-------------------------------------------
Please note that the special constraints may be either hard (requirements) or soft ones (wishes).
The definition of the second group of constraints presupposed some prior notions:
We call top teams the members of a subset of the teams composed by the strongest teams, which require some special treatment. We call distance_of_two_matches (in short form only distance) the number_of_rounds between the rounds in which they take place.

....................................................................
Challenging-match & Top-match concept
....................................................................
The game is called the challenging-match when a (weak) team plays against a strong one. When two strong teams play, it is called the top-match.

The special constraints are the following ones:

....................................................................
II.a Top_match distance: 3 is default value
....................................................................
We call top-match a match between two strong teams. Two top-matches cannot take place at distance smaller than a given value TopMatchDistance.
Top Matches should not be too close together, and not in sequence, there must be at least a number of easy games between two top-matches. (Assured Top_match_distance)

..........................................................................
II.b Top_opponent distance: 2 is default value
..........................................................................
The game is challenging when a (weak) team plays against a strong one.
In the sequence of matches, the two challenging games should be distant and not consecutive. Any team in division cannot match two strong teams at distance smaller than a given value TopOpponentDistance.

Any team in the group should not meet two strong teams consecutively. In the sequence of matches, there must be at least a number of easy games between the two challenging games. (n = Top_opponent_distance)

................................................
II.c Top_matches_schedule
................................................
For a given set of rounds in the sport season, there is a predefined subset of TopRounds, when the top_match can take place.
The top_match can take place only at any of TopRounds.
The two parameters TopMatchDistance and TopOpponentDistance are given at global level; that is, they are the same for all teams in competition. Their typical value can be 3 and 2, respectively.
The teams are split in two subgroups: the top teams (usually 3 or 4) and the other ones.
An another grain grouping is also possible, and more complex constraint types can also be considered.

.....................................................
Periodic_crescendo sequence
.....................................................
For example, Schreuder (1993) proposes, although he does not pursue that idea, to divide teams in three groups |strong, medium, and weak teams| and looks for schedules that alternate matches with teams belonging to the three groups.
So the ideal sequence of matches would be "periodic_crescendo": weak_match, medium_match, strong_match, and so on.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


Constellation includes all instruments for creation of high quality sport-event schedulers. Constellation is supporting a diversity of arrangement algorithms (Balanced ROUND ROBIN scheduling) and analysis built-in instruments to enable creating sport schedules easier than ever.
Constellation Scheduling Algorithms & Reports
Constellation scheduling considers user predefined playground, time and team-binding constraints, which are user predefined in Constellation Graph in Constellation Census module
Constellation Graph enables quick and simple management of team-binding, time and stadium-location constraints settings
Constellation schedules tend to obey particular constraint logic definitions (defined via Constellation Graphs )
Constellation advanced scheduling algorithm will automatically generate competition schedules with a more efficient and compact match calendars
All matches for each week are automatically generated, and constraints are conformed to each schedule week, in order to provide a harmonious distribution of teams and playground locations during the sport season
Inter-divisional conflict resolution: conflicts are automatically resolved across all divisions/groupings during the interactive schedule creation.
Constellation has incorporated support for balanced round robin schedules, Swiss round, single and double elimination tournaments, mixed (inter) divisional schedules.
Scheduler match days in successive rounds do not necessary have to be in a fixed week day; i.e. matches in different rounds can take place in a user modifiable week day.
Constellation has support for groupings of multiple competition schedules in order to follow conflicts and manage inter-divisional play
Competition schedule calendar of each competition is rendered as a web page.
Report includes list of games per team in each round, list of home and away games, home/away sequence for each team, a confrontation diagram describing the game list each team plays versus it's rivals.
Schedule reports allows filtered viewing of games for defined competition, team or date, with information sorted in the proper chronological order.

========================================================

The Travelling Tournament Problem is a sports timetabling problem that abstracts two issues in creating timetables:home/away pattern feasibility and team travel. Instances of this problem seem to be very difficult even for a very small number of teams, making it an interesting challenge for combinatorial optimization techniques such as integer programming and constraint programming.

2.1 Ordinary Constraints
Ordinary constraints we consider are of the following types (see also Schreuder, 1993).

¤ Complementarity: Teams t1 and t2 must have complementary schedules (i.e. when t1 plays home t2 plays away, and vice versa).
Complementarity is also called Y Binding constraint. (i.e. when t1 plays home t2 plays away, and vice versa, it is said that t1 and t2 have - Complementarity [Y] Binding constraint).
¤ Availability: Team t must play home (or away) at round r.

¤ Mating: Team t1 cannot play home (or away, or both) with team t2 at round r.

¤ Triples: Obviously, three teams t1, t2, and t3 cannot be simultaneously in the same location (i.e. two must be in one location and the third in the other location).

Hard complementarity constraints are used if two teams share the same stadium (e.g. the "San Siro" stadium in Milan is shared by Internazionale and A.C. Milan).

Soft complementarity instead is used if the stadia of two teams are located close to each other and the clubs want to optimize the use of railways and highways for their supporters (e.g. Feyenoord and Sparta have their stadia in Rotterdam).
......................................................................................................
-------------------------------------------------------------------------------------
Compulsory Constraints (requirements) and Desired Constraints (wishes)
-------------------------------------------------------------------------------------
We deal with the problem of finding a schedule for a round robin championship with various types of constraints, including availability for matches and venues/stadions. For example, a constraint can state that a team must play home in a given round, or any defined pair of teams cannot match at a specified round.

Constraints are split into hard (requirements) and soft ones (wishes): Hard constraints must necessarily be satisfied by the solution, soft ones instead are associated with a penalty, and they contribute to the objective function to minimize.
The constraint programming approach achieves optimal solutions for problems (competitions) with up to eighteen teams, and near-optimal solutions for problems with up to 300 teams.
A graph model is presented for constructing sport events calendars for sports leagues where balancing requirement have to be considered with respect to the different venues where competitions take place.
-------------------------------------------------------------------------------------------------
=======================================================
-------------------------------------------------------------------------------------------------
Division, sometimes called League or Group
--------------------------------------------------------------
Many times the number of teams registered in a sport competition can be so great that it becomes impractical that teams entered play in one league/division all together. So the matches are held in smaller groupings: league/division.

All teams in a competition (Sporting Activity, Category, League or Division, Committee of competence) which participate in a championship/tournament, are divided into smaller groups of 6, 8,.., 18, ​​up to 20 teams playing versus each other.
When the teams in a competition are divided into groups/divisions, trying to respect the criterion of geographic proximity, or you try to assign the same division/pool neighbouring teams in geographical proximity.

For an example, if in competition there are 151 teams enrolled, the competition league championship can be split into 10 league/divisions with with 16 teams in each division.
So, in 9 league/divisions there is one BYE/dummy team * (1 division with 16 teams and 9 divisions with [15 + 1 bye] teams).




---------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------

Abstract:
Introduction Sports scheduling is an area of increasing interest in constraint programming. As amateur and professional sports leagues proliferate and grow in size and complexity, organizers are increasingly turning to computer assisted scheduling [Nemhauser and Trick]. The scientific literature in this area is also growing and one can begin to get a sense of the range and mathematical difficulty of the problems encountered.

These can include classical challenges such as set covering problems and quadratic assignment problems. In this note we concentrate on a version of a core problem that invariably comes up: determining whether a set of constraints on the schedule is feasible. This is often called the "timetabling" problem of the scheduling process. Here we consider the timetabling problem for a "round robin" schedule: the case in which every team must play every other team exactly once. (Later we will discuss related problems that come up in other sports situations such as Generating a schedule for a professional sports league is an extremely demanding task. Good schedules have many benefits for the league, such as higher incomes, lower costs and more interesting and fairer seasons. Many solution approaches for sports scheduling problems have been introduced in recent years.
We have an overview of the sports scheduling problem, a set of standard benchmark instances and the best solutions obtained for real-world instances.
.............
ABSTRACT
The Traveling Tournament Problem (TTP) is a combinatorial problem that combines features both from the traveling salesman problem and from tournament scheduling, the generation of sport event calendars. In this paper we present an approach to solving the TTP based on the search tab `u that makes use of the combination of two neighborhood relations.

*****************************************************************************************

........................................................
FIXTURE ASSIGNMENTS
........................................................

Before you can run the CONSTELLATION Assigning Division Pools and Schedule Processing you will have to setup requirements and constraints in order to generate "en masse" fixed game assignments.

The CONSTELATION GLOBAL CONTROL checker allows you to control of correctness and completeness of data and every constraint factor imaginable, before CONSTELLATION produces a fixture list for the whole competition league.

........................................................
A FIXTURE can have a different status:
........................................................
More than 90% of fixtures take place and are registered as real sport events with Match results. But sometimes a Fixture status may be irregular.

- Accomplished: A fixture which has successful termination of assigned event with clear result of the game. Reflected in calendar timetable.
- Cancelled: A fixture which was cancelled and will not be re-arranged at a later date. Not reflected in calendar timetable.
- Postponed: A fixture which was cancelled and will be re-arranged for a date in the future. Not reflected in calendar timetable.
- Home/ Away Walkover: A home win irrespective of the result (which is optional). Win and result applied to score tables.
- Home / Away Win Penalties: Used to progress a team to the next round of a cup if the result was a draw.
- Abandoned: Fixture was not completed, score shown as a result. Not reflected in calendar timetable.