Python PULP - Positional Constraints for a Lineup Generator

Question

I've built an NBA lineup generator that optimizes a lineup for 9 positions (2 x Point Guard (PG), 2 x Shooting Guard (SG), 2 x Small Forward (SF), 2 x Power Forward (PF), 1 x Centre (C)) using the projections provided for each player.

Initially to handle players who can play 2 positions I put a constraint that stopped the same player from being picked twice in a lineup, and it is working correctly. The issue I'm running into is occasionally when I build multiple lineups two of them will be duplicates but the program believes they are different.

Version 1 of the Generator

For example what occurs is a lineup is built where Player A and Player B are both picked, but they are both dual position players, and they share the same dual positions (for instance both can be a PG or SG), for the generator will interchange them for in Lineup 1 Player A is selected as a PG and B as a SG and in Lineup 2 Player A is selected as a SG and B as a PG.

The code I was to constrain the position in this first version is per the below:

    prob += (pulp.lpSum(self.positions['PG'][i] * players_lineup[i] for i in range(self.num_players)) == 2)
    prob += (pulp.lpSum(self.positions['SG'][i] * players_lineup[i] for i in range(self.num_players)) == 2)
    prob += (pulp.lpSum(self.positions['SF'][i] * players_lineup[i] for i in range(self.num_players)) == 2)
    prob += (pulp.lpSum(self.positions['PF'][i] * players_lineup[i] for i in range(self.num_players)) == 2)
    prob += (pulp.lpSum(self.positions['C'][i] * players_lineup[i] for i in range(self.num_players)) == 1)

Because the program sees the PG version of Player A and the SG version of Player A as separate entities, it has actually changed the outcome (despite it functionally being the same).

Version 2 of the Generator

So I have created a newer version where each player has a Position 1 and a Position 2 (can be none if the player doesn't have a 2nd position). The issue I have run into here is I can now produce a lineup where the constraints in the below sample are met, but the lineup is technically incorrect. First I'll provide my new constraints and then I'll explain my issue.

    #Ensures that the lineup has at least 2 potential suitors for PG
    prob += (pulp.lpSum(self.positions['PG'][i] * players_lineup[i] for i in range(self.num_players)) >= 2)
    # Ensures that the lineup has no more than 2 players who can only play PG
    prob += (pulp.lpSum(
        self.positions['PG'][i] * self.dualPosition[i] * players_lineup[i] for i in range(self.num_players)) <=2)
    #Ensures that the lineup has at least 2 potential suitors for SG
    prob += (pulp.lpSum(self.positions['SG'][i] * players_lineup[i] for i in range(self.num_players)) >= 2)
    # Ensures that the lineup has no more than 2 players who can only play SG
    prob += (pulp.lpSum(
        self.positions['SG'][i] * self.dualPosition[i] * players_lineup[i] for i in range(self.num_players)) <= 2)
    #Ensures that the lineup has at least 2 potential suitors for SF
    prob += (pulp.lpSum(self.positions['SF'][i] * players_lineup[i] for i in range(self.num_players)) >= 2)
    # Ensures that the lineup has no more than 2 players who can only play SF
    prob += (pulp.lpSum(
        self.positions['SF'][i] * self.dualPosition[i] * players_lineup[i] for i in range(self.num_players)) <= 2)
    #Ensures that the lineup has at least 2 potential suitors for PF
    prob += (pulp.lpSum(self.positions['PF'][i] * players_lineup[i] for i in range(self.num_players)) >= 2)
    # Ensures that the lineup has no more than 2 players who can only play PF
    prob += (pulp.lpSum(
        self.positions['PF'][i] * self.dualPosition[i] * players_lineup[i] for i in range(self.num_players)) <= 2)
    #Ensures that the lineup has at least 1 potential suitor for C
    prob += (pulp.lpSum(self.positions['C'][i] * players_lineup[i] for i in range(self.num_players)) >= 1)
    # Ensures that the lineup has no more than 1 player who can only play C
    prob += (pulp.lpSum(
        self.positions['C'][i] * self.dualPosition[i] * players_lineup[i] for i in range(self.num_players)) <= 1)

The issue I'm facing here is that the constraints are being met, but they obviously aren't achieving what I want them to haha! I'm finding that lineups like the following are being built:

Player	Pos 1	Pos 2
A	PG	None
B	PG	None
C	PG	SG
D	PG	SG
E	SG	SF
F	SF	PF
G	SF	PF
H	C	None
I	PG	SG

Based on the Above the total number of available PGs - 5, SGs - 4, SFs - 3, PFs - 2, C - 1 which all meet my minimum criteria. The issue is 3 players make up the availability for all of the SF and PF slots, so if I place the 2 PF options into the 2 PF slots I'm left with only 1 SF left for 2 SF slots.

I don't know how to update my constraints to make sure that all lineups spots will have a guaranteed supply.

Apologies for the long winded write up and please let me know if there's anything I can clarify.

AirSquid AirSquid · Accepted Answer · 2021-02-23T06:12:02

I think you are going to be a lot happier if you reformulate your problem. It is a natural fit for an integer program here to double-index this with a set of players and a set of positions. Things will get much clearer in your constraints, etc. because you can sum across either players or positions to formulate your problem more clearly. It really isn't clear what many of your model items are like positions[i] and dualPositions[i]. Here is a toy model that solves that might help you think about double indexing this bad boy...

Note there are a couple ways to handle the "legal assignments" part of this. Below is one notion of how to do it.

# hoops dream team

from pulp import *

salaries = {'bob'   : 100,
            'steve' : 110,
            'bernie': 105,
            'eugene': 120,
            'biff'  : 115, 
            'reggie': 99,
            'mike'  : 102}

positions = {'PG','FWD', 'CTR'}

legal_assignments = {   'bob'   : {'PG'},
                        'steve' : {'PG', 'FWD'},
                        'bernie': {'FWD', 'CTR'},
                        'eugene': {'FWD', 'PG'},
                        'biff'  : {'PG'},
                        'reggie': {'CTR', 'FWD'},
                        'mike'  : {'FWD'}}

legal_assignments_set = { (k,v) for k in legal_assignments.keys() for v in legal_assignments[k]}

prob = LpProblem("Team", LpMinimize)

assign = LpVariable.dicts("assignment", legal_assignments_set, cat="Binary")

#minimize cost of team
prob += sum(assign[player, pos] * salaries[player] for (player, pos) in legal_assignments_set)

# constraints...

# only assign each player once
for player in salaries.keys():
    prob += sum(assign[player, pos] for pos in positions if (player, pos) in legal_assignments_set) <=1

# fill each position to 2 PG, 2 FWD, 1 CTR
prob += sum(assign[player, 'PG'] for player in salaries.keys() if (player, 'PG') in legal_assignments_set) == 2
prob += sum(assign[player, 'FWD'] for player in salaries.keys() if (player, 'FWD') in legal_assignments_set) == 2
prob += sum(assign[player, 'CTR'] for player in salaries.keys() if (player, 'CTR') in legal_assignments_set) == 1

prob.solve()
print('Status:', LpStatus[prob.status])
for v in prob.variables():
    print(v.name, '=', v.varValue)

Python PULP - Positional Constraints for a Lineup Generator

1 Answers