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