##
## Atlantic Coast Competition Basketball 1997/98 (Sports scheduling)
## (c) J.P.Walser, Programming Systems Lab, UdS, August 1998
## All rights reserved.
##
##
## Parameters
##
set Teams ordered := { 'Clem', 'Duke', 'FSU', 'GT', 'UMD',
'UNC', 'NCSt', 'UVA', 'Wake' };
set Places ordered := Teams union { 'Bye' };
set Rounds ordered := { 1..2*card(Teams) };
set Weekdays ordered := { 1..last(Rounds) by 2 };
set Weekends ordered := { 2..last(Rounds) by 2 };
set February ordered := { 11..18} ;
set Mirror := { (1,8), (2,9), (3,12), (4,13), (5,14),
(6,15), (7,16), (10,17), (11,18) };
param Final := last(Rounds);
param GameQualityWeekend {Teams, Teams};
param GameQualityWeekday {Teams, Teams};
## Variables: Pairings
## T[i,j,t]=1 iff team i plays at place j in round t
var T {Teams, Places, Rounds} binary;
##
## DDRR constraints
##
subject to OP {i in Teams, t in Rounds}:
sum { j in Places} T[i,j,t] = 1;
subject to OV {j in Teams, t in Rounds}:
sum {i in Teams: i<>j} T[i,j,t] <= 1;
subject to CP {i in Teams, j in Teams, t in Rounds: i<>j}:
T[j,j,t] - T[i,j,t] >= 0;
subject to DRR {i in Teams, j in Teams: i<>j}:
sum {t in Rounds} T[i,j,t] = 1;
##
## Redundant constraints
##
subject to TB {i in Teams}:
sum {t in Rounds} T[i,'Bye',t] = 2;
subject to OB {t in Rounds}:
sum {i in Teams} T[i,'Bye',t] = 1;
subject to HH {t in Rounds}:
sum {i in Teams} T[i,i,t] = floor(card(Teams)/2);
##
## Sequence constraints (Rounds)
##
# Treating Bye as Home, no more than 2 Away games in a row: [ #(A)<=2 ]
subject to SEQ1 {i in Teams, t in Rounds : t <= prev(Final,Rounds,2)}:
sum {s in t .. next(t,Rounds,2), o in Teams: o<>i} T[i,o,s] <= 2;
# Treating Bye as Away, no more than 2 Home games in a row: [ #(H)<=2 ]
subject to SEQ3 {i in Teams, t in Rounds : t <= prev(Final,Rounds,2)}:
sum {s in t .. next(t,Rounds,2)} T[i,i,s] <= 2;
# Treating Bye as Away, no more than 3 Away games in a row: [ #(BA)<=3 ]
# (Bye+Away=not(Home))
subject to SEQ2 {i in Teams, t in Rounds : t <= prev(Final,Rounds,3)}:
sum {s in t .. next(t,Rounds,3)} (1-T[i,i,s]) <= 3;
# Treating Bye as Home, no more than 4 Home games in a row: #(BH)<=4 ]
subject to SEQ4 {i in Teams, t in Rounds : t <= prev(Final,Rounds,4)}:
sum {s in t .. next(t,Rounds,4)} (T[i,i,s] + T[i,'Bye',s]) <= 4;
##
## Sequence constraints (Weekends)
##
# Treating Bye as Home, no more than 2 Away games in a row: [ #(A)<=2 ]
subject to SEQ1w {i in Teams, t in Weekends :
t <= prev(last(Weekends),Weekends,2)}:
sum {s in t .. next(t,Weekends,2), o in Teams: s in Weekends
and o<>i} T[i,o,s] <= 2;
# Treating Bye as Away, no more than 2 Home games in a row: [ #(H)<=2 ]
subject to SEQ3w {i in Teams, t in Weekends :
t <= prev(last(Weekends),Weekends,2)}:
sum {s in t .. next(t,Weekends,2): s in Weekends} T[i,i,s] <= 2;
# Treating Bye as Away, no more than 3 Away games in a row: [ #(BA)<=3 ]
# (Bye+Away=not(Home))
subject to SEQ2w {i in Teams, t in Weekends :
t <= prev(last(Weekends),Weekends,3)}:
sum {s in t .. next(t,Weekends,3): s in Weekends}
(1-T[i,i,s]) <= 3;
# Treating Bye as Home, no more than 4 Home games in a row: #(BH)<=4 ]
subject to SEQ4w {i in Teams, t in Weekends :
t <= prev(last(Weekends),Weekends,3)}:
sum {s in t .. next(t,Weekends,3): s in Weekends}
(T[i,i,s] + T[i,'Bye',s]) <= 3;
##
## Mirror constraints
##
subject to MIR1 {i in Teams, j in Teams, (s,t) in Mirror: i<>j}:
(1-T[i,j,s]) + T[j,i,t] >= 1;
subject to MIR2 {i in Teams, (s,t) in Mirror}:
(1-T[i,'Bye',s]) + T[i,'Bye',t] >= 1;
##
## ACC Specific Constraints
##
# No team finishes AA
subject to FAA {i in Teams}:
sum {t in prev(Final,Rounds)..Final}
(T[i,i,t] + T[i,'Bye',t]) >= 1;
# Of 9 weekend Rounds, each team plays 4 home, 4 on the road
# and one bye
subject to SAT1 {i in Teams}:
sum {t in Weekends} T[i,i,t] = 4;
subject to SAT2 {i in Teams}:
sum {t in Weekends} T[i,'Bye',t] = 1;
# Home or bye at least on two of first five weekends
subject to FIF {i in Teams}:
sum {t in Weekends: ord(t) <= 5}
(T[i,i,t] + T[i,'Bye',t]) >= 2;
##
## ACC/season specific constraints
##
subject to RIV: # Rival matches
T['Duke','UNC', Final] + T['UNC', 'Duke',Final] +
T['Clem','GT', Final] + T['GT', 'Clem',Final] +
T['NCSt','Wake',Final] + T['Wake','NCSt',Final] +
T['UMD', 'UVA', Final] + T['UVA' ,'UMD', Final] >= 3;
# Popular matches in Feb
subject to FEB {(i,j) in {('Wake','UNC'),('Wake','Duke'),
('GT','UNC'),('GT','Duke')}}:
sum {t in February} (T[i,j,t] + T[j,i,t]) >= 1;
# Opponent ordering constraints
subject to OPOa {i in Teams, t in Rounds: i<>'Duke' and i<>'UNC'
and t <= prev(Final,Rounds)} :
sum {s in t..next(t,Rounds)}
(T[i,'Duke',s] + T[i,'UNC',s]) <= 1;
subject to OPOb {i in Teams, t in Rounds: i<>'Duke' and i<>'UNC'
and i<>'Wake' and t <= prev(Final,Rounds,2)}:
sum {s in t..next(t,Rounds,2), o in {'Duke','UNC','Wake'}}
(T[i,o,s] + T[o,i,s]) <= 2;
##
## Other idiosyncratic constraints
##
set FixGames dimen 4 within {Teams, Places, Rounds, 0..1};
subject to FIX {k in 0..1, (i,j,t,k) in FixGames}: T[i,j,t] = k;
data;
set FixGames :=
# UNC plays Duke instantiated
Duke UNC 11 1
UNC Duke 18 1
Duke Bye 16 1
Wake Wake 17 0
# as Wake is bye in Slot 1 the other must be home
Wake Bye 1 1
Clem Clem 1 1
FSU FSU 1 1
GT GT 1 1
# duke cannot be bye here either
Duke Duke 18 1
# rest
FSU Bye 18 0
NCSt Bye 18 0
UNC Bye 1 0
# additions [from Trick's revisions of May 8, 1998]
# Wake has a bye in slot 1 and must end AH
Wake Wake 18 1
Wake Bye 17 0
;
model;
subject to IDI2: T['UNC','Clem',2]+T['Clem','UNC',2] = 1;
subject to IDI3: T['Clem','Clem',Final]+T['Clem','Bye',Final] = 1;
subject to IDI5: T['UMD','UMD',Final]+T['UMD','Bye',Final] = 1;
subject to IDI6: T['Wake','Wake',Final]+T['Wake','Bye',Final] = 1;
##
## From Trick's revisions of May 9, 1998
##
# every team must have an H in the first three slots
subject to FTH {i in Teams}:
sum {t in 1..3} T[i,i,t] >= 1;
# every team must have an H in the last three slots
subject to LTH {i in Teams}:
sum {t in prev(Final,Rounds,2)..Final} T[i,i,t] >= 1;
##
## Optimization Criteria
##
## Criterion 1
## Avoid opening AA (not more than 1 team)
## use the complement: sum over teams home or bye >= card(Teams)-1
subject to OAA:
sum {i in Teams}
(T[i,i,1]+T[i,'Bye',1] + T[i,i,2]+T[i,'Bye',2]) >= card(Teams)-1;
## Criterion 2
## Game qualities: A/B/bad Rounds
##
## Variables: Slot-Quality
## Each slot is either an A,B, or bad slot
var Q {February, 0..2} binary;
subject to SLOTQ {t in February}: sum {q in 0..2} Q[t,q] = 1;
data;
# GameQualityWeekday[H,A]=2 means if team H plays
# home and A visits it is a 2 match (quality A)
# A-match: 2, B-match: 1
param GameQualityWeekday :
Clem Duke FSU GT UMD UNC NCSt UVA Wake :=
Clem 0 0 0 0 0 1 0 0 0
Duke 0 0 0 1 2 0 0 1 1
FSU 0 0 0 0 0 0 0 0 0
GT 0 1 0 0 1 2 0 0 1
UMD 0 2 0 1 0 2 0 1 0
UNC 1 2 0 1 1 0 0 0 0
NCSt 0 1 0 0 0 1 0 0 1
UVA 0 1 0 0 0 0 0 0 1
Wake 0 1 0 1 0 1 1 0 0 ;
param GameQualityWeekend :
Clem Duke FSU GT UMD UNC NCSt UVA Wake :=
Clem 0 0 0 0 0 2 0 0 0
Duke 0 0 0 1 2 2 0 1 1
FSU 0 0 0 0 0 0 0 0 0
GT 0 0 0 0 1 0 0 0 1
UMD 0 0 0 0 0 0 0 0 0
UNC 0 0 0 1 1 0 0 0 0
NCSt 0 1 0 0 0 1 0 0 1
UVA 0 1 0 0 0 0 0 0 0
Wake 0 1 0 1 0 1 1 0 0 ;
model;
# link T and Q variables: If a slot is A, there is at
# least one A or at least two B games
subject to LTQ1 {t in February: t in Weekends}:
2*Q[t,2] <= sum {v in Teams, h in Teams: v<>h}
GameQualityWeekend[h,v] * T[v,h,t];
subject to LTQ2 {t in February: t in Weekdays}:
2*Q[t,2] <= sum {v in Teams, h in Teams: v<>h}
GameQualityWeekday[h,v] * T[v,h,t];
# if a slot is B, there is at least one B game
subject to LTQ3 {t in February: t in Weekends}:
1*Q[t,1] <= sum {v in Teams, h in Teams: v<>h}
GameQualityWeekend[h,v] * T[v,h,t];
subject to LTQ4 {t in February: t in Weekdays}:
1*Q[t,1] <= sum {v in Teams, h in Teams: v<>h}
GameQualityWeekday[h,v] * T[v,h,t];
# Require 3 A Rounds in February
subject to MAXARounds: sum {t in February} Q[t,2] >= 3;
# Require <= 2 bad Rounds in February
subject to MINBADRounds: sum {t in February} Q[t,0] <= 2;
## Criterion 3
## Home/Away/Bye pattern criteria
set RoundsM3 ordered := { 1..last(Rounds)-2 };
set RoundsM3We ordered := { 2..last(Rounds)-2*2 by 2 };
## Variables expressing optimization criteria
## e.g. for each team i and round t,
## HB3[i,t]=1 if a sequence of at least 3
## home games starts for team t in round i
## NOTE: "X=1 if Y" reads "Y -> X" (not iff)
var HB3 {Teams, RoundsM3} binary;
var AB3 {Teams, RoundsM3} binary;
var HB3We {Teams, RoundsM3We} binary;
var AB3We {Teams, RoundsM3We} binary;
# HB3=1 if, treating Bye as Home, 3 Home games occur in a row:
subject to HB3L {i in Teams, t in RoundsM3}:
sum {s in t .. next(t,Rounds,2)}
(T[i,i,s] + T[i,'Bye',s]) <= 2+HB3[i,t];
# AB3=1 if, treating Bye as Away, 3 Away games occur in a row:
subject to AB3L {i in Teams, t in RoundsM3}:
sum {s in t .. next(t,Rounds,2)}
(1-T[i,i,s]) <= 2+AB3[i,t];
# Similarly for weekends:
# HB3=1 if, treating Bye as Home, 3 Home games occur in a row:
subject to HB3LWe {i in Teams, t in RoundsM3We}:
sum {s in t .. next(t,Weekends,2): s in Weekends}
(T[i,i,s] + T[i,'Bye',s]) <= 2+HB3We[i,t];
# AB3=1 if, treating Bye as Away, 3 Away games occur in a row:
subject to AB3LWe {i in Teams, t in RoundsM3We}:
sum {s in t .. next(t,Weekends,2): s in Weekends}
(1-T[i,i,s]) <= 2+AB3We[i,t];
## Formulate constraints on optimization criteria
subject to HB3LE4: sum {i in Teams, t in RoundsM3} HB3[i,t] <= 4;
subject to AB3LE3: sum {i in Teams, t in RoundsM3} AB3[i,t] <= 3;
subject to HB3WeLE5: sum {i in Teams, t in RoundsM3We} HB3We[i,t] <= 5;
subject to AB3WeLE4: sum {i in Teams, t in RoundsM3We} AB3We[i,t] <= 4;