Golomb

The Golomb problem is available at the CSPLib benchmark library (prob006 at http://csplib.cs.strath.ac.uk/). It is also described by Dewdney in [#!Dewdney85!#]. The library describes the problem as:

``A Golomb ruler may be defined as a set of mintegers 0 = a₁ < a₂ < ... < a_m such that the m(m-1)/2differences a_j - a_i, 1 <= i < j <= m are distinct. Such a ruler is said to contain m marks and is of length a_m. The objective is to find optimal (minimum length) or near optimal rulers''.

To distinguish between the m used in the above description and the m used in our notation for the number of constraints in a CSP, we will use M to refer to the number of marks in a Golomb ruler instance.

Example 1    As an example, a Golomb ruler with M = 4 can be constructed by placing mark 1 at distance 0 on the ruler, mark 2 at distance 1, mark 3 at distance 4, and mark 4 at distance 6. This corresponds to a ruler of length 6 which is the optimal Golomb ruler for M = 4.

The basic approach to solving an instance of the Golomb problem, like other optimization problems, is an iterative approach. For an instance with M marks the typical initial length to try is the minimum length found for an instance with M-1 marks. So given an M, a ruler length L is selected to try first. Then a CSP instance is generated (more details on how this is done are given below). If a solution can be found to this instance, then L is the optimal length for a Golomb ruler with M marks. If a solution can not be found to this instance, then the process is repeated with a ruler of length L + 1. This iterative process is continued, with progressively longer rulers, until the optimal length ruler is found.

The Golomb CSP generator takes as input the number of marks M and a ruler length L. The resulting CSP has M variables, x₁,...,x_M, (i.e. n = M) each with a finite integer domain of size equal to the length L. This domain corresponds to each of the places the mark can be placed, so an assignment of a value a to a variable x_i corresponds to the i^th mark being placed on the ruler at position a.

The model we used involves three types of constraints:

• binary less than constraints
  $\forall x_i, x_j \in X$ if i < j then x_i < x_j

• ternary not equal constraints
  $\forall x_i,x_j,x_k \in X$ if (i < j < k) then ( $\vert x_k - x_i\vert \neq \vert x_j - x_i\vert$ and $\vert x_k - x_j\vert \neq \vert x_j - x_i\vert$ and $\vert x_k - x_j\vert \neq \vert x_k - x_i\vert$ )

• quaternary not equal constraints
  $\forall x_i,x_j,x_k,x_l \in X$ if (i < j < k < l) then ( $\vert x_l - x_i\vert \neq \vert x_k - x_j\vert$ and $\vert x_l - x_j\vert \neq \vert x_k - x_i\vert$ and $\vert x_l - x_k\vert \neq \vert x_j - x_i\vert$ )

The range of problems that we found to be solvable within a reasonable length of time, given our formulation, are problems with up to 13 marks. If M is 11 and L is 72 (which is the optimal length for a Golomb ruler with 11 marks), the CSP instance generated has:

• 11 variables, each with domains of size of 73,
• 55 binary constraints,
• 165 ternary constraints, and
• 330 quaternary constraints.

[EXAMPLE][EXAMPLE][][][][]  As an example, a Golomb ruler with M = 4 can be constructed by placing mark 1 at distance 0 on the ruler, mark 2 at distance 1, mark 3 at distance 4, and mark 4 at distance 6. This corresponds to a ruler of length 6 which is the optimal Golomb ruler for M = 4.

The basic approach to solving an instance of the Golomb problem, like other optimization problems, is an iterative approach. For an instance with M marks the typical initial length to try is the minimum length found for an instance with M-1 marks. So given an M, a ruler length L is selected to try first. Then a CSP instance is generated (more details on how this is done are given below). If a solution can be found to this instance, then L is the optimal length for a Golomb ruler with M marks. If a solution can not be found to this instance, then the process is repeated with a ruler of length L + 1. This iterative process is continued, with progressively longer rulers, until the optimal length ruler is found.

The Golomb CSP generator takes as input the number of marks M and a ruler length L. The resulting CSP has M variables, x₁,...,x_M, (i.e. n = M) each with a finite integer domain of size equal to the length L. This domain corresponds to each of the places the mark can be placed, so an assignment of a value a to a variable x_i corresponds to the i^th mark being placed on the ruler at position a.

The model we used involves three types of constraints:

• binary less than constraints
  $\forall x_i, x_j \in X$ if i < j then x_i < x_j

• ternary not equal constraints
  $\forall x_i,x_j,x_k \in X$ if (i < j < k) then ( $\vert x_k - x_i\vert \neq \vert x_j - x_i\vert$ and $\vert x_k - x_j\vert \neq \vert x_j - x_i\vert$ and $\vert x_k - x_j\vert \neq \vert x_k - x_i\vert$ )

• quaternary not equal constraints
  $\forall x_i,x_j,x_k,x_l \in X$ if (i < j < k < l) then ( $\vert x_l - x_i\vert \neq \vert x_k - x_j\vert$ and $\vert x_l - x_j\vert \neq \vert x_k - x_i\vert$ and $\vert x_l - x_k\vert \neq \vert x_j - x_i\vert$ )

The range of problems that we found to be solvable within a reasonable length of time, given our formulation, are problems with up to 13 marks. If M is 11 and L is 72 (which is the optimal length for a Golomb ruler with 11 marks), the CSP instance generated has:

• 11 variables, each with domains of size of 73,
• 55 binary constraints,
• 165 ternary constraints, and
• 330 quaternary constraints.