# kbo_fpc_model.txt
#
# An AMPL model to determine the minimum number of games a team must win in order to clinch first place in the KBO League.

set TEAMS ordered;		# The set of teams 

param M default 144;		# The number of games in a season
param m := (1/M)*(1/(M-1));	# The (absolute value of the)) smallest possible difference between unequal winning percentages is (1/M)(1/(M-1));

param num_playoff_teams default 5; # The top five teams make the KBO League playoffs

param max_ties default 10;	# The maximum number of ties per team in a scenario

# w[i] is the number of wins team i currently has
# l[i] is the number of losses team i currently has
# t[i] is the number of ties (draws) team i currently has
# r[i] is the number of games remaining for team i
param w {TEAMS} default 0;
param l {TEAMS} default 0;
param t {TEAMS} default 0;

# g[i,j] is the number of games left between teams i and j
# note that only the upper diagonal of the g matrix is stored in the data file
#
# (i,j) is in SERIES if, and only if, there are any games left between i and j
param g {i in TEAMS, j in TEAMS: ord(i,TEAMS) < ord(j,TEAMS)} default 0;
set SERIES := {i in TEAMS, j in TEAMS: ord(i,TEAMS) < ord(j,TEAMS) and g[i,j] > 0};

# h[i,j] is the number of wins team i has against team j
param h {i in TEAMS, j in TEAMS} default 0;

# d[i,j] is the number of ties team i has against team j
param d {i in TEAMS, j in TEAMS: ord(i,TEAMS) < ord(j,TEAMS)} default 0;

# the team being solved for
param k symbolic default first(TEAMS);

set ORDERED_TEAM_PAIRS := {i in TEAMS, j in TEAMS: (i == k or j == k) and i <> j};

# x[i,j] is the number of additional games team i wins against team j in the scenario
var x {i in TEAMS, j in TEAMS: (i,j) in SERIES or (j,i) in SERIES} integer >= 0 <= g[member(min(ord(i,TEAMS),ord(j,TEAMS)),TEAMS),member(max(ord(i,TEAMS),ord(j,TEAMS)),TEAMS)];

# y[i,j] is the number of additional times team i and j tie in the scenario
var y {(i,j) in SERIES} integer >= 0 <= g[member(min(ord(i,TEAMS),ord(j,TEAMS)),TEAMS),member(max(ord(i,TEAMS),ord(j,TEAMS)),TEAMS)];

# total_wins[i] is the total number of games that team i wins in the scenario
# total_losses[i] is the total number of games that team i losses in the scenario
# total_ties[i] is the total number of games that team i ties in the scenario
var total_wins {TEAMS} integer >= 0;
var total_losses {TEAMS} integer >= 0;
var total_ties {TEAMS} integer >= 0;

# team i's winning precentage = wpct[i] = total_wins[i]/(total_wins[i] + total_losses[i])
var wpct {TEAMS} >= 0 <= 1;		 

# ties[i,j] = 1 if and only if team i has total of j ties in the scenario
var ties{i in TEAMS, j in 0 .. max_ties} binary;

# alpha[i,j] = 1 if team i wins the tie-breaker with team j
# beta[i,j] = 1 if team i has higher wining percentage than team j
# omega[i,j] = 1 if team i finishes ahead of team j in the standings either by having better winning percentage, or by hainng the same winning percentage and winning the tie-breaker
# T[i,j] = 1 if team i wins the head-to-head series with team j
var alpha {ORDERED_TEAM_PAIRS} binary;
var beta  {ORDERED_TEAM_PAIRS} binary;
var omega  {ORDERED_TEAM_PAIRS} binary;
var T {ORDERED_TEAM_PAIRS} binary;

# z[i] = 1 if there is a tie in the standings between teams k and j (i.e., they have the same winning percentage)
var z {i in TEAMS diff {k}} binary;

# The eliminiation number, playoff or first place, is total_wins[i] - w[i]
maximize wins: total_wins[k];

# Constraints analogous to the Win Comparison section of the NBA paper
# Ensure a feasible scenario in terms of the schedule of remaining games.
subject to feasible_scenario {(i,j) in SERIES}: x[i,j] + x[j,i] + y[i,j] = g[i,j];

# Calculate the number of games each team wins in the scenario.
subject to wins_in_scenario {i in TEAMS}: total_wins[i] = w[i] + sum{j in TEAMS: (i,j) in SERIES or (j,i) in SERIES} x[i,j];

# Calculate the number of games each team loses in the scenario.
subject to losses_in_scenario {i in TEAMS}: total_losses[i] = l[i] + sum{j in TEAMS: (i,j) in SERIES or (j,i) in SERIES} x[j,i];

# Calculate the number of games each team ties in the scenario.
subject to ties_in_scenario {i in TEAMS}: total_ties[i] = t[i] + sum{j in TEAMS: (i,j) in SERIES or (j,i) in SERIES} y[member(min(ord(i,TEAMS),ord(j,TEAMS)),TEAMS),member(max(ord(i,TEAMS),ord(j,TEAMS)),TEAMS)];

# Constraints analogous to the Compare Wins section of the NBA paper
subject to D1 {i in TEAMS diff {k}}: wpct[i] + M*omega[k,i] >= wpct[k] + alpha[k,i]/M;
subject to D2: sum {i in TEAMS diff {k}} omega[k,i] <= 8;

