Vincoli (Requisiti e Desideri)
hard and soft constraints
Vincoli (Requisiti e Desideri)
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)
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.
The special constraints are the following ones:
II.a Top_match distance: 3 is default value
We call top match a match between two top teams. Two top matches cannot take place at distance smaller than a given value TopMatchDistance. Top_match è quando giocano le due squadre forti.
Top_match non devono essere accavalati e troppo vicini tra loro, ovvero nella sequenza delle partite di una squadra forte deve esistere al meno un numero (Top_match_distance) di partite non impegnative.
II.b Top_opponent distance: 2 is default value
Any team cannot match two top teams at distance smaller than a given value TopOpponentDistance.
Le partita_impegnativa è quando una squdra(debole) gioca contro una forte.
Una qualsiasi squdra nel girone non deve incontrare una forte consecutivamente.
Le partite impegnative non possono/devono essere accavalate e troppo vicine tra loro,
ovvero nella sequenza delle partite di una squadra deve esistere al meno
un numero di (n=Top_opponent_distance) partite non impegnative.
For a given set of rounds R, no top_match can take place at any round r 2 R.
The two parameters TopMatchDistance and TopOpponentDistance are given at global level;
that is, they are the same for all teams. Their typical value can be 3 and 2, respectively.
We split teams 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 be considered.
For example, Schreuder (1993) proposes (although he does not pursue this 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.
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.