5.144. golomb

DESCRIPTIONLINKSGRAPH
Origin

Inspired by [Golomb72].

Constraint

πšπš˜πš•πš˜πš–πš‹(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Argument
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰₯0
πšœπšπš›πš’πšŒπšπš•πš’_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)
Purpose

Given a strictly increasing sequence X1,X2,...,X n , enforce all differences X i -X j between two variables X i and X j (i>j) to be distinct.

Example
(0,1,4,6)

FigureΒ 5.144.1 gives a graphical interpretation of the solution given in the example in term of a graph: each vertex corresponds to a value of 〈0,1,4,6βŒͺ, while each arc depicts a difference between two values. The πšπš˜πš•πš˜πš–πš‹ constraint holds since one can note that these differences 1, 4, 6, 3, 5, 2 are all -distinct.

Figure 5.144.1. Graphical representation of the solution 0,1,4,6
ctrs/golomb1
Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
Symmetry

One and the same constant can be added to the πšŸπšŠπš› attribute of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Usage

This constraint refers to the Golomb ruler problem. We quote the definition fromΒ [Shearer96]: β€œA Golomb ruler is a set of integers (marks) a 1 <β‹―<a k such that all the differences a i -a j (i>j) are distinct”.

Remark

Different constraints models for the Golomb ruler problem were presented inΒ [SmithStergiouWalsh99].

Algorithm

At a first glance, one could think that, because it looks so similar to the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint, we could have a perfect polynomial filtering algorithm. However this is not true since one retrieves the same variable in different vertices of the graph. This leads to the fact that one has incompatible arcs in the bipartite graph (the two classes of vertices correspond to the pair of variables and to the fact that the difference between two pairs of variables takes a specific value). However one can still reuse a similar filtering algorithm as for the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint, but this will not lead to perfect pruning.

See also

common keyword: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (all different).

implies: πšœπšπš›πš’πšŒπšπš•πš’_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš.

Keywords

characteristic of a constraint: disequality, difference, all different, derived collection.

puzzles: Golomb ruler.

Derived Collection
πšŒπš˜πš•π™Ώπ™°π™Έπšπš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚑-πšπšŸπšŠπš›,𝚒-πšπšŸπšŠπš›),πš’πšπšŽπš–(𝚑-πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›,𝚒-πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)]
Arc input(s)

π™Ώπ™°π™Έπšπš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš™πšŠπš’πš›πšœ1,πš™πšŠπš’πš›πšœ2)

Arc arity
Arc constraint(s)
πš™πšŠπš’πš›πšœ1.𝚒-πš™πšŠπš’πš›πšœ1.𝚑=πš™πšŠπš’πš›πšœ2.𝚒-πš™πšŠπš’πš›πšœ2.𝚑
Graph property(ies)
πŒπ€π—_𝐍𝐒𝐂𝐂≀1

Graph model

When applied on the collection of items βŒ©πš…π™°πš1,πš…π™°πš2,πš…π™°πš3,πš…π™°πš4βŒͺ, the generator of derived collection generates the following collection of items: βŒ©πš…π™°πš2 πš…π™°πš1,πš…π™°πš3 πš…π™°πš1,πš…π™°πš3 πš…π™°πš2,πš…π™°πš4 πš…π™°πš1,πš…π™°πš4 πš…π™°πš2,πš…π™°πš4 πš…π™°πš3βŒͺ. Note that we use a binary arc constraint between two vertices and that this binary constraint involves four variables.

PartsΒ (A) andΒ (B) of FigureΒ 5.144.2 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_𝐍𝐒𝐂𝐂 graph property we show one of the largest strongly connected component of the final graph. The constraint holds since all the strongly connected components have at most one vertex: the differences 1, 2, 3, 4, 5, 6 that one can construct from the values 0, 1, 4, 6 assigned to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection are all -distinct.

Figure 5.144.2. Initial and final graph of the πšπš˜πš•πš˜πš–πš‹ constraint
ctrs/golombA
(a)
ctrs/golombB
(b)