Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

La planification d’horaires de ligues sportives
par programmation par contraintes
Gilles Pesantgilles.pesant@polymtl.ca
École Polytechnique de Montréal, CanadaSéminaires du département d’informatique et de génie logiciel
Université Laval
8 mars 2013

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

Objectifs de cette présentation

Meilleure compréhension de la planification d’horaires deligues sportives
C’est un domaine complexe avec une notion de qualité
d’horaire difficile à exprimer
La programmation par contraintes est très appropriée pourrésoudre ce problème

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

Outline1

Sports Scheduling2

Constraint Programming

3

TTPPV

4

Brazilian Football

5

Conclusion

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

Sports Schedulingplan a tournament between several teams(set of games between pairs of teams)
decide when (round) and where (venue) each game is played
at a given game one team plays home and the other, away
A schedule may be . . .
compact: each team plays at every roundround robin: teams play each other a fixed nb of times
single round robin (SRR); double round robin (DRR)
mirrored: the second half of the schedule is a repetition of thefirst half, with the venues swapped
G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

Traveling Tournament Problem (Major League Baseball)TTP
compact, double round robin scheduleno more than three consecutive games at home or away
minimize total distance traveled by all the teams

TTP with Predefined Venues (TTPPV)
single round robineach pair of teams meet at predefined venue (SRR+SRR)
instance is balanced if difference between number of home
and away games is at most one for any given team
G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

ExampleTTPPV schedule for 6-team unbalanced instanceroundteam 1:team 2:team 3:team 4:
team 5:team 6:

1st
@2
1
5
@6
@3
4

2nd
@3
6
1
@5
4
@2

3rd
6
@5
4
@3
2
@1

4th
@5
@4
@6
2
1
3

5th
@4
@3
2
1
@6
5

compact, single round robin
no more than three consecutive games at home or awayeach pair of teams meet at predefined venue
unbalanced instance
G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

ExampleTTPPV schedule for 6-team unbalanced instanceroundteam 1:team 2:team 3:team 4:
team 5:team 6:

1st
@2
1
5
@6
@3
4

2nd
@3
6
1
@5
4
@2

3rd
6
@5
4
@3
2
@1

4th
@5
@4
@6
2
1
3

5th
@4
@3
2
1
@6
5

compact, single round robin
no more than three consecutive games at home or awayeach pair of teams meet at predefined venue
unbalanced instance
G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

ExampleTTPPV schedule for 6-team unbalanced instanceroundteam 1:team 2:team 3:team 4:
team 5:team 6:

1st
@2
1
5
@6
@3
4

2nd
@3
6
1
@5
4
@2

3rd
6
@5
4
@3
2
@1

4th
@5
@4
@6
2
1
3

5th
@4
@3
2
1
@6
5

compact, single round robin
no more than three consecutive games at home or awayeach pair of teams meet at predefined venue
unbalanced instance
G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

ExampleTTPPV schedule for 6-team unbalanced instanceroundteam 1:team 2:team 3:team 4:
team 5:team 6:

1st
@2
1
5
@6
@3
4

2nd
@3
6
1
@5
4
@2

3rd
6
@5
4
@3
2
@1

4th
@5
@4
@6
2
1
3

5th
@4
@3
2
1
@6
5

compact, single round robin
no more than three consecutive games at home or awayeach pair of teams meet at predefined venue
unbalanced instance
G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

ExampleTTPPV schedule for 6-team unbalanced instanceroundteam 1:team 2:team 3:team 4:
team 5:team 6:

1st
@2
1
5
@6
@3
4

2nd
@3
6
1
@5
4
@2

3rd
6
@5
4
@3
2
@1

4th
@5
@4
@6
2
1
3

5th
@4
@3
2
1
@6
5

compact, single round robin
no more than three consecutive games at home or awayeach pair of teams meet at predefined venue
unbalanced instance
G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

Constraint Programming (CP)problem described through formal model expressed using
constraints from rich set of modeling primitives
variables take their value from a finite set (domain)each type of constraint encapsulates its own specialized
inference algorithm
sophisticated inference to reduce search space
combination of variable- and value-selection heuristics toguide exploration of search space

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP for Sports Schedulinginstrumental in scheduling Major League Baseball in North
Americaused in the past to schedule the National Football League inthe US
also applied to College Basketball

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Back to the TTPPV. . .

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Decision Variables
n teams (and hence n − 1 rounds)oij , opponent of team i in round jhij = 1 iff team i plays at home in round jroundteam 1:
..
.

