Problem
A Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is the length of the ruler. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values. A Golomb ruler of a given order with minimal length is called a optimal Golomb ruler.
There is no requirement that a Golomb ruler can measure all distances up to its length, but if it does, it is called a perfect Golomb ruler. It has been proven that no perfect Golomb ruler exists for five or more marks. Creating Golomb rulers is easy, but finding optimal Golomb rulers for a specified order is computationally very challenging. Figure 1 displays a Golomb ruler of order 4 and length 6. This ruler is both optimal and perfect. It can measure all distances up to the ruler’s length, and there exists no shorter ruler of order 4.
Figure 2 displays two optimal Golomb rulers of order 5, none of them being perfect, the left ruler misses length 6 and the other misses length 10.
![]() |
![]() |
Built a mathematical model to construct a optimal Golomb ruler up to order 10. [Reference: http://en.wikipedia.org/wiki/Golomb_ruler]
Modeling Steps
The unique data needed is a number n ≥ 1 indicating the order of the ruler. A set of “markers” i = {1…n} define the set of marked positions of the ruler.
-
We introduce an integer variable marki for each marker specifying the positive position of the marker.
-
Note that the marker number zero is calibrated at position zero (mark1 = 0).
-
Without restriction, the marker positions can be ordered in increasing way.
-
The distance between the positions of any two marker i and j must be different from each other, that is the amount marki –markj must be different for every pair (i,j) of markers. This can be formulated using the Alldiff() function in LPL.
-
We want to have to shortest ruler, that is, markn must be minimized.
model golomb "Golomb Ruler";
parameter n := 9 "order";
set i,j,k := 1..n;
integer variable mark{i} [0..70];
constraint A{i|i<n}: mark[i] < mark[i+1];
B: Alldiff({i,j|i>j}(mark[i]-mark[j]));
C: mark[1]=0 and mark[2]=1;
minimize obj: mark[n];
integer parameter D{i,j|i>j}:=mark[i]-mark[j];
Draw.Scale(20,20);
Draw.Text('A Golomb Ruler of order '&n,0,-1);
Draw.Line(0,0,mark[n],0,0,2);
{i} Draw.Line(mark,1,mark,-.5,0,2);
{i} Draw.Text(mark&'',mark+.1,1);
parameter y:=2; m:=0;
{i,j|D} (m:=m+1, {i1 in i,j1 in j|D}
(if(D[i1,j1]=m,
(Draw.Line(m&'',mark[i1],y,mark[j1],y), y:=y+.8))
)
);
end
Solution
LPL translates this model by default into linear integer problem. Using this model method one can solve Golomb ruler up to order n = 10. To find optimal rulers of order larger than 20 is very challenging. Figure 3 is the unique optimal Golomb ruler of order 10, found with the model. Its length is 55.
Questions
-
How many optimal Golomb rulers of order n = 8 are there?
-
The upper bound of variable mark was set arbitrarily to 70. Can you find a more general upper bound?
Answers
-
There is exactly one. To check solve the model several times in which you forbid optimal mark positions.
-
To find good upper and lower bounds will help in finding solutions. However, bounds are not trivial to find. It is certainly not the right place here to explain them. If you are interested, you will find plenty of papers in the Internet for this problem.
References
[1] MatMod. Homepage for Learning Mathematical Modeling : https://matmod.ch.
[2] Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.