# enforce the limit on ties
subject to limit_ties {i in TEAMS}: total_ties[i] <= max_ties;
subject to count_ties1 {i in TEAMS}: sum{j in 0 .. max_ties} ties[i,j] = 1;
subject to count_ties2 {i in TEAMS}: sum{j in 0 .. max_ties} j*ties[i,j] = total_ties[i];

# team i's winning percentage is total_wins[i]/(M-j) where j is the number team i's games that end in a tie.
# if ties[i,j] = 0 then squeeze_wpct_1 is void since the left-hand side is negative.
# if ties[i,j] = 0 then squeeze_wpct_1 is void since the right-hand side is larger than 1.
# if ties[i,j] = 1 then wpct[i] = total_wins[i]/(M-j)
subject to squeeze_wpct_1 {i in TEAMS, j in 0 .. max_ties}: (ties[i,j] - 1) + total_wins[i]/(M-j) <= wpct[i];
subject to squeeze_wpct_2 {i in TEAMS, j in 0 .. max_ties}: wpct[i] <= total_wins[i]/(M-j) + (1-ties[i,j]);

# Determinations of ties (adapted from NBA paper)
subject to A3a {i in TEAMS diff {k}}: alpha[i,k] + alpha[k,i] = z[i];
subject to A3b {i in TEAMS diff {k}}: T[i,k] + T[k,i] <= 1;

subject to A3c {i in TEAMS diff {k}}: wpct[i] - wpct[k] <= 1 - z[i];
subject to A3d {i in TEAMS diff {k}}: wpct[k] - wpct[i] <= 1 - z[i];

subject to A3e {i in TEAMS diff {k}}: m - (wpct[i] - wpct[k]) <= z[i] + (1 + m) * beta[k,i];
subject to A3f {i in TEAMS diff {k}}: m - (wpct[k] - wpct[i]) <= z[i] + (1 + m) * beta[i,k];


subject to A3g {i in TEAMS diff {k}}: m - (wpct[k] - wpct[i]) <= z[i] + (1 + m) * (1 - beta[k,i]);
subject to A3h {i in TEAMS diff {k}}: m - (wpct[i] - wpct[k]) <= z[i] + (1 + m) * (1 - beta[i,k]);

subject to A3i {i in TEAMS diff {k}}: z[i] + beta[i,k] + beta[k,i] = 1;
# if Z[i,j] = 1, beta[i,j] = 0, and beta[j,i] = 0 then 
#  A3d forces wpct[i] = wpct[j] since wpct[i] <= wpct[j] and wpct[j] <= wpct[i] 
#  A3e is void because it reduces to m <= 1 
#  A3f is void because it reduces to m <= 2 + m
#  teams i and j have the same winning percentage
#
# if Z[i,j] = 0, beta[i,j] = 1, and beta[j,i] = 0 then
#  A3d is void because it reduces to wpct[i] - wpct[j] <= 1  
#  A3e forces wpct[i] - wpct[j] >= m, which implies that wpct[i] > wpct[j]
#  A3f is void because it reduces to wpct[i] - wpct[j] <= 1
#  team i has a larger winning percentage than team j 
#
# if Z[i,j] = 0, beta[i,j] = 0, and beta[j,i] = 1
#  A3d is void because it reduces to wpct[i] - wpct[j] <= 1  
#  A3e is void because it reduces to wpct[j] - wpct[i] <= 1 
#  A3f forces wpct[j] - wpct[i] >= m, which implies that wpct[j] > wpct[i]
#  team j has a larger winning percentage than team i
#
#  This is all well and good, but it seems to solve better if the constant on the RHS is M rather than 1 + m.  
#  Do we need the RHS to have smallest constant possible? 
#  Using 2 on the RHS also works better than M.

# either team i is ranked higher in the final standings than team j, or vice versa
# team i is ranked higher in the standings if wpct[i] > wpct[j], or wpct[i] = wpct[j] and team i wins the tie-breaker
subject to relative_order {(i,j) in ORDERED_TEAM_PAIRS}: omega[i,j] + omega[j,i] = 1;

# head-to-head tie-breaking constraints
#
# if T[i,j] = 1 then 
#   squeeze_T_lower forces h[i,j] + x[i,j] > h[j,i] + x[j,i] and squeeze_T1_upper is void
#
# if T[i,j] = 0 then 
#   squeeze_T_lower is void because the LHS = -M and upper forces h[i,j] + x[i,j] <= h[j,i] + x[j,i]
subject to squeeze_T_lower {(i,j) in ORDERED_TEAM_PAIRS}: 1 - (1 + M)*(1 - T[i,j]) <= (h[i,j] + x[i,j]) - (h[j,i] + x[j,i]);
subject to squeeze_T_upper {(i,j) in ORDERED_TEAM_PAIRS}: (h[i,j] + x[i,j]) - (h[j,i] + x[j,i]) <= M*T[i,j];

# use the criteria hierarchy to determine who wins the tie-breaker between teams i and j by applying contraint A12 in the NBA paper with n = 5 and |R| = 1
subject to A12 {i in TEAMS diff {k}}: 64 * (1 - z[i]) + (16 * T[i,k])  + (32 *  alpha[k,i]) >= (16 * T[k,i]);
subject to A13 {i in TEAMS diff {k}}: 64 * (1 - z[i]) + (16 * T[k,i])  + (32 *  alpha[i,k]) >= (16 * T[i,k]);