| 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"]; |