Debian Codegraph @

tests/spec/examples/golomb.mzn

raw
1 /***
2 !Test
3 expected:
4 - !Result
5 solution: !Solution
6 mark:
7 - 0
8 - 1
9 - 4
10 - 6
11 objective: 6
12 ***/
13
14 %------------------------------------------------------------------------%
15 % Golomb rulers
16 % prob006 in csplib
17 %------------------------------------------------------------------------%
18 % From csplib:
19 % A Golomb ruler may be defined as a set of m integers 0 = a_1 < a_2 <
20 % ... < a_m such that the m(m-1)/2 differences a_j - a_i, 1 <= i < j
21 % <= m are distinct. Such a ruler is said to contain m marks and is of
22 % length a_m. The objective is to find optimal (minimum length) or
23 % near optimal rulers.
24 %
25 % This is the "ternary constraints and an alldifferent" model
26 %------------------------------------------------------------------------%
27
28 include "globals.mzn";
29
30 int: m = 4;
31 int: n = m*m;
32
33 array[1..m] of var 0..n: mark;
34
35 array[int] of var 0..n: differences =
36 [ mark[j] - mark[i] | i in 1..m, j in i+1..m];
37
38 constraint mark[1] = 0;
39
40 constraint forall ( i in 1..m-1 ) ( mark[i] < mark[i+1] );
41
42 constraint alldifferent(differences);
43
44 % Symmetry breaking
45 constraint differences[1] < differences[(m*(m-1)) div 2];
46
47 solve :: int_search(mark, input_order, indomain, complete)
48 minimize mark[m];
49
50 output ["golomb ", show(mark), "\n"];