Show HN: Solve the best fantasy team with MiniZinc

#1

Post by d0m3 » Mon, Sep 25, 2023, 1:40 PM UTC

It's the rugby world cup at the moment, and there is a fantasy game for it. Someone started posting the best possible team after each round and I thought "how could I automate this?". I recalled a post I read here (https://www.hillelwayne.com/post/np-hard/) and that's where I found a reference to MiniZinc. I gave it a go and although it's not that easy to learn using only the docs, I was pleasantly surprised that I managed to make it work in less than a day. Pretty fun to play with the constraints to get different results and develop an understanding of what matters to pick a good team. The constraints are the following: - only 3 players per country - can't exceed a maximum budget based on each player cost - players have to be picked in their official position and there is a different number of slots for each position (8 positions, 15 slots) Happy to get some feedback and perhaps it can inspire others!

Show HN: Solve the best fantasy team with MiniZinc
github.com

Re: Show HN: Solve the best fantasy team with MiniZinc

#2

Post by mzl » Mon, Sep 25, 2023, 2:30 PM UTC

Interesting model! Testing it locally, I could see that one issue in the model is that there is a lot of symmetry to the results. Enforcing that players in the team are ordered was not useful and did not help. Enforcing that the team positions were ordered helped a lot though, by extracting the `[position[p] | p in team]` expression as a separate array `team_position` and enforcing increasing on it.

With HiGHS the solve-time went from 1m7s on my machine (M1 Max) to just 7.23s. The model is solved at the root node with this change, as opposed to 1430 nodes without it.

Using OR-Tools 9.7 with free search enabled (see Configuration editor in the MiniZinc IDE) with the new model took 10.3 seconds. With 10 threads it is solved in 1.56s.

Re: Show HN: Solve the best fantasy team with MiniZinc

#3

Post by d0m3 » Mon, Sep 25, 2023, 4:03 PM UTC

mzl wrote: post #2

Interesting model! Testing it locally, I could see that one issue in the model is that there is a lot of symmetry to the results. Enforcing that players in the team are ordered was not useful and did not help. Enforcing that the team positions were ordered helped a lot though, by extracting the `[position[p] | p in team]` expression as a separate array `team_position` and enforcing increasing on it. With HiGHS the so…

Thank you that is such a useful change! I wondered about symmetry but had no idea how to break it.

Re: Show HN: Solve the best fantasy team with MiniZinc

#4

Post by mzl » Mon, Sep 25, 2023, 4:36 PM UTC

d0m3 wrote: post #3

mzl wrote: post #2

Interesting model! Testing it locally, I could see that one issue in the model is that there is a lot of symmetry to the results. Enforcing that players in the team are ordered was not useful and did not help. Enforcing that the team positions were ordered helped a lot though, by extracting the `[position[p] | p in team]` expression as a separate array `team_position` and enforcing increasing on it. With HiGHS the so…

Thank you that is such a useful change! I wondered about symmetry but had no idea how to break it.

I realized that there is more to do in handling the team positions. Since the number of each position is fixed, the whole array of team_position can be replaced with a fixed set of integers.

With that change, it is also possible to add symmetry breaking on the player identifiers within each type of player position.

These two changes taken together makes the HiGHS solver taker around 3.2s on my machine, and OR-Tools with 10 threads takes 1.28s.