combinatorics - MiniZinc - Optimizing Script for Scheduling Problem - Stack Overflow

The following code generates a schedule that fits the following scenario:

An event is taking place with 8 stations and 24 teams. There are 3 teams at a station at a time. There are exactly 8 rotations, and every team must visit each of the 8 stations in the 8 rotations. No team can repeat a station, and all teams must be at a station during each rotation. Furthermore, each team cannot see another team more than once throughout the whole event. For example, if team 1 saw team 2 and 3 at station 1, team 1 cannot be with team 2 or 3 at any of the future stations. (Implies that a team will not be able to see every team, but the goal is that each team competes against as many different teams as possible).

include "alldifferent.mzn";

int: num_teams = 24;         % Number of teams
int: num_stations = 8;       % Number of stations
int: num_rotations = 8;      % Number of rotations
int: teams_per_station = 3;  % Teams per station per rotation

% Decision variable: station assignments
array[1..num_teams, 1..num_rotations] of var 1..num_stations: station;

% Constraints
constraint
    % Each team visits exactly one station in each rotation
    forall(t in 1..num_teams, r in 1..num_rotations) (
        station[t, r] >= 1 /\ station[t, r] <= num_stations
    )
    /\
    % No team visits the same station more than once
    forall(t in 1..num_teams, s in 1..num_stations) (
        sum([station[t, r] == s | r in 1..num_rotations]) <= 1
    )
    /\
    % Each station accommodates exactly teams_per_station teams per rotation
    forall(r in 1..num_rotations, s in 1..num_stations) (
        sum([station[t, r] == s | t in 1..num_teams]) == teams_per_station
    )
    /\
    % Teams do not see each other more than once
    forall(t1 in 1..num_teams, t2 in 1..num_teams where t1 != t2) (
        sum([station[t1, r] == station[t2, r] | r in 1..num_rotations]) <= 1
    );

% Objective: Maximize team diversity by minimizing the number of repeat encounters
solve satisfy;

% Output the station assignments
output [
    "Team " ++ show(t) ++ ": " ++ show([station[t, r] | r in 1..num_rotations]) ++ "\n"
    | t in 1..num_teams
];

The code works for smaller numbers (ex. 15 teams, 5 stations and rotations, 3 teams per station), but I need it to finish running for a solution to 24 teams, 8 stations and rotations, and 3 teams per station). I ran for 18 hours, and it still didn't compute.

I tried combining the first 2 constraints using alldifferent, but was unsuccessful. Does anyone have an idea on how to get this to compute in a reasonable amount of time?

The following code generates a schedule that fits the following scenario:

An event is taking place with 8 stations and 24 teams. There are 3 teams at a station at a time. There are exactly 8 rotations, and every team must visit each of the 8 stations in the 8 rotations. No team can repeat a station, and all teams must be at a station during each rotation. Furthermore, each team cannot see another team more than once throughout the whole event. For example, if team 1 saw team 2 and 3 at station 1, team 1 cannot be with team 2 or 3 at any of the future stations. (Implies that a team will not be able to see every team, but the goal is that each team competes against as many different teams as possible).

include "alldifferent.mzn";

int: num_teams = 24;         % Number of teams
int: num_stations = 8;       % Number of stations
int: num_rotations = 8;      % Number of rotations
int: teams_per_station = 3;  % Teams per station per rotation

% Decision variable: station assignments
array[1..num_teams, 1..num_rotations] of var 1..num_stations: station;

% Constraints
constraint
    % Each team visits exactly one station in each rotation
    forall(t in 1..num_teams, r in 1..num_rotations) (
        station[t, r] >= 1 /\ station[t, r] <= num_stations
    )
    /\
    % No team visits the same station more than once
    forall(t in 1..num_teams, s in 1..num_stations) (
        sum([station[t, r] == s | r in 1..num_rotations]) <= 1
    )
    /\
    % Each station accommodates exactly teams_per_station teams per rotation
    forall(r in 1..num_rotations, s in 1..num_stations) (
        sum([station[t, r] == s | t in 1..num_teams]) == teams_per_station
    )
    /\
    % Teams do not see each other more than once
    forall(t1 in 1..num_teams, t2 in 1..num_teams where t1 != t2) (
        sum([station[t1, r] == station[t2, r] | r in 1..num_rotations]) <= 1
    );

% Objective: Maximize team diversity by minimizing the number of repeat encounters
solve satisfy;

% Output the station assignments
output [
    "Team " ++ show(t) ++ ": " ++ show([station[t, r] | r in 1..num_rotations]) ++ "\n"
    | t in 1..num_teams
];

The code works for smaller numbers (ex. 15 teams, 5 stations and rotations, 3 teams per station), but I need it to finish running for a solution to 24 teams, 8 stations and rotations, and 3 teams per station). I ran for 18 hours, and it still didn't compute.

I tried combining the first 2 constraints using alldifferent, but was unsuccessful. Does anyone have an idea on how to get this to compute in a reasonable amount of time?

• combinatorics
• minizinc

Share Improve this question Follow asked yesterday tangulotangulo 1 New contributor tangulo is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. 3

• By 'each team cannot see another team more than once throughout the whole event.' do you mean each team never shares a station with the same team more than once in the 8 rotations? – Simon Goater Commented 21 hours ago
• @SimonGoater That is correct. – tangulo Commented 15 hours ago
• The complexity of this problem appears to become catastrophic pretty quickly. You could use a greedy depth first search type algorithm to find the 'best solution so far' in whatever time you allow, but you would have to relax some constraints. Have you tried solving for 7 rounds 8 stations, 24 teams? I can get 6-8-24 easily with my test program, but 7-8-24 was taking too long so I stopped it.. – Simon Goater Commented 2 hours ago

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

This is my attempt to tweak your model:

int: num_teams = 15; % 24;         % Number of teams
int: num_stations = 5; % 8;       % Number of stations
int: num_rotations = 5; % 8;      % Number of rotations
int: teams_per_station = 3;  % Teams per station per rotation

%  for brevity
set of int: Teams = 1..num_teams;
set of int: Stations = 1..num_stations;
set of int: Rotations = 1..num_rotations;

% Decision variable: station assignments
array[Teams, Rotations] of var Stations: station;

predicate atmostone(array[int] of var bool:x) =
          forall(i,j in index_set(x) where i < j)(
            (not x[i] \/ not x[j]));
            
% Constraints
constraint
    % No team visits the same station more than once
    forall(t in Teams, s in Stations) (
        atmostone([station[t, r] == s | r in Rotations])
    )
    /\
    % Each station accommodates exactly teams_per_station teams per rotation
    forall(r in Rotations, s in Stations) (
        sum([station[t, r] == s | t in Teams]) == teams_per_station
    )
    /\
    % Teams do not see each other more than once
    forall(t1 in Teams, t2 in Teams where t1 < t2) (
        atmostone([station[t1, r] == station[t2, r] | r in Rotations])
    );

% Output the station assignments
output [
    "Team " ++ show(t) ++ ": " ++ show([station[t, r] | r in Rotations]) ++ "\n"
    | t in Teams
];

The first constraint was omitted as it is already implied by the domain of station. In the last constraint, I reduced the number of cases. I am not sure if amostone() is actually faster than sum() <= 1.