3.3. An implementation of the first model

  1. C++ code:
    1. golomb1.cc

In this section, we code the first model developed in The Golomb ruler problem and a first model.

We take the order (the number of marks) from the command line:

DEFINE_int64(n, 5, "Number of marks.");

3.3.1. An upper bound

Several upper bounds exist on Golomb rulers. For instance, we could take n^3 - 2n^2+ 2n -1. Indeed, it can be shown that the sequence

\Phi(a) = na^2 + a \qquad 0 \leqslant a < n.

forms a Golomb ruler. As its largest member is n^3 - 2n^2+ 2n -1 (when a = n - 1), we have an upper bound on the length of a Golomb ruler of order n:

G(n) \leqslant n^3 - 2n^2+ 2n -1.

Most bounds are really bad and this one isn’t an exception. The great mathematician Paul Erdös conjectured that

G(n) < n^2.

This conjecture hasn’t been proved yet but computational evidence has shown that the conjecture holds for n < 65000 (see [Dimitromanolakis2002]).

This is perfect for our needs:

CHECK_LT(n, 65000);
const int64 max = n * n - 1;

3.3.2. The first model

We can now define our variables but instead of creating single instances of IntVars like this:

const int64 num_vars = (n*(n - 1))/2;
std::vector<IntVar*> Y(num_vars);
for (int i = 0; i < num_vars; ++i) {
  Y[i] = s.MakeIntVar(1, max, StringPrintf("Y%03d", i));

we use the MakeIntVarArray() method:

const int64 num_vars = (n*(n - 1))/2;
std::vector<IntVar*> Y;
s.MakeIntVarArray(num_vars, 1, max, "Y_", &Y);

Note that these two methods don’t provide the same result! MakeIntVarArray() appends num_vars IntVar* to the std::vector with names Y_i where i goes from 0 to num_vars - 1. It is a convenient shortcut to quickly create an std::vector<IntVar*> (or to append some IntVar*s to an existing std::vector<IntVar*>).

StringPrintf() (shown in the first example) is a helper function declared in the header base/stringprintf.h that mimics the C function printf().

We use the AllDifferent constraint to ensure that the differences (in Y) are distinct:


and the following constraints to ensure the inner structure of a Golomb ruler as we have seen in the previous section[1]:

int index = n - 2;
IntVar* v2 = NULL;
for (int i = 2; i <= n - 1; ++i) {
   for (int j = 0; j < n-i; ++j) {
     v2 = Y[j];
     for (int p = j + 1; p <=  j + i - 1 ; ++p) {
       v2 = s.MakeSum(Y[p], v2)->Var();
     s.AddConstraint(s.MakeEquality(Y[index], v2));
CHECK_EQ(index, num_vars - 1);

How do we tell the solver to optimize? Use an OptimizeVar to declare the objective function:

OptimizeVar* const length = s.MakeMinimize(Y[num_vars - 1], 1);

and give the variable length to the Solve() method:

s.Solve(db, collector, length);

In the section How does the solver optimize?, we will explain how the solver optimizes and the meaning of the mysterious parameter 1 in

... = s.MakeMinimize(Y[num_vars - 1], 1);


[1]Remember the remark at the beginning of this chapter about the tricky sums!


[Dimitromanolakis2002]Apostolos Dimitromanolakis. Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers. Ph.D. Thesis, Department of Electronic and Computer Engineering, Technical University of Crete.