Home

Welcome to the GamesScheduler wiki!

GamesScheduler

Story time: My friend was organizing a tournament in an unknown board game. There is exactly 4 players in every game and he wanted to divide players into smaller groups and make sure that every player in a group played other player from the same group exactly twice. Sounds like a lot of fun right?

I was thinking how to solve this using as few lines of code as possible. Going through his conditions it became more and more clear: Linear programming.

I used a language MathProg (because it was one of the first results in google) and also it was easy enough to learn it in a day. Also I found a website that can run this for me: https://online-optimizer.appspot.com

I started simple with binary variables:

y[i, k] = 1 <=> player i is playing in game k;

y[i, k] = 0 <=> player i is not playing in game k;

this looks easy but then a funny problem appeared: how to make a linear condition that every two players have to play together in exactly two games?

Obvious way is for every players i,j: sum{through game k} y[i, k]*y[j, k] = 2;

You maybe noticed, this is not linear. Fuck. Ok then we need different variables, how about:

x[i, j, k] = 1 iff player i plays with player j in game k.

Looks good but there was a problem in another condition: Every game has exactly 4 players. Using these variables it seems it is unable to do. Fortunately, there is a tricky way how to tie together both x and y variables using linear inequations. We need to force a few things:

y[i, k] = 1 && y[j, k] = 1 <=> x[i, j, k] = 1

I was so lucky I figured out how to do it and made it kinda working. More details in the source code.