The Golomb Ruler problem consists in finding $n$ integers such that all possible differences are distinct and such that the largest difference is minimum. We review three lower bounds based on linear programming that have been proposed in the literature for this problem, and propose a new one. We then show that these 4 lower bounds are equal. Finally we discuss some computational experience aiming at identifying the easiest lower bound to compute in practice.

A Golomb ruler with M marks can be defined as a set of integers so that all pairwise differences are distinct. An order 2 Golomb ruler is a Golomb ruler such that all differences of pairwise differences are distinct as much as possible. Contruction of optimum order 2 Golomb ruler, i.e., of rulers of minimum length, is a highly combinatorial problem which has applications, e.g., in the design of convolutional self doubly orthogonal codes. We propose here a first exact algorithm, different from a pure exhaustive search, for building optimum order 2 Golomb rulers and provide optimal rulers for up to 9 marks and new rulers which improve on the previous ones for up to 20 marks.

We will present and discuss different integer linear programming formulations for the design of DTS - Difference Traingle Set. A (I,J)-DTS is a set of I Golomb rulers with J+1 marks each, which have no common difference.