lundi 27 juin 2016

All possible team rosters algorithm? Similar to knapsack maybe?


I have been working on a hobby project for a while that involves finding all possible team rosters given the constraints of a salary cap and player positions while trying to N teams with the maximum projection. This is specifically for fantasy football, but the problem can be more generalized to a maximization problem. I can't find a more efficient solution than using nested for loops. I am using python dictionaries to track specific player data by position where qbs[playerName] = {Salary: X, Projection: Y} and rbs[playerName] = {Salary: X, Projection: Y}, etc.

The constraints are as follows:

  • 1 quarterback (qb)
  • 2 running backs (rb1, rb2)
  • 3 wide receivers (wr1, wr2, wr3)
  • 1 tight end (te)
  • 1 defense (dst)
  • 1 flex player (can be a running back, a tight end, or a wide receiver)
  • total salary has to be <= N

a general form of my algorithm follows:

def optimize(teams):
    for qb in qbs:
        iter_rb = itertools.combinations(rbs,2)
        for rb1, rb2 in iter_rb:
            iter_wr = itertools.combinations(wrs,3)
            for wr1, wr2, wr3 in iter_wr:
                for te in tes:
                    for dst in dsts:
                        baseSalary = qb['Salary'] + rb1['Salary'] + rb2['Salary'] + wr1['Salary'] + wr2['Salary'] + wr3['Salary'] + te['Salary'] + dst['Salary']
                        baseProjection = qb['Projection'] + rb1['Projection'] + rb2['Projection'] + wr1['Projection'] + wr2['Projection'] + wr3['Projection'] + te['Projection'] + dst['Projection']
                        if baseSalary <= maxSalary:
                            for rb3 in rbs:
                                salary = baseSalary + rb3['Salary']
                                if salary <= maxSalary:
                                    projection = baseProjection + rb3['Projection']
                                    if projection > teams[-1].projection:
                                        insertTeamAndReorderList()
                            for wr4 in wrs:
                                salary = baseSalary + wr4['Salary']
                                if salary <= maxSalary:
                                    projection = baseProjection + wr4['Projection']
                                    if projection > teams[-1].projection:
                                        insertTeamAndReorderList()
                            for te2 in tes:
                                salary = baseSalary + te2['Salary']
                                if salary <= maxSalary:
                                    projection = baseProjection + te2['Projection']
                                    if projection > teams[-1].projection:
                                        insertTeamAndReorderList()
    return teams

I feel like there is a more optimal solution, but I simply cannot figure out any more optimizations? Even when cutting wrs and rbs with low projections, this still takes a few hours to run.

Any ideas of where to look or confirmation that there isn't a more efficient solution would be very much appreciated. Thanks!

EDIT: For clarification, I loop through the wrs, tes, and rbs again inside of the dst loop to search for the flex player. This reduces the search space greatly instead of having a list of all flex eligible players.


Aucun commentaire:

Enregistrer un commentaire