The Golomb Ruler Problem
Description
The problem can simply be stated as: given a positive integer n, find a set of n positive increasing integers (marks) such that all the differences between marks are distinct and such that the last mark (the length of the ruler when the first mark is 0) is minimal. More on the Golomb ruler problem...
Business and Industrial Applications
This problem is said to have many practical applications including sensor placements for x-ray crystallography and radio astronomy.
Modelling & Solving
We use a very classical modelling - Java file (5kb) [view] - based on marks and distances between marks, and a very basic optimizer: Java file (1kb) [view].
As stated in this research report,
additional pruning of the search space can be obtained by taking into account the fact
that distances between marks are sums of integers that have to be different.
Instead of writing a new constraint,
we define a new solver by overriding the filter method of a BacktrackSolver:
Java file (4kb) [view].
Results
The following results include the computation of an optimal solution and the proof of its optimality.
| Size | Time | Backtracks |
|---|---|---|
| 10 | 2.2 s | 8280 b |
| 11 | 60 s | 171 kb |
| 12 | 590 s | 1305 kb |
| 13 | 3.5 h | 19 Mb |
| 14 | 57.8 h | 256 Mb |