Golomb Rulers

A Golomb ruler (wiki) is a set of m marks (0 = x1 < x2 <...< xm) such as m(m - 1)/2 distances {xj - xi :1 <= i < j <= m} are distinct. A ruler is of order m if it contains m marks, and it is of length xm. The goal is to find
a ruler of order m with minimal length (minimize xm).

A declarative model of this problem is given in Mx(k) while Px(k) presents a refined and improved model.

  • The four intermediate versions of the Golomb rulers we kept from our initial program development
    contain realistic faults, not invented for the experiment.
  • CPUT1
  • CPUT2
  • CPUT3
  • CPUT4
  • CPUT5
  • CPUT6
  • CPUT7

The results we got for an instance parameter m = 8 are given in the folowing Tab.1. For the conf_bounds relation, the interval [50; 100] was used to feed the relation, knowing that the global minimum is xm = 34 when m = 8. Each time a non-con rmity was found, it was reported with the CPU time required to nd it. Firstly, the four faulty CPUT were reported as being non-conforms and the time required for nding these non-conformities is acceptable (less than a few minutes in the worst case).

Tab1.Non-conformities found by CPTEST in various CPUTs of the Golomb rulers (timeout=5400s)
m=8 conf_one conf_all conf_bounds conf_best

non-conf CPUT1 T(s)

[0 7 8 18 24 26 35 44]
[17 18 20 25 34 45 49 55]
[0 2 3 6 11 58 72 86]
[0 1 3 6 10 15 24 33]
4.29s
21.45s
5.64s
7.31s
non-conf CPUT2 T(s)
[0 4 5 26 28 31 47 63]
[17 18 20 25 34 45 49 55]
[0 18 39 43 45 46 55 64]
[0 3 4 9 13 15 24 33]
5.62s
40.78s
4.64s
174.43s
non-conf CPUT3 T(s)
[0 4 5 26 28 31 47 63]
[0 4 5 26 28 31 47 63]
[0 18 39 43 45 46 55 64]
[0 3 4 9 13 15 24 33]
9.53s
45.78s
7.15s
389.04s
non-conf CPUT4 T(s)
[0 12 18 20 29 33 34 39]
[1 2 10 22 33 55 57 60]
[0 21 30 32 42 45 46 50]
[0 6 13 21 22 25 27 32]
12.60s
0.15s
9.01s
12.53s

non-conf__ P T(s)

conf
[0 7 9 12 37 54 58 64]
conf
---
3 448.46s
0.18s
3 658.13s
timeout

 

 

Our experimental evaluation also had the goal to check that computing non-conformities with CPTEST was less hard than computing solutions. Fig. 6 shows: A) the CPU time required to find a global optimum for instances of the Golomb rulers (red line) and B) the CPU time required to find non- conformities with CPTEST with the conf_bounds conformity relation (blue line). The search heurisitic used in both cases is the default heuristic of OPL, i.e. depth-first search with restarts, and branch-and-bound for the global optimization problem. CPTEST can find non-conformities when m < 22 in a reasonable amount of time because the hard global optimization problem has been relaxed in a simpler satisfaction problem, in order to deal with larger instances.
This is the essence of the conf_bounds conformity relation.

tab2. non-conformity point for Golomb rulers instances (2 < m < 24).

m T(s) M(mo) Rulers (non-conformities)
3 0.00______ 0.80 [0 4 8]
4 0.00 0.83 [0 1 6 11]
5 0.00 0.90 [0 1 3 9 15]
6 0.00 1.10 [0 1 14 18 26 34]
7 0.04 1.30 [0 1 12 19 27 37 47]
8 0.18 1.70 [1 10 13 23 35 36 46 56]
9 0.11

1.90

 [9 11 12 16 24 31 57 67 77]
10 0.04 2.30 [4 11 15 16 18 21 32 37 66 95]
11 0.09 2.70 [1 6 19 23 24 27 29 41 89 103 117]
12 0.17 3.50 [14 15 18 33 52 60 67 98 100 113 128 143]
13 0.26 4.10 [0 4 9 19 53 59 70 72 73 76 83 99 115]
14 1.55 5.40 [4 5 24 80 99 117 134 140 142 145 149 154 169 184]
15 0.76 6.30 [6 10 21 27 51 85 90 91 130 133 147 149 156 190 224]
16 2.30 7.70 [0 5 8 70 101 120 139 143 144 146 156 168 179 187 205 223]
17 40.12 12.60 [0 3 32 58 76 77 82 86 101 108 110 116 126 135 146 165 184]
18 81.17 15.20 [29 58 68 73 87 100 106 118 125 145 197 205 209 212 213 215 260 305]
19 5.43 12.40 [7 12 19 23 41 84 106 121 123 242 253 256 257 277 285 299 305 331 357]
20 448.40 22.70 [7 19 28 53 75 81 82 89 114 125 162 214 233 235 288 308 316 319 342 365]
21 646.15 25.00 [3 12 30 52 58 80 92 103 106 113 132 163 167 181 186 187 197 226 324 381 438]
22 1 047.59 31.30 [37 59 74 77 91 163 210 211 291 298 302 344 349 351 376 384 390 399 422 434 459 484]
23

6 467.34

 38.70 [18 52 82 103 105 137 161 212 217 227 233 241 245 248 260 267 280 294 310 376 417 449 481] ___________________________________________________________________________________

 

 

tab3. Fault detection and localization of Golomb rulers problem.

TEST LOCALIZATION
G.rulers #_constr. fault_injected non.conf._detected fault localization time
CPUT1 2 p1_ct2 [0 1 3 6] (rev(P1), (m_ct2)) 0.32s
CPUT2 4 p2_ct3 [0 1 6 11] (rev(P2), (m_ct2)) 0.82s
CPUT3 5 p3_ct3 [0 5 6 11] (rev(P3), (m_ct2)) 1.15s
CPUT4 9 p4_ct5 sol(CPUT4)=emptyset (rev(p4_ct5),emptyset) 1.87s
CPUT5 9

p5_ct1

 sol(CPUT5)=emptyset (rev(p5_ct1),emptyset) 1.62s
CPUT6 9 p6_ct2 [0 1 6 11] (rev(P6), (m_ct2)) 2.14s
CPUT7 9 p7_ct9 sol(CPUT7)=emptyset (rev(p7_ct6,p7_ct9),emptyset) 1.92s

Correction:

All our experiments were performed on Intel Core2 Duo CPU 2.40Ghz machine with 2.00 GB of RAM.