I’m trying to apply programming to a real-life problem that comes around each year for my tennis team. It’s about picking the best team for a team match, given some rules. I thought I’d have a go at formalising the rules and automating the player selection process.
I’m used to using Matlab from uni, but have dabbled in Python with numpy before so I went with that. I’m trying to formulate the problem as an optimization, and am using a toolkit called puan as a way of “writing rules”. I went through the puan tutorials successfully and thought it should be possible to apply similar logic to my problem.
Bear with me, I’m not a star programmer! Hope you can follow the reasoning.
The team has 5 possible players.
The matches to be played are 2 singles matches and 1 doubles match.
Therefore, two players need to be picked to play a singles match each and two players to play the doubles match together.
A player cannot play both singles and doubles.
I have managed to formulate the problem, and to get the program to pick players so that the matches can be played. I can also set a preference for if I know beforehand that I want a specific player to definitely play the doubles. But my end goal is to automatically get the program to select a constellation of players that is based on a ranking in singles and a ranking in doubles (i.e put the best singles players on the singles matches, and the doubles specialists in the doubles match). How would I do that, attach a ranking which is used as a parameter in the player selection? That’s where I’m stumped.
Here is the code right now:
import puan
import puan.logic.plog as pg
import puan.modules.configurator as cc
import puan_solvers as ps
Define variables true/false to reply to the questions "Does this player play singles?" and "Does this player play doubles?"
p1s = puan.variable(id="p1s") #Does player 1 play the singles match?
p2s = puan.variable(id="p2s")
p3s = puan.variable(id="p3s")
p4s = puan.variable(id="p4s")
p5s = puan.variable(id="p5s")
p1d = puan.variable(id="p1d") #Does player 1 play the doubles match?
p2d = puan.variable(id="p2d")
p3d = puan.variable(id="p3d")
p4d = puan.variable(id="p4d")
p5d = puan.variable(id="p5d")
Combine "at most" and "at least" propositions to get exactly 2 singles matches.
singles_matches_max = pg.AtMost(propositions=[p1s,p2s,p3s,p4s,p5s],value=2)
singles_matches_min = pg.AtLeast(propositions=[p1s,p2s,p3s,p4s,p5s],value=2)
Combine "at most" and "at least" propositions to get exactly two players who play doubles, i.e. one doubles pairing.
doubles_matches_max = pg.AtMost(propositions=[p1d,p2d,p3d,p4d,p5d],value=2)
doubles_matches_min = pg.AtLeast(propositions=[p1d,p2d,p3d,p4d,p5d],value=2)
Define that players 1-5 may not play both singles and doubles.
only_one_match1 = pg.Not(pg.All(p1s,p1d))
only_one_match2 = pg.Not(pg.All(p2s,p2d))
only_one_match3 = pg.Not(pg.All(p3s,p3d))
only_one_match4 = pg.Not(pg.All(p4s,p4d))
only_one_match5 = pg.Not(pg.All(p5s,p5d))
Combine all of the above rules/criteria into a configurator model of the team.
team_model = cc.StingyConfigurator(
singles_matches_max,
singles_matches_min,
doubles_matches_max,
doubles_matches_min,
only_one_match1,
only_one_match2,
only_one_match3,
only_one_match4,
only_one_match5
)
I'm not sure what this does but I kept it from the tutorial:
team_ph = team_model.to_ge_polyhedron(active=True)
Formulate a solution based off of one initial truth, that player 4 plays doubles.
team_solution = next(
team_model.select(
{"p4d": 1}, #I know that player 4 is the best doubles player, so I want them to play doubles.
solver = ps.glpk_solver,
only_leafs = True
)
)
print(team_solution)
This gives an answer of:
{'p1d': 0.0, 'p1s': 1.0, 'p2d': 1.0, 'p2s': 0.0, 'p3d': 0.0, 'p3s': 1.0, 'p4d': 1.0, 'p4s': 0.0, 'p5d': 0.0, 'p5s': 0.0}
Which makes sense to me, because you have Players 1 and 3 playing singles, and Players 2 and 4 teaming up to play the doubles match. The one left out is Player 5.
So now my wish is to connect a singles and doubles ranking to each of the players, and get the optimizer to choose the team that is strongest on each match. I would have liked to add it somehow as an attribute to each variable but I can't see that that's possible!
In my country we have a ranking system where the lower your number is, the better you are. For example, I’d like to define the following for my players:
p1 = {"s_rank": 1.9225, "d_rank": 1.8000} #Singles rank and doubles rank, lower number = better
p2 = {"s_rank": 3.8156, "d_rank": 3.7765}
p3 = {"s_rank": 4.0611, "d_rank": 2.3133}
p4 = {"s_rank": 3.0974, "d_rank": 3.9666}
p5 = {"s_rank": 2.3790, "d_rank": 2.5672}
As you may guess, I want the optimizer to recognize that Player 4 is better at singles than doubles. And that Player 3 is quite terrible at singles but good in doubles. But also: you can see that Player 1 and Player 5 are the best players ranking-wise overall. But if I were to put both of them on the doubles, that would only be one match win for the team. Putting them on a singles match each would probably win the team two matches. So I’d like to write a rule that the best 2 players on the team should avoid being placed in the doubles.
Further actual criteria I’d like to add down the line is that: there is a limit on the number of foreign players a team can play with (because it’s the national team championships). I should be able to add this info too and get the optimizer to take it into consideration. Another dimension is “home” matches and “away” matches, with some players either not able to travel to other cities to play, or they simply compete a lot worse without home arena support…
I’m running Python 3.9.2 right now, I don’t know if that might be relevant to running this! Thanks for any suggestions!
I have used Google-ortool's CP-SAT solver (python API) to solve the above optimization problem. CP-SAT solver cannot handle float values, so I have converted the ranks into integer by multiplying with a large scalar value.
You can do a "pip install ortools" to install the ortools package in your python environment (in case you don't have that already
from ortools.sat.python import cp_model as cp
players = {"p1" : {"s_rank": 19225, "d_rank": 18000}, # multiplied all ranks with a scalar to convert them
"p2" : {"s_rank": 38156, "d_rank": 37765},# into integers. This will not impact the solution
"p3" : {"s_rank": 40611, "d_rank": 23133},
"p4" : {"s_rank": 30974, "d_rank": 39666},
"p5" : {"s_rank": 23790, "d_rank": 25672},
"p6" : {"s_rank": 56745, "d_rank": 23456},
"p7" : {"s_rank": 15645, "d_rank": 21345}
}
nationality = {'p1' : ("domestic","international"), # can play both domestic and international
'p2' : ("domestic"), # can play only domestic
'p3' : ("domestic"),
'p4' : ("international"), # can play only international
'p5' : ("domestic","international"),
'p6' : ("domestic"),
'p7' : ("international")}
game_location = {'p1' : ("home"), # can play only home games
'p2' : ("home", "away"), # can play both home and away games
'p3' : ("home", "away"),
'p4' : ("home", "away"),
'p5' : ("away"), # can play only away games
'p6' : ("away"),
'p7' : ("home")}
model = cp.CpModel()
# decision variable : whether a player will play a single or double
dv_player_sngl_dbl = {}
for plry in players:
for typ in ["single", "double"]:
dv_player_sngl_dbl[(plry, typ)] = model.NewBoolVar(plry + "_" + typ)
# constraint a player can play either a single or double (and not both).
# The player can be out from both single or double also
for plry in players:
model.Add(sum(dv_player_sngl_dbl[(plry, typ)] for typ in ["single", "double"]) <= 1)
total_players_singles = 2
total_players_doubles = 2
num_single_games = 2
num_double_games = 1
# match attributes:
matches = {
"match_1" : ("single", "home", "domestic"), # match 1 is a singles match to be played at home. Only domestic player can participate
"match_2" : ("single", "home", "domestic"),
"match_3" : ("double", "home", "international")
}
dv_total_singles_score = model.NewIntVar(0, 100000000, "")
dv_total_doubles_score = model.NewIntVar(0, 100000000, "")
dv_avg_doubles_score = model.NewIntVar(0, 100000000, "")
# constraint : select 2 single players
model.Add(sum(dv_player_sngl_dbl[(plry, "single")] for plry in players) == total_players_singles)
# constraint : select 2 doubles players
model.Add(sum(dv_player_sngl_dbl[(plry, "double")] for plry in players) == total_players_doubles)
# calculate the rank scores when selecting 2 single players (2 matches)
# rank scores of these players will be added to the objective function, which we will minimize at the end
model.Add(dv_total_singles_score == sum(dv_player_sngl_dbl[(plry, "single")] * players[plry]["s_rank"] for plry in players))
# calculate the rank scores when selecting 2 double players (1 match)
# summation of the double scores for 2 players will be added and then divided by 2
# because its a single match
model.Add(dv_total_doubles_score == sum(dv_player_sngl_dbl[(plry, "double")] * players[plry]["d_rank"] for plry in players))
# divivding the above summed score for 2 players by 2 (since its one match)
model.AddDivisionEquality(dv_avg_doubles_score, dv_total_doubles_score, num_double_games * 2)
# addiing game location (home / away) and nationality (domestic / international) constraint
for match in matches:
match_details = matches[match]
single_or_double = match_details[0]
location = match_details[1]
nation = match_details[2]
# players who cannot play at the above game location
plyrs_not_in_loc = [k for k,v in game_location.items() if location not in v]
# constraint : players such as above cannot be selected for the match
model.Add(sum(dv_player_sngl_dbl[(plry, single_or_double)] for plry in plyrs_not_in_loc) == 0)
# players who are not eligible to play per nationality status
plyrs_not_in_nationality = [k for k,v in nationality.items() if nation not in v]
# constraint : players such as above cannot be selected for the match
model.Add(sum(dv_player_sngl_dbl[(plry, single_or_double)] for plry in plyrs_not_in_nationality) == 0)
# defining the objective function
# this is summation of ranks, and we will minimize (since lower rank is better)
objective_function = dv_total_singles_score + dv_avg_doubles_score
model.Minimize(objective_function)
solver = cp.CpSolver()
solver.Solve(model)
# inspect decision variable values
for plry in players:
for typ in ["single", "double"]:
print(str((plry, typ)) + " : " + str(solver.Value(dv_player_sngl_dbl[(plry, typ)])))