| 1 |
/*** |
| 2 |
!Test |
| 3 |
solvers: [gecode] |
| 4 |
expected: |
| 5 |
- !Result |
| 6 |
status: OPTIMAL_SOLUTION |
| 7 |
solution: !Solution |
| 8 |
cost: 48 |
| 9 |
s: [4, 1, 2, 3, 6, 5] |
| 10 |
dur: [!!set {2, 4}, !!set {1, 2, 4}, !!set {1, 3, 4}, !!set {1, 3, 4}, !!set {1, 3}, !!set {1, 3}] |
| 11 |
bef: [!!set {}, !!set {2, 4}, !!set {1, 2, 4}, !!set {1, 2, 3, 4}, !!set {1, 2, 3, 4}, !!set {1, 2, 3, 4}] |
| 12 |
aft: [!!set {1, 2, 3, 4}, !!set {1, 2, 3, 4}, !!set {1, 3, 4}, !!set {1, 3, 4}, !!set {1, 3}, !!set {}] |
| 13 |
a: [!!set {1, 2}, !!set {2, 3}, !!set {3, 4}, !!set {2, 4}, !!set {1, 3}, !!set {1, 4}] |
| 14 |
- !Result |
| 15 |
status: OPTIMAL_SOLUTION |
| 16 |
solution: !Solution |
| 17 |
cost: 48 |
| 18 |
s: [4, 1, 2, 3, 6, 5] |
| 19 |
dur: [!!set {2, 4}, !!set {1, 2, 4}, !!set {1, 3, 4}, !!set {1, 3, 4}, !!set {1, 3}, !!set {1, 3}] |
| 20 |
bef: [!!set {}, !!set {2, 4}, !!set {1, 2, 4}, !Range 1..4, !Range 1..4, !Range 1..4] |
| 21 |
aft: [!Range 1..4, !Range 1..4, !!set {1, 3, 4}, !!set {1, 3, 4}, !!set {1, 3}, !!set {}] |
| 22 |
a: [!Range 1..2, !Range 2..3, !Range 3..4, !!set {2, 4}, !!set {1, 3}, !!set {1, 4}] |
| 23 |
- !Result |
| 24 |
status: OPTIMAL_SOLUTION |
| 25 |
solution: !Solution |
| 26 |
cost: 48 |
| 27 |
s: [5, 3, 2, 1, 4, 6] |
| 28 |
dur: [!!set {1, 3}, !!set {1, 3, 4}, !!set {1, 2, 4}, !!set {1, 2, 4}, !!set {1, 4}, !!set {1, 4}] |
| 29 |
bef: [!!set {}, !!set {1, 3}, !!set {1, 3, 4}, !Range 1..4, !Range 1..4, !Range 1..4] |
| 30 |
aft: [!Range 1..4, !Range 1..4, !!set {1, 2, 4}, !!set {1, 2, 4}, !!set {1, 4}, !!set {}] |
| 31 |
a: [!Range 1..2, !Range 2..3, !Range 3..4, !!set {2, 4}, !!set {1, 3}, !!set {1, 4}] |
| 32 |
- !Result |
| 33 |
status: OPTIMAL_SOLUTION |
| 34 |
solution: !Solution |
| 35 |
cost: 48 |
| 36 |
s: [4, 1, 2, 3, 5, 6] |
| 37 |
dur: [!!set {2, 4}, !!set {1, 2, 4}, !!set {1, 3, 4}, !!set {1, 3, 4}, !!set {1, 4}, !!set {1, 4}] |
| 38 |
bef: [!!set {}, !!set {2, 4}, !!set {1, 2, 4}, !Range 1..4, !Range 1..4, !Range 1..4] |
| 39 |
aft: [!Range 1..4, !Range 1..4, !!set {1, 3, 4}, !!set {1, 3, 4}, !!set {1, 4}, !!set {}] |
| 40 |
a: [!Range 1..2, !Range 2..3, !Range 3..4, !!set {2, 4}, !!set {1, 3}, !!set {1, 4}] |
| 41 |
***/ |
| 42 |
|
| 43 |
% mzn2fzn and minizinc aborted on this model with an error message about |
| 44 |
% being unable to compute set bounds. This was fixed in r8782. |
| 45 |
% (This is derived from the talent scheduling model in the MiniZinc |
| 46 |
% benchmarks.) |
| 47 |
|
| 48 |
include "all_different.mzn"; |
| 49 |
|
| 50 |
int: numActors; % number of actors |
| 51 |
int: numScenes; % numer of scenes |
| 52 |
|
| 53 |
%-- Types --------------------------------------------------------------------- |
| 54 |
set of int: Actors = 1..numActors; |
| 55 |
set of int: Scenes = 1..numScenes; |
| 56 |
|
| 57 |
array[Actors,Scenes] of 0..1: ia; % 01 definition of actors in scenes |
| 58 |
array[Scenes] of set of Actors: a :: add_to_output = |
| 59 |
[ { j | j in Actors where ia[j,i] == 1} | i in Scenes] ; % actors for each scene |
| 60 |
array[Scenes] of int: d; % duration of each scene |
| 61 |
array[Actors] of int: c; % cost of each actor |
| 62 |
|
| 63 |
numScenes = 6; |
| 64 |
numActors = 4; |
| 65 |
ia = [| |
| 66 |
1,0,0,0,1,1| |
| 67 |
1,1,0,1,0,0| |
| 68 |
0,1,1,0,1,0| |
| 69 |
0,0,1,1,0,1|]; |
| 70 |
c = [1,1,1,1]; |
| 71 |
d = [1,2,3,4,5,6]; |
| 72 |
|
| 73 |
%-- Decision variables -------------------------------------------------------- |
| 74 |
|
| 75 |
array[Scenes] of var Scenes: s :: add_to_output; % schedule of scenes |
| 76 |
|
| 77 |
%-- Auxilliary variables ------------------------------------------------------ |
| 78 |
|
| 79 |
array[Scenes] of var set of Actors: bef :: add_to_output; % actors appearing before time t |
| 80 |
array[Scenes] of var set of Actors: aft :: add_to_output; % actors appearing after time t |
| 81 |
array[Scenes] of var set of Actors: dur :: add_to_output; % actors on set at time t |
| 82 |
|
| 83 |
var int: cost :: add_to_output; |
| 84 |
|
| 85 |
%-- Constraints --------------------------------------------------------------- |
| 86 |
|
| 87 |
constraint all_different(s); % each scene scheduled once |
| 88 |
|
| 89 |
constraint |
| 90 |
bef[1] = {} /\ % no actors before time 1 |
| 91 |
aft[numScenes] = {} /\ % no actors after time numScenes |
| 92 |
forall(t in 1..numScenes-1)( |
| 93 |
bef[t+1] = a[s[t]] union bef[t] /\ |
| 94 |
aft[t] = a[s[t+1]] union aft[t+1] ); |
| 95 |
|
| 96 |
constraint |
| 97 |
dur[1] = a[s[1]] /\ |
| 98 |
forall(t in 2..numScenes-1)( |
| 99 |
dur[t] = bef[t+1] intersect aft[t] |
| 100 |
) /\ |
| 101 |
dur[numScenes] = a[s[numScenes]]; |
| 102 |
|
| 103 |
constraint cost = sum(i in Scenes)( |
| 104 |
sum(j in Actors)( |
| 105 |
c[j] * d[s[i]] * bool2int(j in dur[i]) |
| 106 |
) |
| 107 |
); |
| 108 |
|
| 109 |
%-- symmetry breaking constraint |
| 110 |
constraint s[1] < s[numScenes]; |
| 111 |
|
| 112 |
%-- Solving objective and solution output ------------------------------------- |
| 113 |
|
| 114 |
solve :: int_search(s, first_fail, indomain, complete) |
| 115 |
minimize cost; |