1st

...

team i:
..
.

j th

...

(n − 1)thhij ; oijteam n:G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Decision Variables
n teams (and hence n − 1 rounds)oij , opponent of team i in round jhij = 1 iff team i plays at home in round jroundteam 1:
..
.

1st

...

team i:
..
.

j th

...

(n − 1)th0; kteam n:G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Decision Variables
n teams (and hence n − 1 rounds)oij , opponent of team i in round jhij = 1 iff team i plays at home in round jroundteam 1:
..
.

1st

...

team i:
..
.

j th

...

(n − 1)th@kteam n:G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Basic Structureoij ∈ {1, . . . , i − 1, i + 1, . . . , n}

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

hij ∈ {0, 1}

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

alldifferent((oij )1≤j≤n−1 )ooij ,j = i

G. Pesant1≤i ≤n1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Predefined Venues

oij ∈ {1, . . . , i − 1, i + 1, . . . , n}

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

hij ∈ {0, 1}

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

alldifferent((oij )1≤j≤n−1 )1≤i ≤nooij ,j = i

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

hij = V [i , oij ]1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

At most 3 consecutive home or away games
oij ∈ {1, . . . , i − 1, i + 1, . . . , n}

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

hij ∈ {0, 1}

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

alldifferent((oij )1≤j≤n−1 )1≤i ≤nooij ,j = i

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

hij = V [i , oij ]1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

regular((hij )1≤j≤n−1 , A)
1

1H

2H

1

3H

0

1
start

1≤i ≤n

1

0
1

0

0

1
1A

G. Pesant

0

2A

0

3A

Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Adding travel costs
D : n × n travel distance matrix
vars dij : travel distance for team i to go play in round jroundteam 1:..
.
team i:
..
.

1st

j th

...

...

(n − 1)thhij ; oij ; dij

team n:G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Adding travel costs
D : n × n travel distance matrix
vars dij : travel distance for team i to go play in round j
Individual travel distances depend on pairs of consecutive variables:(hij = 1 ∧ hi ,j+1 = 1) ⇒ di ,j+1 = 0

1≤i ≤n,1≤j<n−1(hij = 1 ∧ hi ,j+1 = 0) ⇒ di ,j+1 = D[i , oi ,j+1 ]1≤i ≤n,1≤j<n−1(hij = 0 ∧ hi ,j+1 = 1) ⇒ di ,j+1 = D[oij , i ]1≤i ≤n,1≤j<n−1(hij = 0 ∧ hi ,j+1 = 0) ⇒ di ,j+1 = D[oij , oi ,j+1 ]1≤i ≤n,1≤j<n−1

dij ∈ {0} ∪ {min{D}, . . . , max{D}}
n
n X
X
dij
z=
i =1 j=1
G. PesantHoraires de ligues sportives

1≤i ≤n,1≤j≤n

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

At this point
we have a complete model

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Adding redundant constraints

In a round j, each team appears exactly once as an opponent:

alldifferent((oij )1≤i ≤n )G. Pesant1 ≤ j ≤ n−1

Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Catching infeasible instances
Need enough home (resp. away) games to separate long
stretches of away (resp. home) games
Necessary condition: at least ⌊ n−1
4 ⌋ of each are needed(Melo,Urrutia,Ribeiro, J. Scheduling, 2009)
Combine “3-home/3-away” constraint with counting number ofhome games:
cost regular((hij )1≤j≤n−1 , A,1≤k≤n V [i , k], [0, 1])

1

1H

2H

1

3H

0

1
start

P

1

0
1

0

0

1
1A
G. Pesant

0

2A

0

3A

Horaires de ligues sportives

1≤i ≤nSports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Catching infeasible subinstances
Consider 14-team individual schedule with 3 predefined home
games
Necessary condition satisfied: ⌊ 14−1
4 ⌋=3
New constraint more powerful because used dynamically:
H

+2H
(i)

H

A

A

A

H

A

A

A

H

A

A

A

H

(ii)

H

A

A

