this repo has no description
dekker.one
1/***
2!Test
3solvers: [gecode]
4expected:
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
48include "all_different.mzn";
49
50int: numActors; % number of actors
51int: numScenes; % numer of scenes
52
53%-- Types ---------------------------------------------------------------------
54set of int: Actors = 1..numActors;
55set of int: Scenes = 1..numScenes;
56
57array[Actors,Scenes] of 0..1: ia; % 01 definition of actors in scenes
58array[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
60array[Scenes] of int: d; % duration of each scene
61array[Actors] of int: c; % cost of each actor
62
63numScenes = 6;
64numActors = 4;
65ia = [|
661,0,0,0,1,1|
671,1,0,1,0,0|
680,1,1,0,1,0|
690,0,1,1,0,1|];
70c = [1,1,1,1];
71d = [1,2,3,4,5,6];
72
73%-- Decision variables --------------------------------------------------------
74
75array[Scenes] of var Scenes: s :: add_to_output; % schedule of scenes
76
77%-- Auxilliary variables ------------------------------------------------------
78
79array[Scenes] of var set of Actors: bef :: add_to_output; % actors appearing before time t
80array[Scenes] of var set of Actors: aft :: add_to_output; % actors appearing after time t
81array[Scenes] of var set of Actors: dur :: add_to_output; % actors on set at time t
82
83var int: cost :: add_to_output;
84
85%-- Constraints ---------------------------------------------------------------
86
87constraint all_different(s); % each scene scheduled once
88
89constraint
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
96constraint
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
103constraint 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
110constraint s[1] < s[numScenes];
111
112%-- Solving objective and solution output -------------------------------------
113
114solve :: int_search(s, first_fail, indomain, complete)
115 minimize cost;