-
Notifications
You must be signed in to change notification settings - Fork 6
/
golomb_mybab.mzn
53 lines (42 loc) · 1.7 KB
/
golomb_mybab.mzn
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
% RUNS ON mzn20_fd
% RUNS ON mzn20_fd_linear
%------------------------------------------------------------------------%
% Golomb rulers
% prob006 in csplib
%------------------------------------------------------------------------%
% From csplib:
% A Golomb ruler may be defined as a set of m integers 0 = a_1 < a_2 <
% ... < a_m such that the m(m-1)/2 differences a_j - a_i, 1 <= i < j
% <= m are distinct. Such a ruler is said to contain m marks and is of
% length a_m. The objective is to find optimal (minimum length) or
% near optimal rulers.
%
% This is the "ternary constraints and an alldifferent" model
%------------------------------------------------------------------------%
include "globals.mzn";
%include "minisearch.mzn"; % include the search minisearch lite
int: m = 10;
int: n = m*m;
array[1..m] of var 0..n: mark;
var 0..n: obj;
array[int] of var 0..n: differences =
[ mark[j] - mark[i] | i in 1..m, j in i+1..m];
constraint mark[1] = 0;
constraint obj = mark[m];
constraint forall ( i in 1..m-1 ) ( mark[i] < mark[i+1] );
constraint alldifferent(differences);
% Symmetry breaking
constraint differences[1] < differences[(m*(m-1)) div 2];
%function ann: mybab(var int: obj) =
% repeat(
% if next() then
% print("Intermediate solution with objective \(sol(obj))\n") /\
% commit() /\ post(obj < sol(obj))
% else break endif
% );
% solve using minimizing branch & bound
solve :: int_search(mark, input_order, indomain, complete)
minimize obj;
% search mybab(obj) /\ print();
% search time_limit(3000, mybab(obj)) /\ if hasSol() then print() else print("No solution found\n") endif;
output ["golomb ", show(obj), "\n", show(mark), "\n"];