dekker.one
The models, scripts, and results of the benchmarks performed for a Half Reification Journal paper
1% Prize collecting problem.
2%
3int: n; % size
4array[1..n, 0..n] of int: p;
5
6array[1..n] of var 0..n: next;% next posn in tour :
7 % 1 for last edge, 0 for unused
8
9array[1..n] of var 0..n: pos; % posn of node i in path, 0 = notin
10
11constraint pos[1] = 1;
12
13constraint forall(i in 1..n) (
14 let {
15 var bool: b;
16 constraint array_var_int_element_imp(next[i], pos, pos[i]+1, b);
17 } in (pos[i] > 0 <-> next[i] > 0) /\ (next[i] > 1 -> b)
18);
19
20constraint all_different_except_0(next);
21
22predicate all_different_except_0(array[int] of var int: x) =
23 forall(i in index_set(x)) (
24 x[i] = 0 \/ forall(j in index_set(x) where j > i)(x[i] != x[j])
25 );
26solve
27 :: seq_search([
28 int_search(next, largest, indomain_max, complete),
29 int_search(pos, largest, indomain_max, complete)])
30 maximize sum(i in 1..n)(p[i, next[i]]);
31
32output
33 [ "next =" ++ show(next) ++ "\n",
34 "pos =" ++ show(pos) ++ "\n",
35 "obj =" ++ show(sum(i in 1..n)(p[i, next[i]])) ++ "\n"
36 ];