A

A

A

A

A

H

A

A

A

H

Both (i) and (ii) completed schedules are invalid
G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Symmetry breaking

Forbid the mirror image of a schedule, going from the last round to
the first (travel distances are symmetric):o11 < o1,n−1

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Some generic variable-selection heuristics

Branching on opponent variables
lexico: Select variables in lexicographic order (row by row)
random: Select variables randomly
dom: Select the variable with the fewest alternatives

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Dedicated value-selection heuristic

At this point, we have selected one team and the round;value selection determines the other team (and thus a game)
dist: For that game (in both rows), compute lower bound on
travel distances from previous round and to next round.
Select the value with the smallest lower bound.

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Benchmark Instances

Existing TTP instances (Circle instances) to which a venue isadded for each game (Melo,Urrutia,Ribeiro, J. Scheduling,2009)
Up to 20 teams; twenty instances (ten balanced; tennonbalanced) of each size

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

G. PesantCP ModelVariable- and Value- selection heuristics
Empirical Results

Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Brazilian Football League

compact, mirrored double round robin schedule
20 teams
many restrictions
maximize gate attendance and TV audience

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Decision Variablesn = 20 teams (and hence 38 rounds)
oij : opponent of team i in round jhij = 1 iff team i plays at home in round jrik : first-half round in which team i plays against k′ = 1 iff team i plays at home against k in first halfhikbij : away break (0), home break (2), or no break (1)for team i in round j

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Basic Structureoij ∈ {1, . . . , i − 1, i + 1, . . . , n}

1 ≤ i ≤ n, 1 ≤ j ≤ 2(n − 1)hij ∈ {0, 1}

1 ≤ i ≤ n, 1 ≤ j ≤ 2(n − 1)

ooij ,j = i

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1hoij ,j 6= hij

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

alldifferent((oij )1≤j≤n−1 )alldifferent((oij )1≤i ≤n )G. Pesant1≤i ≤n1≤j ≤n−1

Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Basic Structure (continued)

rik ∈ {0, . . . , n − 1}

1 ≤ i ≤ n, 1 ≤ k ≤ n′hik∈ {0, 1}1 ≤ i ≤ n, 1 ≤ k ≤ nbij ∈ {0, 1, 2}

1 ≤ i ≤ n − 1, 1 ≤ j ≤ n − 1

rii = 01≤i ≤nalldifferent((rik )1≤k≤n )1≤i ≤nrik = rki

1 ≤ i ≤ n, 1 ≤ k ≤ n′′
6= hkihik′hik= hirik

1 ≤ i ≤ n, 1 ≤ k ≤ noirik = k

1 ≤ i ≤ n, i < k ≤ n

bij = hij + hi ,j+1
G. Pesant1 ≤ i ≤ n, i < k ≤ n
1 ≤ i ≤ n − 1, 1 ≤ j ≤ n − 1
Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Basic Structure (continued)

rik ∈ {0, . . . , n − 1}

1 ≤ i ≤ n, 1 ≤ k ≤ n′hik∈ {0, 1}1 ≤ i ≤ n, 1 ≤ k ≤ nbij ∈ {0, 1, 2}

1 ≤ i ≤ n − 1, 1 ≤ j ≤ n − 1

rii = 01≤i ≤nalldifferent((rik )1≤k≤n )1≤i ≤nrik = rki

1 ≤ i ≤ n, 1 ≤ k ≤ n′′
6= hkihik′hik= hirik

1 ≤ i ≤ n, 1 ≤ k ≤ noirik = k

1 ≤ i ≤ n, i < k ≤ n

bij = hij + hi ,j+1
G. Pesant1 ≤ i ≤ n, i < k ≤ n
1 ≤ i ≤ n − 1, 1 ≤ j ≤ n − 1
Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Mirrored Double Round Robin Structureoi ,(n−1)+j = oij

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

hi ,(n−1)+j 6= hij

1 ≤ i ≤ n, 1 ≤ j ≤ n − 1

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Particular groupings

Special types of games
G12: games between the 12 best teams
Classic: games between teams of the same city
Regional: games between teams of the same state
Paired teams
teams are paired: 1 with 2, 3 with 4, . . .
usually teams from the same city

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Particular groupings

