Show HN: Solve the best fantasy team with MiniZinc

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

3 points by d0m3 2 years ago | 3 comments

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!

mzl 2 years ago |

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.

d0m3 2 years ago | |

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

mzl 2 years ago | | |

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.