Math
Variables

An integer variable $\text{tick}_i$ per mark i indicates its position.
$$\forall i \in [1,m], \text{tick}_i = [\![0,9999]\!]$$

An integer variable $\text{diff}_{i,j}$ per couple of marks $i,j$ ($i < j$) indicates distance between the two marks.
$$\forall i,j \in [1,m], i < j, \text{diff}_{i,j} = [\![0,9999]\!]$$
Constraints

Maks are ordered :
$$\forall i \in [2,m], \text{tick}_{i1} < \text{tick}_i$$

Distance between two distinct marks :
$$\forall i,j \in [1,m], i < j, \text{diff}_{i,j} = \text{tick}_j  \text{tick}_i$$

No two pairs of marks are the same distance apart
$$\forall i,j \in [1,m], i \ne j, \text{tick}_{i} \ne \text{tick}_{j}$$
We saw this type of constraint before, it is an alldifferent constraint.

The first mark can be set to
0
: $$\text{tick}_0 = 0$$
Those variables and constraints are sufficient to define the problem. However, this initial model can be improved by adding redundant constraints and by breaking symmetries.
Redundant constraints
These types of constraints are not required to find solutions, they are implied by the other constraints of the model. Thus, their role is to bring more filtering and to possibly detect infeasible combinations earlier in the search.
The following reasoning is based on the fact that:
$$\forall i,j \in [1,m], i < j, \text{diff}_{i,j} = \text{diff}_{i,i+1} \ldots \text{diff}_{j1,j}$$
Because all distances must be different, we can estimate the minimal sum of distances as a sum of ji different positive numbers.
$$\forall i,j \in [1,m], i < j, \text{diff}_{i,j} \geq \frac{(ji) * (ji+1)}{2}$$
Moreover, remember that
$$\text{diff}_{1,m} = \text{tick}_{m}  \text{tick}_1$$
and
$$\text{diff}_{1,m} = \text{diff}_{1,2} \ldots \text{diff}_{i,j} \ldots\text{diff}_{m1,m}$$
Thus, since $\text{tick}_1$ is equal to 0, we deduce that:
$$\text{tick}_{m} = \text{diff}_{1,2} \ldots \text{diff}_{i,j} \ldots\text{diff}_{m1,m}$$
There are m1j+i different numbers so the upper for $\text{diff}_{i,j}$ can be defined as:
$$\forall i,j \in [1,m], i < j, \text{diff}_{i,j} \leq \text{tick}_m  \frac{(m  1  j + i) * (m  j + i)}{2}$$
To go into details, please read Barták, “Effective modeling with constraints”.
Symmetrybreaking constraints
These types of constraints aims at breaking symmetries and reducing the search space size. Indeed, they avoid finding new solutions that are symmetric to previously found ones.
In a Golomb ruler, an easy way to break symmetries is to define an order between the first and the last distances:
$$\text{diff}_{0,1} < \text{diff}_{m1,m}$$
Objective
The objective is to find a solution that minimizes the position of the last mark $\text{tick}_m$.
Feedback
Was this page helpful?
Glad to hear it! Please tell us how we can improve.
Sorry to hear that. Please tell us how we can improve.