this repo has no description
dekker.one
1% RUNS ON mzn20_fd
2% RUNS ON mzn-fzn_fd
3% RUNS ON mzn20_mip
4
5% Regression test for the bug descibed in var_self_assign_bug.mzn.
6% (This is the model from the original bug report.)
7
8% Global constraint in MiniZinc.
9%
10% From Global Constraint Catalogue
11% http://www.emn.fr/x-info/sdemasse/gccat/Cchange_parition.html
12% """
13% NCHANGE is the number of times that the following constraint holds:
14% X and Y do not belong to the same partition of the collection PARTITIONS.
15% X and Y correspond to consecutive variables of the collection VARIABLES.
16%
17% Example
18% (
19% 2,<
20% var-6,
21% var-6,
22% var-2,
23% var-1,
24% var-3,
25% var-3,
26% var-1,
27% var-6,
28% var-2,
29% var-2,
30% var-2
31% >,
32% <
33% p-<1, 3>,
34% p-<4>,
35% p-<2,6>
36% >
37% )
38%
39% In the example we have the following two changes:
40% * One change between values 2 and 1 (since 2 and 1 respectively belong
41% to the third and the first partition),
42% * One change between values 1 and 6 (since 1 and 6 respectively belong
43% to the first and the third partition).
44%
45% Consequently the change_partition constraint holds since its first
46% argument NCHANGE is assigned to 2.
47% """
48
49%
50% Model created by Hakan Kjellerstrand, hakank@bonetmail.com
51% See also my MiniZinc page: http://www.hakank.org/minizinc
52
53include "globals.mzn";
54
55int: n = 11;
56int: m = 3;
57set of int: S = {1,2,3,4,6};
58array[1..n] of var S: variables;
59array[1..3] of var set of S: partitions;
60var int: nchange;
61
62output [
63 "nchange = ", show(nchange), ";\n",
64 "partitions = ", show(partitions), ";\n",
65 "variables = ", show(variables), ";\n"
66];
67
68% a variant of the partition_set from globals.mzn where universe is
69% a var set of int (instead of par set of int)
70predicate partition_set2(array[int] of var set of int: S,
71 var set of int: universe) =
72 all_disjoint(S) /\ universe == array_union(i in index_set(S)) ( S[i] )
73;
74
75
76%
77% change_partition(NCHANGE, VARIABLES, PARTITIONS)
78%
79predicate change_partition(var int: nchange, array[int] of var int: variables, array[int] of var set of int: partitions) =
80 let {
81 int: lbv = min(index_set(variables)),
82 int: ubv = max(index_set(variables)),
83 int: lbp = min(index_set(partitions)),
84 int: ubp = max(index_set(partitions))
85 }
86 in
87 % number of patition changes
88 nchange = n - sum(v in lbv+1..ubv, p in lbp..ubp) (
89 bool2int(
90 variables[v-1] in partitions[p] /\ variables[v] in partitions[p]
91 )
92 ) - 1
93 /\
94 partition_set2(partitions, array_union(i in lbp..ubp) (partitions[i]))
95
96 /\ % for generating partitions: exclude empty partitions
97 forall(i in lbp..ubp) (
98 card(partitions[i]) > 0
99 )
100;
101
102predicate cp1d(array[int] of int: x, array[int] of var int: y) =
103 assert(index_set(x) = index_set(y),
104 "cp1d: x and y have different sizes",
105 forall(i in index_set(x)) (
106 x[i] = y[i]
107 )
108 )
109;
110
111predicate cp1d(array[int] of set of int: x, array[int] of var set of int: y) =
112 assert(index_set(x) = index_set(y),
113 "cp1d: x and y have different sizes",
114 forall(i in index_set(x)) (
115 x[i] = y[i]
116 )
117 )
118;
119
120
121solve satisfy;
122
123constraint
124 cp1d([6,6,2,1,3,3,1,6,2,2,2], variables)
125 /\
126 cp1d([
127 {1,3},
128 {4},
129 {2,6}], partitions)
130 /\
131 change_partition(nchange, variables, partitions)
132 /\
133 nchange = 2
134;