advent_or_day16.mzn

%% Method: we build a directed graph, with edges 
%% {from, to} representing a pair of consequent non-overlapping tasks. 
%% That is, `end_time(from) < start_time(to)`  
%% Then we constrain a list of tasks for each crew as a path in this graph.
%% Finally, we constrain the lists to be disjoint.

include "globals.mzn";

int: T;
int: C;
int: N;
int: E;

%% Tasks
set of int: TASKS = 1..T;
set of int: TASKS0 = 0..T;
%% Crews
set of int: CREWS = 1..C;

%% Pairs of non-overlapping tasks as edges
set of int: EDGES = 1..E;

array[EDGES] of int: from;
array[EDGES] of int: to;
array[EDGES] of int: weight;

array[CREWS, EDGES] of var bool: schedule_assignment;
array[CREWS, TASKS] of var bool: task_assignment;
array[CREWS] of var TASKS: first_assignment;
array[CREWS] of var TASKS: last_assignment;

array[CREWS] of var 0..sum(weight): crew_cost;

constraint forall(c in CREWS)(
    bounded_dpath(N,
      E,
      from,
      to,
      weight,
      first_assignment[c],
      last_assignment[c],
      row(task_assignment, c),
      row(schedule_assignment, c),
      crew_cost[c])
);

%% One crew per task
constraint forall(t in TASKS)(
  sum(col(task_assignment, t)) = 1
);

solve minimize(sum(crew_cost));

%% Optional: output

array[CREWS] of var set of TASKS: crew_tasks;
constraint forall(c in CREWS)(
  link_set_to_booleans(crew_tasks[c], row(task_assignment, c))
);
output ["crew: \(c), task(s): \(crew_tasks[c])\n" | c in CREWS] ++ ["\ntotal cost: \(_objective)"];  

% Solution (OR Tools CP-Sat)
crew: 1, task(s): 1
crew: 2, task(s): 2
crew: 3, task(s): 3
crew: 4, task(s): 4
crew: 5, task(s): 5
crew: 6, task(s): 6
crew: 7, task(s): 7
crew: 8, task(s): 8
crew: 9, task(s): 9
crew: 10, task(s): 10
crew: 11, task(s): 11
crew: 12, task(s): 12
crew: 13, task(s): 13
crew: 14, task(s): 14
crew: 15, task(s): 15
crew: 16, task(s): 16
crew: 17, task(s): 17
crew: 18, task(s): 18
crew: 19, task(s): 19
crew: 20, task(s): 20
crew: 21, task(s): 21
crew: 22, task(s): 22
crew: 23, task(s): 23
crew: 24, task(s): 24.
crew: 25, task(s): 25
crew: 26, task(s): 26
crew: 27, task(s): 27
crew: 28, task(s): {28,41}
crew: 29, task(s): {29,42}
crew: 30, task(s): {30,45}
crew: 31, task(s): {31,36,46}
crew: 32, task(s): {32,47}
crew: 33, task(s): {33,39,48}
crew: 34, task(s): {34,38,40,44,49}
crew: 35, task(s): {35,37,43,50}

total cost: 0

==========
Finished in 1m 30s.