3
$\begingroup$

This is a "fun" optimization problem that was prompted by an NFL betting pool. Each week you pick one team to win. If that team wins you stay in the game. If it loses you're out. The catch is that you can not pick the same team twice. For those of you unfamiliar with American football, there are 32 teams and 17 weeks in the season. Each team (nominally) plays one game per week.

I thought it would be fun to try to optimize my pick strategy by using a ranking of the 32 teams. I then used a likelihood-to-win metric as the difference in the team rank. You can then make a 17x32 array of likelihood-to-win values. I would like to maximize the cumulative likelihood-to-win value over the 17-week season.

Oddly enough I was able to do with in Excel using the Solver add-in and assuming the chosen teams were picked from the (current) top 17.

However, I hate Excel and would love to do this in Mathematica.

It seems like a variation of the Traveling Salesman problem or at least a common problem in combinatorial optimization. Unfortunately I am at a loss how to fit this into Mathematica. I was thinking I could use FindShortestTour with a DistanceFunction related to the likelihood-to-win metric. However, I cannot seem to determine how to set up the problem to use this method.

I thought it would be a fun challenge for someone with much greater knowledge in optimization, and it's been stymying me for a few days. I don't want to be able to do an optimization problem in Excel without knowing how to do it in Mathematica ;-).

Update

Nothing's fun to start from scratch so as suggested I explored this a bit more. First, here is a link to the Excel spreadsheet.

https://www.dropbox.com/s/qkv7tae2skimsks/NFL.xlsx?dl=0

It contains pre-season rankings and was not made for public scrutiny ;-) However, it will let people understand the problem better. There are three "optimized" solutions. One is based on pure ranking, one considers home/away bias, and one considers that the rankings are less helpful the farther into the season one gets. (I plan to update the rankings and re-optimize each week.)Excel Solver setup.

I used the Solver add-in for Excel with the setting shown in the screenshot. The default algorithm options were used. I have not done any timing benchmarks but Excel solved the problem in a handful of minutes. Again, note this is an overly constrained problem assume you pick only from the (current) top 17 teams. I'm not sure how to make Excel pick from all the teams.

I also got something running in Mathematica based on Daniel Lichtblau's nice paper "Differential Evolution in Discrete and Combinatorial Optimization: Mathematica tutorial notes". In particular, I used the Ordering method to generate candidate solutions.

First I made a simple "weeks" array:

weeks = Range[17];

The objective function (following Lichtblau) is:

