Related Topics
Constraints and preferences
Sport Schedule Constraints
Competition SchemeCode
Competition division
Slot number
XY binding-constraints
Types of constrained teams in Constellation Graph
Balanced Round Robin
CONSTELLATION GRAPH
Constraints and preferences  
Constraints and preferences
hard and soft constraints


Constraints and preferences
Constraints and preferences
=============================================
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
we can also say that the team t1 is a complementary travel partner of the team t2).
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)

..................................................................
A PRIORI RESERVED 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.

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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, ie. inter-league 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.

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


-------------------------------------------
II. SPECIAL Constraints
-------------------------------------------
We may consider applying the SPECIAL Constraints, in the divisions/competitions where the strong and weak teams participate.

The SPECIAL Constraints are NOT defined via CCDL (Constellation Constraint Definition Language) nor in Constellation Graph.

The following SPECIAL Constraints are specified globally in the COMPETITION CARDS, and are valid for the whole competition:
- Top_match distance: 3 is default value
- Top_opponent distance: 2 is default value
- Top_matches_schedule / TopRounds

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