A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1%------------------------------------------------------------------------------
2% Parameters
3
4int: num_strings;
5int: max_length_strings;
6int: max_char;
7
8int: max_length_median;
9
10array [1..num_strings, 1..max_length_strings] of int: strings;
11array [1..num_strings] of int: str_length;
12
13
14%------------------------------------------------------------------------------
15% Variables
16
17array [1..max_length_strings] of var 0..max_char: median;
18array [1..num_strings] of var 0..2*max_length_strings: distances;
19
20int: obj_ub = num_strings * 2 * max_length_strings;
21var 0..obj_ub: objective;
22
23%------------------------------------------------------------------------------
24% Predicates
25
26predicate lcs_global(array[int] of var int: S1, array[int] of var int: S2, var int: ED) =
27
28 let { int: l1 = min(index_set(S1)) - 1;
29 int: l2 = min(index_set(S2)) - 1;
30 int: u1 = max(index_set(S1));
31 int: u2 = max(index_set(S2));
32 array[l1..u1,l2..u2] of var 0..u1+u2: T; } in
33 T[l1,l2] = 0 /\
34 T[u1,u2] = ED /\
35 forall(i in l1+1..u1, j in l2+1..u2)
36 (T[i,j] >= 0 /\ T[i,j] <= i+j) /\
37 forall(j in l2+1..u2)(T[l1,j] = j-l2) /\
38 forall(i in l1+1..u1)(T[i,l2] = i-l1) /\
39 forall(i in l1+1..u1, j in l2+1..u2)
40 (T[i,j] = if S1[i] = S2[j] then
41 T[i-1,j-1]
42 else
43 if S1[i] = 0 then
44 T[i-1,j]
45 else
46 if S2[j] = 0 then
47 T[i,j-1]
48 else
49 min([T[i-1,j]+1,T[i,j-1]+1])
50 endif
51 endif
52 endif
53 );
54
55%------------------------------------------------------------------------------
56% Constraints
57
58constraint forall(i in 1..num_strings)(
59 lcs_global([strings[i,j] | j in 1..max_length_strings], median, distances[i])
60);
61
62constraint forall(i in max_length_median+1..max_length_strings)(
63 median[i] = 0
64);
65
66constraint objective = sum(i in 1..num_strings)(distances[i]);
67
68%------------------------------------------------------------------------------
69% Solve item
70
71solve
72 :: int_search(median, input_order, indomain_min, complete)
73 minimize objective;
74
75%------------------------------------------------------------------------------
76% Output
77
78output [
79 "median = \(median);\n",
80 "objective = \(objective);\n"
81];