Debian Codegraph @

tests/spec/unit/regression/decision_tree_binary.mzn

raw
1 /***
2 !Test
3 solvers: [gecode, chuffed]
4 expected:
5 - !Result
6 solution: !Solution
7 node_used: [3, 4, 6, 9, 11, 13, 15, 8, 9, 10, 11, 12, 13, 14, 15]
8 x: [6, 2, 6, 2, 4, 6, 8, 1, 2, 3, 4, 5, 6, 7, 8]
9 ***/
10
11 % Regression test for a problem in mzn2fzn 1.2 where log/2
12 % was not recognised as a built-in operation by the flattening
13 % engine.
14
15 % THe model is from: http://www.hakank.org/minizinc/decision_tree_binary.mzn
16
17 % Decision tree in MiniZinc.
18 %
19 % Simple zero sum binary decision trees.
20 %
21 %
22 % Model created by Hakan Kjellerstrand, [email protected]
23
24 % The model only handles complete binary trees of sizes
25 % n = (a**2) - 1, for some a. The values are at the lowest level.
26 %
27 % Example with n = 7
28 %
29 % x1 A maximizes
30 % /\
31 % x2 x3 B minimizes
32 % / \ /\
33 % x4 x5 x6 x7 (A)
34 %
35 % The value nodes (the last level):
36 % x4 = 6
37 % x5 = 1
38 % x6 = 5
39 % x7 = 3
40 %
41 % First B minimizes the last level (x4..x7):
42 % x2 = argmin(x5, x4) -> x2 = x5
43 % x3 = argmin(x6, x7) -> x3 = x7
44 %
45 % A then maximizes from B's choices as the last step:
46 % x1 = argmax( x3, x2) -> x1 = x3
47 %
48 %
49 % The solution is a decision tree represented here as as:
50 %
51 %
52 % x (the values):
53 % 3
54 % 1 3
55 % 6 1 5 3
56 %
57 % node_used:
58 % 3
59 % 5 7
60 % 4 5 6 7
61
62
63 %
64 % minizinc and fz can handle n as large as 4095 (2**12-1)
65 % without breaking much sweat.
66 % For n = 8191 (2**13-1), it core dumps however.
67 %
68
69
70 int: n; % must be a (a**2) - 1, for some a, e.g. 7, 15, 31, 63 etc
71 int: levels = n div 2; % the number of levels
72
73 array[1..n] of var int: x; % the decision variables, the value tree
74 array[1..n] of var 1..n: node_used; % the nodes indices
75
76
77 %
78 % tree_levels contains the levels in the tree, e.g.
79 % [1, 2,2, 3,3,3,3, 4,4,4,4,4,4,4,4, ....]
80 % for odd levels: A is trying to maximize his/her gain,
81 % for even levels B is trying to minimize A's gains
82 %
83 array[1..n] of 0..n: tree_levels = [1+floor(log(2.0,int2float(i))) | i in 1..n ];
84
85 % solve :: int_search(x, "first_fail", "indomain", "complete") satisfy;
86 solve satisfy;
87
88 %
89 % argmax: maximize A's values
90 %
91 predicate argmax(array[int] of var int: x, int: i1, int: i2, array[int] of var int: node_used, int: node_used_ix) =
92 (x[i1] >= x[i2] -> node_used[node_used_ix] = i1)
93 /\
94 (x[i1] < x[i2] -> node_used[node_used_ix] = i2)
95 ;
96
97 % argmin: minimize A's values
98 predicate argmin(array[int] of var int: x, int: i1, int: i2, array[int] of var int: node_used, int: node_used_ix) =
99 (-x[i1] >= -x[i2] -> node_used[node_used_ix] = i1)
100 /\
101 (-x[i1] < -x[i2] -> node_used[node_used_ix] = i2)
102 ;
103
104 predicate cp1d(array[int] of var int: x, array[int] of var int: y) =
105 assert(index_set(x) = index_set(y),
106 "cp1d: x and y have different sizes",
107 forall(i in index_set(x)) ( x[i] = y[i] ) )
108 ;
109
110
111 constraint
112
113 % the first 1..n div 2 in x is to be decided by the model,
114 % the rest is the node values.
115
116 cp1d(x, [_, _,_, _,_, _,_, 1,2, 3,4, 5,6, 7,8]) % n = 15
117
118 /\ % the last n div 2 positions (the node "row") in node_used is static
119 forall(i in levels+1..n) (
120 node_used[i] = i
121 % more general: makes the node value 1.. .
122 % Comment it if another tree should be used.
123 % /\ x[i] = -(n - i - levels) + 1
124 )
125 /\
126 % the first n div 2 positions and values are dynamic,
127 % the rest are static.
128 forall(i in 1..levels) (
129 x[i] = x[node_used[i]]
130 )
131 /\ % Should we maximize or minimize?
132 % It depends on the level.
133 forall(i in 1..levels) (
134 if tree_levels[i] mod 2 = 1 then
135 argmax(x, 2*i, 2*i+1, node_used, i)
136 else
137 argmin(x, 2*i, 2*i+1, node_used, i)
138 endif
139 )
140
141 ;
142
143 % A "nice tree" (OK, it's not so nice. :-)
144 output
145 ["x (the values):\n" , show(x[1])]
146 ++
147 [
148 if tree_levels[i] > tree_levels[i-1] then "\n" else " " endif ++
149 show(x[i])
150 | i in 2..n
151 ] ++
152 ["\n\nnode_used:\n", show(node_used[1])]
153 ++
154 [
155 if tree_levels[i] > tree_levels[i-1] then "\n" else " " endif ++
156 show(node_used[i])
157 | i in 2..n
158 ] ++ ["\n"];
159
160 n = 15;