Maximise a groups probability of reaching a score within PuLP

user_19574505 0
Viewed 93

Using python, I have a linear programming solution in Pulp which selects 6 players within a budget constraint whilst maximising a specified parameter.

However, I want to be able to maximise a probability parameter of each team of 6 players.

Namely, I want to be able to input a mean and standard deviation for each player, and then maximise the percentage chance of each team reaching a predetermined score. This requires summing the means and standard deviations of the 6 players in each team, then calculating the percentage chance of them surpassing this score (I have been using numpy.norm to do this).

The problem I am having is that I am not sure if it is possible to maximise this parameter within a linear programming module like pulp. I can not get it to maximise the probability after summing each teams mean and standard deviation.

I have tried estimating this value by multiplying each individuals mean and standard deviation by 6, thus creating a dummy team, and calculating the probability of reaching the predetermined score, then scaling back down and maximising the sum of these values in each team. This gets close but is not as accurate as I want. This is the code I have so far:

lineup dataframe:

index mu std Salary
Rory McIlroy 73.450198 10.455766 11100.
Scottie Scheffler 72.652175 9.477475 11000.
Jon Rahm 73.033862 10.293721 10800.
Justin Thomas 73.886648 10.426305 10500.
Collin Morikawa 68.409628 10.588617 10300. 
target_score = 600

limit = 50000
lineup_im = lineup2.set_index('index')

w = lineup_im.Salary
v = lineup_im.mu
z = lineup_im['std']

items = list(sorted(lineup_im.index))
# Create model
m = LpProblem("Knapsack", LpMaximize)

# Variables
x = LpVariable.dicts('p', items, lowBound=0, upBound=1, cat=LpInteger)

# Objective
m += sum((((1-(norm(loc=v[i]*6, scale=z[i]*6).cdf(target_score)))))*x[i] for i in items)/6
   
# Constraint
m += sum(w[i]*x[i] for i in items) <= limit

m += sum(x[i] for i in items) == 6

# Optimize

m.solve()

Is there a way to do this within Pulp or another LP module in python?

pulp distribution linear-programming python
2 Answers

Welcome to the site and nice post w/ data!

You have a chicken vs. egg problem here... Let me explain...

The parameter that you want to get to is the CDF of the team score, which, if you assume it is normally distributed is the sum of the means of the player's scores with a variance that is a sum of the player's variances... That's how it works for Norm distribution, right?

So, all of those things are known values (parameters) in your problem, based on the player data. You just haven't calculated the team's CDF for all of the possible teams. The problem is you cannot do that as some kind of callback after using the optimizer to pick team membership, it must be done in advance. pulp solver does not have the ability/linkages to make calls to numpy to get the CDF "on the fly". So you have a couple options...

  1. You could reformulate your problem in terms of the teams and then expand your data set and just have a binary variable for which team is selected, but that seems kind of like a waste, because you are essentially having the solver just picking the single best team, with only one constraint (total salary), which makes me think you should just brute force this (see below.)

  2. You could just brute force this. If you are considering 100 players and you are choosing 6, that is combin(100, 6) ~ 1 billion. So I would use put the data into dictionaries for fast lookup, use itertools to run through the combinations, first screen for total salary cap, and if that passes, compute the team CDF/p-value for the target score, and keep track of the max value

user_107892070

Define decision variable x_i to indicate whether player i is selected for the team. From the basics of independent random variables, if we define mu_i to be the mean for each player i and sd_i to be their standard deviation, then:

mu_team = \sum_i mu_i*x_i
var_team = \sum_i sd_i^2*x_i
sd_team = sqrt(var_team)

You seek to maximize the probability that a normal random variable with mean mu_team and standard deviation sd_team exceeds some target score S. Conveniently, this is equivalent to minimizing the Z-score of the value S for that random variable:

z_team = (S-mu_team) / sd_team

It's now clear that you could reformulate your optimization model as minimizing z_team subject to your budget and team size constraints. However, z_team is non-linear --- it's a linear function of the decision variables divided by the square root of another linear function of the decision variables. In general mixed integer optimization problems with non-linear objective functions are not so trivial to solve; you won't be able to do it "out of the box" with pulp.

Not all is lost, though! Notice that we're basically balancing quantity S-mu_team with quantity sd_team. If we can construct teams with mu_team > S, then we'd ideally like teams with large mu_team and small sd_team, which enables as negative a z_team value as possible. If we could build a tradeoff curve between achievable mu_team and sd_team values, we could quickly identify the best achievable z_team value. Similarly, if all teams have mu_team < S, then we'd ideally like teams with large mu_team and large sd_team to get a z_team value as close as possible to 0; again, a tradeoff curve would be helpful.

This leads us to a simple solution:

  1. Maximize mu_team subject to budget and team size constraints. Call the best achievable mu_team value M. In the special case of M=S, the best achievable z_team value is 0, and you are done. Otherwise, continue.
  2. Build an efficient frontier trading off mu_team and sd_team:
  • If M > S, then maximize mu_team - alpha*var_team for various constants alpha >= 0
  • If M < S, then maximize mu_team + alpha*var_team for various constants alpha >= 0
  1. Compute z_team for each solution in your efficient frontier, and select the one with the smallest z_team value.

Note that each of the optimization problems in steps 1 and 2 now have a linear objective value (both mu_team and var_team are linear in the decision variables), so they will be easily solvable with pulp.

user_30933870
Related