Clever Geek Handbook

Combinatorics - schedule of team associations for the game

TL; DR

I would like to distribute players through the various activities of the game.
There are a fixed number of rounds a team can play during a game.
Major Limitations: Each Teammust play every game , but every teammust not play against all teams .

I've searched the internet for answers, but they all involve tournaments that don't have the same restrictions as me.

You can now skip the next two sections.

Introduction

I am involved in organizing a huge game, and I have a responsibility to distribute the players through various actions during the game. When I realized that it was not an easy task to solve, I tried to code a Python script to make it work. Then I realized I was doing it wrong, because my script was working in a deterministic way. People told me that I should do it with a solver (Constraint Programming). However, I had no clue in this area. He tried using the python-constraint package to solve my problem, but I was unable to identify good constraints.

The suits that I have completed

I have also searched the internet for this problem, but most of the answers I have found have to do with tournaments that do not have the same restrictions as me. Indeed, the main goal of the tournament is to make sure that each team plays against all other teams. The main limitation here is to make sure that every team plays at every event. I found a similar thread on math.stackexchange, but the limits were not the same and there was no proper answer to the problem.

Inputs

  • 36 teams .
  • 22 actions . (there are duels)
  • 22 rounds .

Limitations

  • The team cannot play against itself .
  • Every team must play in every activity .
  • A team cannot perform more than 22 actions during a game. (since there are only 22 rounds)
  • Minimize teams playing against a team they have already played with.

Since there are 36 teams in 22 matches, some actions will be empty in each round.
Since there are 22 events and 22 rounds, a team cannot perform their activity more than once.

Example of a likely response

       | Round 1        | Round 2        | Round n        
------ | -------------- | -------------- | --------------  
Game 1 | Team1 vs Team2 | Team3 vs Team5 | Team? vs Team?  
Game 2 | Team3 vs Team4 | Team1 vs Team6 | Team? vs Team?  
Game n | Team? vs Team? | Team? vs Team? | Team? vs Team?

The problem model in Python

from constraint import *

problem = Problem()
problem.addVariable("Activity", [i for i in range(1, 22+1)])
problem.addVariables(["Team1", "Team2"], [i for i in range(1, 36+1)])
problem.addVariable("Round", [i for i in range(1, 22+1)])
problem.addConstraint(lambda a, b: a != b, ("Team1", "Team2"))
???

My question

I'm looking for someone who could:

  • determine what constraints I should use for my problem.
  • or solve this problem with combinatorics .

It can be any language or any tool. I used Python as an example.

Any help would be much appreciated. Thank you in advance!

+3


source to share


2 answers


Your question is not trivial at all, but I will try to approach it. :) I will try to define the problem in terms of the feasibility of the constraint. I'll rely on logical feasibility and use the Zeintin Transform to encode your task.

First of all, let's introduce a set of Boolean variables that correspond to the game that the team played during the round:

game0_team0_round0, g0_t0_r1, ..., gk_tm_rn

We will encode the constraints as a boolean formula. It returns True if there is a schedule that meets all the given constraints. The set of values ​​for the variables defined above is a graph: if the variable is True , then the game was played by the corresponding team in the corresponding round. We introduce many restrictions. Suppose that if the constraint formula returns True , then this constraint is violated.

The first restriction prohibits a team from playing multiple games in a round:

for round in rounds:
    for team in teams:
        games = get_games_from_team_and_round (round, team)
        constr = greater_then_equal (games, 2)
        add_must_be_false_constr (constr)

'large_then_equal' builds pseudo-boolean constraints that ensure that only one game can be True per team / round. You can read here how to implement it. 'add_must_be_false_constr' ensures that the constraint is not violated.

Next, let's introduce a duel limitation: two teams must play in a round. At the same time, they must play the same game:



for round in rounds:
    for game in games:
        teams = get_teams_from_round (round)
        constr = greater_then_equal (teams, 3)
        add_must_be_false_constr (constr)

Finally, every team must play every game:

for round in rounds:
    for team in teams:
        games = get_games_from_team_and_round (round, team)
        constr = boolean_or (games)
        add_must_be_false_constr (constr)

We guarantee that at least one game will be played in every round.

You can put the resulting formula in a solver (like Glucose ), it will find you a random graph that satisfies all the given constraints.

Now the tricky part is minimization. I'm not sure how to do this correctly, but, for example, you can enter the variable True if a couple of teams played a game during a given round. Then you introduce the 'more_then_equal' constraint to limit the number of True values for these variables. Finally, you can use guesswork to find the best schedule with the least repetition.

Keep in mind that this approach can take a long time to solve the problem: it is not trivial to get everything right, so I am not providing your code, but just giving you a fairly general description of how to do it. It can take up to several hours to resolve the problem, but it depends on the problem itself and the limitations. Another problem is that it can consume a lot of memory. I have practical experience of solving very large (10 ^ 4 variables, 10 ^ 6 constraints) by doing things like this. Good luck!