Special types of games
G12: games between the 12 best teams
Classic: games between teams of the same city
Regional: games between teams of the same state
Paired teams
teams are paired: 1 with 2, 3 with 4, . . .
usually teams from the same city

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Public Safety

Opposite home/away pattern for paired teams
hij 6= hi +1,ji ∈ {1, 3, 5, . . . , n − 1}, 1 ≤ j ≤ n − 1

At most 1 Classic game per city per roundalldifferent((rik )(i ,k)∈Classicj )G. Pesantj ∈ “>2 team cities′′

Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Revenues
Maximize classic games on double-weekend rounds
X((i , oij ) ∈ Classic) ≥ 2 × LB

1≤i ≤n, j∈DW

Number of G12 games in each round is between 2 and 4gcc((rik )(i ,k)∈G 12 , hg1 , . . . , gn−1 i)
2 ≤ gj ≤ 4

G. Pesant1≤j ≤n−1

Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

AttractivenessNo regional (or classic) games in first 3 rounds
rik 6∈ {1, 2, 3}(i , k) ∈ Regional

No G12 RdJ-SP game in same round as Classic RdJ or SP gamerik 6= ri ′ k ′(i , k) ∈ Classic RdJ or SP, (i ′ , k ′ ) ∈ G12 RdJ-SP

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Fairness

First team of a pair plays home in first round and away in lastround
hi 1 = 1 ∧ hi ,n−1 = 0

G. Pesanti ∈ {1, 3, 5, . . . , n − 1}

Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Fairness
No breaks in first 4 or last 2 rounds
bi 1 = 1

1≤i ≤nbi 2 = 1

1≤i ≤nbi 3 = 1

1≤i ≤nbi ,n−2 = 1

1≤i ≤nNo regional games in last 4 rounds
rik 6∈ {n − 4, n − 3, n − 2, n − 1}
G. Pesant(i , k) ∈ Regional

Horaires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Fairness

Each team has x home breaks and y away breaks;
x and y should be smallgcc((bij )1≤j≤n−1 , hbA, ⋆, bHi)

1≤i ≤nbA ≤ maxbAbH ≤ maxbH

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Fairness
At most 4 consecutive games in SP state, for any SP state teamSee below
At most 3 consecutive games in SP state, for any non SP state
team
See below
At most 5 consecutive games against G12 teams, for any teamregular(. . . (oij )1≤j≤2(n−1) . . . , A)

G. Pesant1≤i ≤nHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Fairness

No consecutive Classic games for any team
allMinDistance((rik )(i ,k)∈Classici , 2)

G. Pesant1≤i ≤nHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Fairness

Perfect matching of paired teams′, hi′ +1,k , hi′ +1,k+1 , hi′ ,k+1 i, A)
regular(hhiki ∈ {1, 3, 5, . . . , n − 3},k ∈ {i + 2, i + 4, . . . , n − 1}

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

More sophisticated generic variable-selection heuristics

Can branch on opponent, home, round, and homeAway variables
IBS: Select variable to maximize impact of that choice on sizeof search space; select value to minimize that impact
maxSD: Select variable-value to (try to) maximize theproportion of solutions being preserved

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Benchmark InstanceThe 2010 season of the 1st division of the Brazilian Professional
Football League;
a particularly difficult year to schedule

G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

CP ModelVariable- and Value- selection heuristics
Empirical Results

Results so far
maxSD performs much better than the other heuristics
solved easily (a few seconds) . . . without perfect matching
constraints:′
regular(hhik, hi′ +1,k , hi′ +1,k+1 , hi′ ,k+1 i, A)

solved easily (a few seconds) . . . without no regional games at
beginning or end constraints:rik 6∈ {1, 2, 3, n − 4, n − 3, n − 2, n − 1}with all constraints: nothing after several hours. . .
The League uses an IP approach, generating solutions in a few
minutes
G. PesantHoraires de ligues sportives

Sports SchedulingConstraint Programming
TTPPV
Brazilian Football
Conclusion

Objectifs de cette présentation

Meilleure compréhension de la planification d’horaires deligues sportives
C’est un domaine complexe avec une notion de qualité
d’horaire difficile à exprimer
La programmation par contraintes est très appropriée pourrésoudre ce problème

G. PesantHoraires de ligues sportives