With all of the daily fantasy games out there, I am looking to see if I can easily implement a platform that will help identify the optimal lineup for a fantasy league based on a salary cap and projected points for each player.
If given a pool of ~500 players and you need to find the highest scoring lineup of within the maximium salary cap restraints. 1 Quarter Back 2 Running Back 3 Wide Receiver 1 Tight End 1 Kicker 1 Defense
Each player is assigned a salary (that changes weekly) and I will assign projected points for those players. I have this information in a MySQL DB and would prefer to use PHP/Pear or JQuery if that's the best option for calculating this.
The Table looks something like this
player_id name position salary ranking projected_points
1 Joe Smith QB 1000 2 21.7
2 Jake Plummer QB 2500 6 11.9
I've tried sorting by projected points and filling in the roster, but it obviously will provide the highest scoring team, but also exceeds the salary cap. I cannot think of a way to have it intelligently remove players and continue to loop through and find the highest scoring lineup based on the salary constraints.
So, is there any PHP or Pear class that you know of that will help "Solve" this type of problem? Any articles you can point me to for reference? I'm not asking for someone to do this, but I've been Googleing for a while and the best solution I currently have is this. http://office.microsoft.com/en-us/excel-help/pick-your-fantasy-football-team-with-solver-HA001124603.aspx and that's using Excel and limited to 200 objects.
I'll suggest two approaches to this problem.
The first is dynamic programming. For brute force, we could initialize a list containing the empty partial team, then, for each successive player, for each partial team currently in the list, add a copy of that partial team with the new player, assuming that this new partial team respects the positional and budget constraints. This is an exponential-time algorithm, but we can reduce the running time by quite a lot (to O(#partial position breakdowns * budget * #players), assuming that all monetary values are integer) if we throw away all but the best possibility so far for each combination of partial position breakdown and budget.
The second is to find an integer programming library callable from PHP that works like Excel's solver. It looks like (e.g.) lpsolve comes with a PHP interface. Then we can formulate an integer program like so.
maximize sum_{player p} value_p x_p
subject to
sum_{quarterback player p} x_p <= 1
sum_{running back player p} x_p <= 2
...
sum_{defense player p} x_p <= 1
sum_{player p} cost_p <= budget
for each player p, x_p in {0, 1} (i.e., x_p is binary)