0


source


Here's the solution at MiniZinc . Here are the main ideas:

1) Variable decisions to handle the teams to play when it is a 3-dimensional array of the x

size of the number of operations x the number of rounds x 2 and contains two teams that are playing in a specific activity and round. Since there can be "zero" games, i.e. Round / Activity when no team is playing in the domain is 0 .. the number of teams where "team" 0 indicates zero play. We also add the constraint that if one team of the game is team 0, then the other team must also be team 0: (x[a,r,1] = 0 <-> x[a,r,2] = 0)

where it <->

indicates the implications.

2) For the restrictions that all teams must participate in all activities and in all rounds, only two (global) restrictions are needed: global_cardinality

which counts the number of times a team participates in activities and rounds respectively.

3) The goal of the problem is to minimize the number of "double" games between teams. For this, a 2-dimensional matrix is ​​used y

: it contains the number of matches that two teams play against each other. The target of the model z

counts the number of double pieces, which we then minimize. However, it seems that there is no need for any double games at all, and hence the area y

is only 0..1, meaning either the two teams play each other once or not. Since the domain is 1, this effectively constrains the model so as not to allow for any double games at all. Note. I don't know if this works for all different values ​​for the number of commands x actions x rounds, but it works for different instances I've tested, including the 32 x 22 x 22 instance in the question.

include "globals.mzn"; 
int: num_teams = 36;
int: num_activities = 22;
int: num_rounds = 22;

% decision variables
%  x[a,r,1..2] = t1..t2: team t1 and team t2 plays in activity a, round r
% 0 mean an empty game
array[1..num_activities, 1..num_rounds, 1..2] of var 0..num_teams: x;

% number of plays against the other teams
array[1..num_teams, 1..num_teams] of  var 0..1: y;
% number of plays where a team meet another team more than once
var 0..(num_teams*(num_teams-1)) div 2: z; %  = sum([y[t1,t2] > 1 | t1,t2 in 1..num_teams where t1 < t2]);

% minimize the number of "double" matches between the teams
solve :: int_search(array1d(x), most_constrained, indomain_min, complete) minimize z;

constraint
    % the number of times the teams play against each other
    forall(t1 in 1..num_teams) ( 
        y[t1,t1] = 0 % a team do not play against itself
        /\
        forall(t2 in 1..num_teams where t1 < t2) (
             y[t1,t2] = sum([x[a,r,1] = t1 /\ x[a,r,2] = t2 | a in 1..num_activities, r in 1..num_rounds])
             /\
             y[t2,t1] = y[t1,t2] % symmetric matrix
        )
    )
    /\
    z = sum([y[t1,t2] > 1 | t1,t2 in 1..num_teams where t1 < t2])

    % /\ z = 0
    ;

    constraint
       % a team must participate in all activities
       forall(a in 1..num_activities) (
          global_cardinality([x[a,r,i] | r in 1..num_rounds, i in 1..2],1..num_teams,[1 | r in 1..num_teams]) :: domain
      )

      /\ % a team must participate in all rounds
      forall(r in 1..num_rounds) (
            global_cardinality([x[a,r,i] | a in 1..num_activities, i in 1..2],1..num_teams,[1 | r in 1..num_teams]) :: domain
      )

      /\ % null games "team" 0 vs "team" 0
      forall(a in 1..num_activities,r in 1..num_rounds) (
          (x[a,r,1] = 0 <-> x[a,r,2] = 0)
       )
       ;

       output 
       [ "z:\(z)\n" ] ++
       [
         if r = 1 then "\n" else "" endif ++
            "\(a)-\(r): \(x[a,r,1]) vs \(x[a,r,2])\n"
         | a in 1..num_activities, r in 1..num_rounds
       ]
       ++
       [ % the play matrix
          if t2 = 1 then "\n" else "" endif ++
            show_int(2,y[t1,t2]) ++ " "
          | t1,t2 in 1..num_teams
       ]
       ++ [ "\n\nz:\(z)\n" ];

The Gecode solver solves the problem in 8 seconds (and the creation time for the FlatZinc model takes about a minute). For a smaller task of 18 teams x 11 activities x 11 rounds, it takes 4 seconds (including flattening to FlatZinc).



The model is also here: http://hakank.org/minizinc/schedule_team_associations_for_a_game.mzn . It includes some of the comments I've tested, for example. various constraints on symmetry breaking, but this rather scaled model seems to be the fastest. The order of the teams in action and the round in the solution seems to be random. If this issue helps some constraints of symmetry constraints (but it may take longer time).

The solution is too big to show here, but saved at http://hakank.org/minizinc/schedule_team_associations_for_a_game.txt

Also, since it stands, the model is a minimization problem and will only show one solution. If more / many solutions are required, only two changes are required:

1) Change solve ... minimize z

to solve satisfy

.

2) Uncomment the line z = 0

.

0


source






More articles:


All Articles