spfun[vec : {__Real}] := With[{vals = Take[Ordering[vec], 17]}, Total[(data[[#1[[1]], #1[[2]] + 1]] &) /@ Transpose[Join[{vals}, {weeks}]]]]

Note: data is below.

Randomly guessing over 10000 schedules:

Max[Map[spfun[#] &, RandomReal[1, {10000, 32}]]]

gave me a best score of 181.

The optimization problem is then:

vars = Array[xx, 32];
ranges = ({#1, 0, 1} &) /@ vars;
picks[cp_, sp_] := Module[{sol, orderSol}, sol = NMaximize[spfun[vars], ranges, Method -> {"DifferentialEvolution", "CrossProbability" -> cp, "SearchPoints" -> sp}, MaxIterations -> 10000]; orderSol = Take[Ordering[Array[xx, 32] /. sol[[2]]], 17]; {sol[[1]], (data[[#1[[1]], #1[[2]] + 1]] &) /@ Transpose[Join[{orderSol}, {weeks}]], data[[orderSol, 1]]}]

I played around with CrossProbability and SearchPoints and found 0.9 and 300 to work well. The optimal best solution gave a value of 352 with picks:

{"CAR", "OAK", "PIT", "GB", "MIN", "HOU", "DAL", "ATL", "ARI", "NYG", "DET", "SEA", "KC", "DEN", "TEN", "NE", "TB"}

It took 790 seconds on my 2.6 GHz Intel Core i7 MacBook Pro; much longer than Excel. However, this optimized over all teams, not just the best. The score of 352 is slightly (by one point) better than what Excel found. Note that the Mma optimization includes DET (my hometown team that I know never to bet on) which is not in the top 17 teams in the rankings.

It seems to me there should be a better way to do the optimization. The methods Lichtblau presented (in 2009) do not use all the new functionality of Mma, I believe.

{{"NYJ", -6, -25, -7, -4, -2, -31, -7, -30, -6, -19, 
  0, -16, -24, -23, -9, -8, -31}, {"SF", -15, -28, -4, -21, -13, -11,
-25, -16, -21, -20, 
  0, -28, -2, -17, -19, -3, -4}, {"CLE", -26, -9, -12, -8, 
  2, -16, -18, -13, 
  0, -11, -2, -8, -6, -25, -9, -1, -26}, {"CHI", -27, -16, -25, -24,
-12, -8, -13, -6, 0, -24, -10, -14, 2, -7, -10, 
  1, -12}, {"JAX", -14, -16, -7, 4, -24, -1, -10, 0, -6, -4, 
  2, -18, -10, -25, -14, 3, -16}, {"LAR", -9, -7, 4, -21, -24, 1, -17,
   0, -16, -13, -10, -4, -17, -12, -24, -15, 4}, {"BUF", 
  6, -10, -17, -24, -4, 0, -13, -19, 
  6, -3, -2, -18, -25, -8, -1, -25, -1}, {"MIA", -12, -1, 
  7, -2, -13, -23, 7, -4, -18, -9, 0, -24, -16, -24, 1, -17, 
  1}, {"LAC", -15, 1, -16, -9, -13, -17, -15, -23, 0, 4, 2, -18, 
  6, -4, -16, 8, -17}, {"NO", -6, -22, -7, 2, 0, -4, -18, 6, -10, 
  3, -3, 4, -7, -21, 9, -21, -10}, {"CIN", -1, -8, -17, 8, 4, 
  0, -18, -4, 6, -10, -13, 8, -18, 7, -5, -3, -1}, {"BAL", 1, 9, 
  7, -17, -14, 8, -4, 4, -9, 0, -16, -7, -2, -17, 9, -3, 
  1}, {"WSH", -5, 7, -13, -12, 0, 11, -5, -14, -17, -3, 3, -9, -14, 
  4, -10, -11, -9}, {"DET", -9, -8, -17, -2, -3, 4, 0, -15, -14, 11, 
  10, -2, 2, -6, 10, 3, -14}, {"IND", 9, -8, 12, -15, 13, -6, 10, 
  4, -4, -14, 0, -6, 10, 8, -9, 3, -4}, {"MIN", 6, -13, -4, 2, 
  12, -12, 4, 13, 0, 3, 10, 2, -15, -1, 5, -12, 12}, {"CAR", 15, 10, 
  7, -15, 3, -1, 13, -3, -14, 9, 0, 16, 7, 1, -11, -3, -14}, {"PHI", 
  5, -7, -4, 9, -5, 1, 5, 16, -6, 0, -9, 14, -12, 
  12, -4, -8, -9}, {"HOU", 14, 8, -13, -2, -6, 16, 0, -11, 4, 13, -4, 
  7, -2, 17, 14, -10, 4}, {"TB", 12, 16, 4, -2, -12, -3, 13, 3, 10, 
  19, 0, -11, -8, 6, -11, 3, 10}, {"TEN", -5, 16, -9, 2, 13, 6, 18, 0,
   9, 10, -8, 6, 2, -2, 19, 15, 16}, {"NYG", -5, 8, 4, 2, 13, -2, -8, 
  0, 16, 20, -3, 9, -4, -5, 4, -1, 9}, {"ARI", 9, 8, -4, 21, 5, 3, 17,
   0, 21, -7, 4, 18, 17, 2, 10, 1, -7}, {"DEN", 15, -3, 17, -2, 0, 2, 
  15, -1, 6, -8, 13, -2, 16, 23, 9, 11, -1}, {"KC", -7, 7, 16, 12, 
  6, -4, -1, 1, -2, 0, 3, 18, 24, -1, 16, 17, 1}, {"OAK", 5, 25, 13, 
  2, 14, 17, 1, 19, 18, 0, -6, 2, 4, 1, -1, 8, 17}, {"DAL", 5, 3, 4, 
  21, -1, 0, 25, 14, 2, -4, 9, 18, 14, 5, 1, -3, 9}, {"GB", -2, -3, 
  17, 24, 1, 12, 18, 0, 14, 24, 16, -1, 8, 25, 11, 12, 14}, {"PIT", 
  26, 13, 25, 17, 24, 4, 18, 15, 0, 14, 8, 1, 18, 17, -3, 10, 
  26}, {"SEA", 2, 28, 9, 15, 24, 0, 8, 11, 17, 7, -1, 28, 12, 25, 24, 
  3, 7}, {"ATL", 27, 3, 17, 24, 0, 23, -1, 30, 14, 4, 1, 11, 15, 21, 
  11, 21, 14}, {"NE", 7, 22, 13, 15, 12, 31, 1, 23, 0, 8, 6, 24, 25, 
  24, 3, 25, 31}}
$\endgroup$
  • 5
    $\begingroup$ This does seem like a fun problem, but perhaps not fun enough to start from scratch :) Could you provide at least a sketch (perhaps pseudocode?) of the method you used with Excel? It would also be nice if you could give us some sample data, and set up the same matrix you did in Excel. I can't speak for everyone, but I'd guess many (most?) users on this site would be more likely to help you if you put a bit more Mathematica-specific effort into your post. $\endgroup$ – jjc385 Sep 8 '17 at 3:29
  • 1
    $\begingroup$ I have added (much) more information. $\endgroup$ – EricMock Sep 9 '17 at 0:11
  • $\begingroup$ Question appears to be dead. I would have thought this could have been cast into a Traveling Salesman problem, but perhaps not. If it could I would assume it would be faster. While the method presented works, it just does seem very elegant. $\endgroup$ – EricMock Sep 13 '17 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.