# Partial reformulation-linearization based optimization models for the Golomb ruler problem

Hacène Ouzia

► To cite this version:

Hacène Ouzia. Partial reformulation-linearization based optimization models for the Golomb ruler problem. RAIRO - Operations Research, 2024, 58 (4), pp.3171-3188. 10.1051/ro/2024121. hal-04681114

HAL Id: hal-04681114

https://hal.sorbonne-universite.fr/hal-04681114v1

Submitted on 29 Aug 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# PARTIAL REFORMULATION-LINEARIZATION BASED OPTIMIZATION MODELS FOR THE GOLOMB RULER PROBLEM

HACÈNE OUZIA*

**Abstract.** In this paper, we provide a straightforward proof of a conjecture proposed in [P. Duxbury, C. Lavor and L.L. de Salles-Neto, *RAIRO:RO 55* (2021) 2241-2246.] regarding the optimal solutions of a non-convex mathematical programming model of the Golomb ruler problem. Subsequently, we investigate the computational efficiency of four new binary mixed-integer linear programming models to compute optimal Golomb rulers. These models are derived from a well-known nonlinear integer model proposed in [B. Kocuk and W.-J. van Hoeve, *A Computational Comparison of Optimization Methods for the Golomb Ruler Problem*. (2019) 409-425.], utilizing the reformulation-linearization technique. Finally, we provide the correct outputs of the greedy heuristic proposed in [P. Duxbury, C. Lavor and L.L. de Salles-Neto, *RAIRO:RO 55* (2021) 2241-2246.] and correct false conclusions stated or implied therein.

**Mathematics Subject Classification.** 90C10, 90C11, 90C20, 90C26, 90C27, 90C30.

Received February 26, 2024. Accepted May 31, 2024.

# 1. INTRODUCTION

## 1.1. The problem

Given a positive integer $n$, a *ruler* with $n$ marks is a finite increasing sequence $\langle x_0, \dots, x_{n-1} \rangle$ of $n$ integers (the *marks*). The *length* of the ruler $\langle x_0, \dots, x_{n-1} \rangle$ is the difference $x_{n-1} - x_0$. A *Golomb ruler* with $n$ marks is a ruler $\langle x_0, \dots, x_{n-1} \rangle$ such that the inter-distances between its marks are all different. Since the inter-distances are invariant by translation, one can assume that $x_0 = 0$, which implies that $x_{n-1}$ will be the length of the ruler. In the following, we will assume that 0 is the first mark of any Golomb ruler.

The *Golomb Ruler (Optimization) Problem (GRP)* consists of finding, among all Golomb rulers $\langle 0, x_1, \dots, x_{n-1} \rangle$, one that has a minimum length $x_{n-1}$. A Golomb ruler with minimum length will be called an *optimal Golomb ruler*. For example, in the case of $n=4$, the two rulers $\langle 0, 1, 4, 6 \rangle$ and $\langle 0, 1, 3, 7 \rangle$ are Golomb rulers with lengths 6 and 7, respectively. One can easily check that the former is an optimal Golomb ruler among Golomb rulers with 4 marks.

The length of an optimal Golomb ruler with $n$ marks is usually denoted by $G(n)$. To the best of our knowledge, no mathematical expression for $G(n)$ is known, and its values are tabulated only for $n \le 28$. For any given $n$,

<footnote>*Keywords.* Golomb ruler problem, reformulation-linearization techniques, mixed integer linear programming, integer nonlinear programming, quadratic programming.</footnote>

<footnote>*Corresponding author: hacene.ouzia@sorbonne-universite.fr</footnote>
the value of $G(n)$ is trivially bounded below by $\binom{n}{2}$ because a Golomb ruler with $n$ marks measures exactly $\binom{n}{2}$ distinct distances [8]. A proof of a better lower bound of $n^2+\sqrt{n}(1-2n)-2$ can be found in [8]. Regarding upper bounds, the best-known upper bound for any number of marks $n$ is $G(n) \le 2n^3 + n$. A conjecture attributed to Erdős states that $G(n) \le n^2 + c$, where $c \in \mathbb{R}$. Computationally, this conjecture was proven to be true for $n \le 65000$ [8].

The GRP has been studied since the 1960s and remains a very challenging problem from both theoretical and computational points of view. Indeed, to the best of our knowledge, its complexity remains an open question, and it is not even known if the Golomb Ruler Decision Problem (given two integers $n$ and $\ell$, is there a Golomb ruler with at least $n$ marks and length at most $\ell$?) belongs to the complexity class NP or not [23]. Moreover, the optimal Golomb ruler with 28 marks was announced last year after approximately 8.5 years of computational efforts using an enumeration approach implemented on a distributed architecture (distributed.net project OGR-28).

During the last few years, in addition to the exact approach implemented in the project OGR-28, two other exact approaches to compute optimal Golomb rulers have also been investigated: constraint programming-based approaches [13] and mathematical programming-based approaches [16, 22]. Moreover, a lot of work has been done to compute near-optimal Golomb rulers using different principles. For instance, construction methods from number theory [10, 11, 26]; hybrid evolutionary heuristic [9]; hybrid search heuristic [28]; and genetic algorithms [36].

Finally, the GRP has many applications. To cite a few, in telecommunication engineering [2], in radio-astronomy [2], in error-correcting codes [30], and x-ray analysis of crystal structures [5].

## 1.2. Related works

The starting point of this work is the conjecture presented in [12]. This conjecture concerns the solution of the continuous relaxation of a non-convex quadratically constrained integer programming model (see Sect. 3) for the GRP. This model is derived from a mathematical programming model first presented in [16], which we recall below.

Let $\hat{L}$ be a given upper bound on the length of an optimal Golomb ruler with $n$ marks. The length of an optimal Golomb ruler can be computed using the following nonlinear programming model:

$$ (K_0) \quad \left\{ \begin{array}{ll} \min & \max \{kx_k : k = 1, \dots, \hat{L}\} \\ \text{s.t.} & x_j + \sum_{k=1}^{\hat{L}-j} x_k x_{k+j} \le 1, j = 1, \dots, \hat{L}-1, \\ & x_k \in \{0, 1\}, k = 1, \dots, \hat{L}, \end{array} \right. \quad (1a) $$

where, for every index $k$, the variable $x_k$ assumes value 1 if and only if the $k$-th mark is chosen. The $j$-th quadratic constraint in (1a) imposes that if the $j$-th mark is selected then no other pair of marks at distance $j$ from each other can be selected.

In [16], the authors conducted a computational comparison between three different optimization approaches to solve the GRP. In the first approach, they considered several enhancements, including bound tightening and branching strategies, to solve two well-known integer linear programming formulations of the GRP [19, 22] using a branch-and-bound algorithm. In the second approach, they considered solving another well-known constraint programming-based model [34, 35] for the GRP and introduced several enhancements as well. In the third approach, they considered solving the GRP using the model (K₀) above. Two approaches based on equivalent formulations of the model (K₀) were considered. The first one is based on a mixed-integer semi-definite reformulation of (K₀). The second is based on what the authors called the feasibility version of the model (K₀). This version is used to certify the length of an optimal Golomb ruler (see [16] for more detail). Their approaches differ from the one presented in this work.
Indeed, the approach presented in this work uses the well-known reformulation-linearization approach to derive strong models to the GRP from the following binary mixed integer linear programming (BMILP for short) problem equivalent to the program ($K_0$). This BMILP model, also stated in [12, 16], reads:

$$ (K_1) \quad \left\{ \begin{array}{ll} \min & \zeta \\ \text{s.t.} & kx_k \le \zeta, \ k = 1, \dots, \hat{L}, \tag{2a} \\ & \sum_{k=1}^{\hat{L}} x_k = n-1, \tag{2b} \\ & x_j + \sum_{k=1}^{\hat{L}-j} x_k x_{k+j} \le 1, \ j = 1, \dots, \hat{L}-1, \tag{2c} \\ & x_k \in \{0, 1\}, \ k = 1, \dots, \hat{L}. \tag{2d} \end{array} \right. $$

Notice that the equality constraint (2b) is mandatory; otherwise, the zero vector is an optimal solution.

## 1.3. Our contributions

The contributions of this work are threefold. Firstly, we propose a simple proof of the conjecture stated in [12]. A proof based on arguments from algebraic geometry is presented in the non-peer-reviewed paper [18]. Secondly, we investigate the computational efficiency of four new BMILP models for the GRP. These models are derived from an equivalent BMILP model to the non-linear integer programming model ($K_0$) using the well-known reformulation-linearization technique. Thirdly, we provide the correct outputs of the greedy heuristic proposed in [12], and we correct false conclusions stated or suggested in therein.

The rest of the paper is organized as follows. In Section 2, we recall the principal concepts and the main theorem of the Reformulation-Linearization technique. Then, in Section 3, we detail our proof of the conjecture stated in [12]. In Section 4, we describe the new BMILP models for the GRP. In Section 5, we investigate the computational efficiency of these proposed models and provide the correct outputs of the greedy heuristic proposed in [12] to compute feasible Golomb rulers. Finally, we give concluding remarks in Section 6.

## 2. THE REFORMULATION LINEARIZATION TECHNIQUE

The Reformulation Linearization Technique (RLT) for BMILP problems was introduced and studied by Sherali-Adams in [32, 33]. It produces, for a given BMILP model, a finite hierarchy of continuous relaxations with increasing strength, where the relaxation of the higher rank is the description of the convex hull of the set of integer feasible solutions of the considered BMILP. The RLT approach of Sherali-Adams extends the Lift-and-Project hierarchy of Balas [3]. Several other hierarchies are known, such as Lovász-Shrijver [20], Lasserre [17], and the DRL* hierarchy of Minoux and Ouzia [24]. A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre hierarchies can be found in [25]. Links between DRL*, RLT, and Lift-and-Project hierarchies can be found in [24]. To be self-contained, we recall below the general RLT principle for BMILP problems; more details can be found in [24, 32, 33].

Let $P$ be a subset of $\mathbb{R}_+^{n_1+n_2}$ describing the set of feasible solutions of a BMILP problem featuring $n_1$ binary variables and $n_2$ continuous variables. Let us assume that $P$ features the following linear description:

$$ \sum_{j=1}^{n_1+n_2} a^j x_j \le b, \tag{3} $$

$$ x_j \le 1 \text{ for all } j \in E = \{1, \dots, n_1\}, \tag{4} $$

$$ -x_j \le 0 \text{ for all } j \in N = \{1, \dots, n_1 + n_2\}, \tag{5} $$

$$ x_j \in \{0, 1\} \text{ for all } j \in E. \tag{6} $$
In the above description, $E$ is the index set of the $n_1$ binary variables describing $P$; $N$ is the index set of all the variables; and for each index $j \in N$, the vectors $a^j$ and $b$ belong to $\mathbb{R}^m$, where $m$ is the number of constraints in (3).

The continuous relaxation of the integer set $P$, denoted $\bar{P}$, is the polyhedron defined by the $m + 2n_1 + n_2$ constraints (3)–(5). Recall that two linear descriptions are said to be equivalent if they define the same polyhedron, and a linear description $D_1$ dominates another linear description $D_2$ if the polyhedron defined by $D_1$ is included in the polyhedron defined by $D_2$.

Let $p$ be a positive integer, and let $S$ be a finite non-empty set. The notation $S^{[p]}$ will denote the set of all subsets of $S$ with cardinality $p$, while $S^p$ will indicate that the set $S$ has cardinality $p$ ($S$ will be called a $p$-element set).

Let $J^d$ be a $d$-element subset of $E$ and let $J$ be a subset from $J^d$. The $d$-factor associated with the sets $J$ and $J^d$, denoted $F_d(J, J^d \setminus J)$, is the degree $d$ polynomial:

$$F_d(J, J^d \setminus J) = \prod_{j \in J} x_j \prod_{j \in J^d \setminus J} (1 - x_j).$$

We use the convention that $F_0(\emptyset, \emptyset) = 1$. Notice that $F_d(J, J^d \setminus J)$ is nonnegative for all $x \in [0, 1]^{n_1}$.

A rank $d$ reformulation-linearization relaxation (of the mixed integer set $P$) is defined in three steps. First, the problem is reformulated as a 0-1 polynomial mixed integer system (semi-algebraic set$^2$) by multiplying the constraints (3)–(5) with all $d$-factors. Then, the nonlinear terms are linearized by introducing new variables, giving rise to a higher-dimensional linear description. The last step consists of projecting back the resulting polyhedron onto the original $x$-space. The linearization step can be performed in many different ways, possibly leading to as many different hierarchies of relaxations [24].

The solution set in $\mathbb{R}^{n_1+n_2}$ associated with the nonlinear description resulting from the reformulation step will be denoted $R_*^d$ and reads:

$$R_*^d = \bigcap_{J^d \in E^{[d]}} R^d(J^d),$$

where, for each subset $J^d$ of $E$, $R^d(J^d)$ is the following nonlinear system:

$$\sum_{j=1}^{n_1+n_2} a^j x_j F_d(J, J^d \setminus J) - b F_d(J, J^d \setminus J) \le 0 \quad \text{for all } J \subseteq J^d, \qquad (7)$$

$$x_j F_d(J, J^d \setminus J) - F_d(J, J^d \setminus J) \le 0 \quad \text{for all } j \in E \text{ and } J \subseteq J^d, \qquad (8)$$

$$x_j F_d(J, J^d \setminus J) \ge 0 \quad \text{for all } j \in N \text{ and } J \subseteq J^d, \qquad (9)$$

$$F_d(J, J^d \setminus J) \ge 0 \quad \text{for all } J \subseteq J^d. \qquad (10)$$

Starting from this non-linear reformulation, various linear descriptions can be constructed depending on the type of linearization considered. Below, we recall the Sherali-Adams linearization [32, 33]. Other linearizations are possible [24, 27].

The description of the rank $d$ Sherali-Adams relaxation for the polyhedron $\bar{P}$, denoted $\hat{P}_{RLT}^d$, is a Reformulation-Linearization relaxation of rank $d$ where the nonlinear terms in (7)–(10) are linearized by intro-

<footnote>$^2$A semi-algebraic set in $n$ dimensions is a subset of $\mathbb{R}^n$ defined as the solution set of a finite system of polynomial equalities and inequalities; see [4, 7].</footnote>
ducing new variables $w_J$ and $w_J^k$ defined by:

$$w_J = \prod_{j \in J} x_j \quad \text{for all } J \subseteq E \text{ and } |J| \le \min(d+1, n_1), \qquad (11)$$

$$w_J^k = x_k \prod_{j \in J} x_j \quad \text{for all } k \in N \setminus E, J \subseteq E \text{ and } |J| \le d, \qquad (12)$$

where it is assumed that $w_\emptyset = 1$, and $w_\emptyset^k = x_k$ for every index $k$ in $N \setminus E$.

The resulting higher dimensional linear description will be denoted $P_{RLT}^d$ and it is defined as follows:

$$P_{RLT}^d = \bigcap_{J^d \in E^{[d]}} Q_{RLT}^d (J^d), \qquad (13)$$

where, for each subset $J^d$ of $E$, the polyhedron $Q_{RLT}^d (J^d)$ is

$$\sum_{j=1}^{\kappa} a^j W_j^{J, J^d} - b W_0^{J, J^d} \le 0 \quad \text{for all } J \subseteq J^d, \qquad (14)$$

$$W_j^{J, J^d} - W_0^{J, J^d} \le 0 \quad \text{for all } j \in E \text{ and } J \subseteq J^d, \qquad (15)$$

$$W_j^{J, J^d} \ge 0 \quad \text{for all } j \in N \text{ and } J \subseteq J^d, \qquad (16)$$

$$W_0^{J, J^d} \ge 0 \quad \text{for all } J \subseteq J^d. \qquad (17)$$

and where, for every $j$ in $N$, $W_j^{J, J^d}$ and $W_0^{J, J^d}$ denote the linearized forms of the polynomials $x_j F_d (J, J^d \setminus J)$ and $F_d (J, J^d \setminus J)$ respectively; these are related to the $w_J$ and $w_J^k$ variables as follows:

$$W_j^{J, J^d} = \sum_{J \subseteq H \subseteq J^d} (-1)^{|H \setminus J|} w_{H \cup \{j\}} \quad \text{for all } J^d, J \subseteq J^d \text{ and } j \in E, \qquad (18)$$

$$W_j^{J, J^d} = \sum_{J \subseteq H \subseteq J^d} (-1)^{|H \setminus J|} w_H^j \quad \text{for all } J^d, J \subseteq J^d \text{ and } j \in N \setminus E, \qquad (19)$$

$$W_0^{J, J^d} = \sum_{J \subseteq H \subseteq J^d} (-1)^{|H \setminus J|} w_H \quad \text{for all } J^d, J \subseteq J^d. \qquad (20)$$

(The above expressions (18)–(20) can also be found in [33]). Notice that the constraints (16)–(17) imply the non-negativity of the variables $w_J$ and $w_J^k$. The rank $d$ Sherali-Adams relaxation $\hat{P}_{RLT}^d$ is obtained by projecting the polyhedron $P_{RLT}^d$ onto $\mathbb{R}^{n_1+n_2}$.

The following theorem states the two main results concerning the Sherali-Adams relaxations.

**Theorem 2.1** (Sherali-Adams [31, 33]). For every integer $d \in \{1, \dots, n_1 - 1\}$, we have:

$$\hat{P}_{RLT}^{d+1} \subseteq \hat{P}_{RLT}^d.$$

Moreover, the rank $n_1$ Sherali-Adams relaxation of the set $\bar{P}$ coincides with the convex hull of the integer set $P$, that is:

$$\mathrm{conv}(P) = \hat{P}_{RLT}^{n_1}.$$

In essence, this theorem provides a procedure to compute, at least in theory, the convex hull of the integer set $P$. Additionally, it defines a finite hierarchy of continuous relaxations that can be used as alternatives to
the continuous relaxation $\bar{P}$ for optimizing any linear function over $P$. The rank of each relaxation serves as a measure of its strength.

As a final definition, the Sherali-Adams relaxation obtained using a subset of the $d$-factors or a subset of the constraints (3) will be called a *partial rank $d$ Sherali-Adams relaxation*. It is evident that any partial rank $d$ Sherali-Adams relaxation contains the corresponding rank $d$ relaxation.

In this work, we will use partial rank 1 and 2 Sherali-Adams relaxations because they feature smaller size. Indeed, after linearizing the nonlinear terms in (7)–(10) using the $w$ variables defined in (11) and (12) above, the $P_{RLT}^d$ description features $\sum_{k=1}^{\min\{d+1,n\}} \binom{n}{k} + m \sum_{k=0}^{d} \binom{n}{k}$ variables (notice that the variable $w_0$ is not counted here since $w_0 = 1$) and $O(\binom{n}{d} (n_1 + n_2) 2^d)$ constraints.

### 3. PROOF OF THE CONJECTURE

In [12], the authors proposed the following continuous non-convex quadratically constrained model to solve the GRP with $n$ marks:

$$ (\hat{K}) \left\{ \begin{array}{ll} \min & \zeta \\ \text{s.t.} & kx_k \le \zeta x_k, \ k = 1, \dots, \hat{L}, \\ & \hat{L} \sum_{k=1}^{\hat{L}} x_k = n-1, \\ & x_j + \sum_{k=1}^{\hat{L}-j} x_k x_{k+j} \le 1, \ j = 1, \dots, \hat{L}-1, \\ & \zeta \in \mathbb{R}_+, \ x_k \in [0, 1], \ k = 1, \dots, \hat{L}. \end{array} \right. \qquad \begin{array}{l} (21a) \\ (21b) \\ (21c) \\ (21d) \end{array} $$

And, they stated the following conjecture.

**Conjecture 3.1.** Given an upper bound $\hat{L}$ of the length of an optimal Golomb rule with $n$ marks. It is true that any optimal solution to the model ($K_1$) is an optimal solution to the model ($\hat{K}$).

Rephrased differently, this conjecture states that the optimal Golomb rulers with $n$ marks constitute a subset of the set of optimal solutions of the model ($\hat{K}$).

Before proving this conjecture, one can observe that the model ($\hat{K}$) is the continuous relaxation of the model ($K$) given below, which in turn is a partial rank 1 Sherali-Adams reformulation of the constraints (2a) of the model ($K_1$).

$$ (K) \left\{ \begin{array}{ll} \min & \zeta \\ \text{s.t.} & kx_k \le \zeta x_k, \ k = 1, \dots, \hat{L}, \\ & \hat{L} \sum_{k=1}^{\hat{L}} x_k = n-1, \\ & x_j + \sum_{k=1}^{\hat{L}-j} x_k x_{k+j} \le 1, \ j = 1, \dots, \hat{L}-1, \\ & \zeta \in \mathbb{R}_+, \ x_k \in \{0, 1\}, \ k = 1, \dots, \hat{L}. \end{array} \right. \qquad \begin{array}{l} (22a) \\ (22b) \\ (22c) \\ (22d) \end{array} $$

Thus, according to Theorem 2.1, the models ($K_1$) and ($K$) feature the same set of feasible solutions. Indeed, the $k$-th constraint of (22a) is obtained by first multiplying the $k$-th constraint of (2a) by the non-negative
variable $x_k$ and then replacing $x_k^2$ with $x_k$, because $x_k$ is binary. These two steps preserve the feasible solutions of (K1).

Building upon this observation, in Section 4 and 5, we will propose four new BMILP models for the GRP, derived from the model (K1) using the partial rank 1 and 2 Sherali-Adams reformulation-linearization technique.

Coming back to the conjecture, below, a straightforward proof.

*Proof.* (Conjecture 3.1) It is sufficient to prove that any optimal solution to the model (K) is an optimal solution to the model (K̂). Because, as mentioned above, the two models (K) and (K1) share the same feasible solutions and thus the same optimal solutions.

Let $(L, x_*)$ be an optimal solution to the model (K). By contradiction, assume that there exists an optimal solution $(\hat{\zeta}, \hat{x})$ to the model (K̂) such that $\hat{\zeta} < L$. Recall that we already have $\hat{\zeta} \le L$, because the model (K̂) is the continuous relaxation of the model (K). It follows from our assumption that, for every feasible solution $(\zeta, x)$ of the model (K̂), it must be true that $x_L = 0$, otherwise, if $x_L \in ]0, 1]$ then:

$$Lx_L \le \zeta x_L \Rightarrow \zeta \ge L, \qquad (23)$$

which implies that $\hat{\zeta} \ge L$, contradicting our assumption. Consequently, the constraint $x_L \le 0$ is valid for the set of feasible solutions of the model (K̂) and it cuts off the optimal integer solution $(L, x_*)$ of the model (K). This is impossible because the model (K̂) contains all the integer solutions of the model (K). Therefore, we must have $\hat{\zeta} = L$. Since $x_*$ is a feasible solution of the model (K̂) and it has the same value as its optimal solution $(\hat{\zeta}, \hat{x})$, then $(L, x_*)$ is an optimal solution of the continuous model (K̂). This completes the proof. □

Thus, one can state the following:

**Theorem 3.2.** Given an upper bound $\hat{L}$ of the length of an optimal Golomb rule with n marks. It is true that any optimal solution to the model (K1) is an optimal solution to the model (K̂).

Two other facts concerning the optimal solutions of the model (K̂) can be easily demonstrated. Let us emphasize the two parameters n and $\hat{L}_n$ in the program (K̂) by the notation $(\hat{K}_{n, \hat{L}_n})$. Let $\ell_n$ be the length of an optimal Golomb ruler featuring n marks.

**Proposition 3.3.** For any optimal solution $(\hat{\zeta}, \hat{x})$ of the program $(\hat{K}_{n, \ell_n})$, the component $\hat{x}_{\ell_n}$ is equal to 1 and $\hat{\zeta}$ is equal to $\ell_n$.

*Proof.* Let $(\hat{\zeta}, \hat{x})$ be an optimal solution the program $(\hat{K}_{n, \ell_n})$. Then, $\hat{\zeta} \le \ell_n$ and the point $(\hat{\zeta}, \hat{x})$ satisfies the inequality $\hat{\zeta} \ge \ell_n x_{\ell_n}$ (obtained by multiplying $x_{\ell_n} \le 1$ by $\hat{\zeta}$, which is a positive quantity, and then noticing that $\hat{\zeta} x_{\ell_n} \ge \ell_n x_{\ell_n}$). Thus, if $\hat{x}_{\ell_n} < 1$ then $(\ell_n \hat{x}_{\ell_n}, \hat{x})$ is a feasible solution to the program $(\hat{K}_{n, \ell_n})$ with a better value, contradicting the optimality of $(\hat{\zeta}, \hat{x})$. Consequently, $\hat{x}_{\ell_n} = 1$ and $\hat{\zeta} \ge \ell_n$ implying that $\hat{\zeta} = \ell_n$. This completes the proof. □

**Proposition 3.4.** For any optimal solution $(\ell_n, \hat{x})$ of the program $(\hat{K}_{n, \hat{L}_n})$, the component $\hat{x}_k = 0$ for $k > \ell_n$.

*Proof.* Let $(\ell_n, \hat{x})$ be an optimal solution to the program $(\hat{K}_{n, \hat{L}_n})$. By contradiction, let us assume that there exists an index $k > \ell_n$ such that $\hat{x}_k \in ]0, 1]$. Thus, we have:

$$\ell_n \hat{x}_k < k \hat{x}_k. \qquad (24)$$

But, from the constraints (21a), we also have $k \hat{x}_k \le \ell_n \hat{x}_k$. Then, it follows that $\ell_n \hat{x}_k < \ell_n \hat{x}_k$, which is absurd. Consequently, for all $k > \ell_n$, we have $\hat{x}_k = 0$, which completes the proof. □
## 4. NEW MODELS

In this section, we provide the descriptions of four new BMILP models proposed to solve the GRP. The first three models are obtained using a partial rank-1 Sherali-Adams relaxation, while the last one is based on a partial rank-2 relaxation.

First, notice that the model (K1) is equivalent to the following BMILP model:

$$
\begin{equation}
\begin{array}{ll}
\left\{
\begin{array}{@{}l@{}}
  \min \\
  \text{s.t.}
\end{array}
\right.
& \zeta \\[1ex]
\text{(G)} &
\left\{
\begin{array}{@{}l@{}}
  kx_k \le \zeta, \quad k = 1, \dots, \hat{L}, \hfill (25a) \\[1ex]
  \sum_{k=1}^{\hat{L}} x_k = n-1, \hfill (25b) \\[1ex]
  x_j + \sum_{k=1}^{\hat{L}-j} w_{k,k+j} \le 1, \quad j = 1, \dots, \hat{L}-1, \hfill (25c) \\[1ex]
  x_k + x_j - w_{kj} \le 1, \quad 1 \le k < j \le \hat{L}, \hfill (25d) \\[1ex]
  w_{kj} \le x_j, \quad 1 \le k < j \le \hat{L}, \hfill (25e) \\[1ex]
  w_{kj} \le x_k, \quad 1 \le k < j \le \hat{L}, \hfill (25f) \\[1ex]
  w_{kj} \ge 0, \quad 1 \le k < j \le \hat{L}, \hfill (25g) \\[1ex]
  x_k \in \{0, 1\}, \quad k = 1, \dots, \hat{L}, \hfill (25h) \\[1ex]
  \zeta \in \mathbb{R}_+. \hfill (25i)
\end{array}
\right\}
\end{array}
\end{equation}
$$

Indeed, the quadratic terms appearing in the constraints (2c) are linearized using the well-known McCormick inequalities [21], which lead to the constraints (25c)–(25f). In the sequel, the constraints (25d)–(25f) will appear frequently. To avoid repeating them, we introduce the following set:

$$
\mathcal{M} = \left\{ (x, w) \in \mathbb{R}^{\hat{L}} \times \mathbb{R}^{\binom{\hat{L}}{2}} : (\text{25d}) -- (\text{25g}) \right\}. \quad (26)
$$

Linearizing in the model (K) the products $\zeta x_k$ using new variables $v_k$ and using the McCormick inequalities to linearize the quadratic terms appearing in the constraints (22c), we obtain the following BMILP equivalent model:

$$
\[
\mathbf{M}_1
\begin{cases}
\min & \zeta \\
\text{s.t.} & \\
& kx_k \le v_k, \quad k = 1, \dots, \hat{L}, \tag{27a} \\
& v_k \le \zeta, \quad k = 1, \dots, \hat{L}, \tag{27b} \\
& v_k \le \hat{L}x_k, \quad k = 1, \dots, \hat{L}, \tag{27c} \\
& v_k \ge \zeta + \hat{L}(x_k - 1), \quad k = 1, \dots, \hat{L}, \tag{27d} \\
& \sum_{k=1}^{\hat{L}} x_k = n-1, \tag{27e} \\
& x_j + \sum_{k=1}^{\hat{L}-j} w_{k,k+j} \le 1, \quad j = 1, \dots, \hat{L}-1, \tag{27f} \\
& \zeta \in \mathbb{R}_+, (x,w) \in \mathcal{M}, \tag{27g} \\
& x_k \in \{0,1\}, k = 1, \dots, \hat{L}. \tag{27h}
\end{cases}
\]
$$
The model (M₁) can be seen as derived from the model (G) using a partial rank 1 Sherali-Adams reformulation, where the k-th constraint (25a) is first multiplied by $x_k$. Then, the term $x_k^2$ is replaced by $x_k$, because $x_k$ is binary. Finally, the products $\zeta x_k$ are linearized using the constraints (27a)-(27d). To avoid repeating the linearization constraints (27b)-(27d), let $\mathcal{V}$ be the following set:

$$ \mathcal{V} = \left\{ (x, w, v) \in \mathbb{R}^{\hat{L}} \times \mathbb{R}^{(\frac{\hat{L}}{2})} \times \mathbb{R}^{\hat{L}} : (27b) -- (27d) \right\}. \quad (28) $$

In the sequel, we propose two other BMILP models for the GRP. These models are obtained, as above, by a partial rank 1 Sherali-Adams reformulation-linearization approach applied to the model (G).

The model (M₂) below is obtained from the model (G) using a complete rank 1 Sherali-Adams reformulation-linearization of the constraints (25a). This means that these constraints are first multiplied by the 1-factors $x_j$ and $1-x_j$, for all $j \in \{1, \dots, \hat{L}\}$. Then, the products $\zeta x_k$ are linearized using the new variables $v_k$. Additionally, for every pair of indexes $(i, j)$ such that $i < j$, the product $x_i x_j$ is linearized using the variable $w_{ij}$. This model (M₂) reads:

$$ \begin{array}{ll} \text{min} & \zeta \\ \text{s.t.} & \\ & kx_k \le v_k, \quad k = 1, \dots, \hat{L}, \qquad (29a) \\ & kw_{kj} \le v_j, \quad 1 \le k < j \le \hat{L}, \qquad (29b) \\ & kx_k - kw_{kj} \le \zeta - v_j, \quad 1 \le k < j \le \hat{L}, \qquad (29c) \\ & \sum_{k=1}^{\hat{L}} x_k = n-1, \qquad (29d) \\ & x_j + \sum_{k=1}^{\hat{L}-j} w_{k,k+j} \le 1, \quad j = 1, \dots, \hat{L}-1, \qquad (29e) \\ & \zeta \in \mathbb{R}_{+}, (x, w) \in \mathcal{M}, (x, w, v) \in \mathcal{V}, \qquad (29f) \\ & x_k \in \{0, 1\}, k = 1, \dots, \hat{L}. \qquad (29g) \end{array} $$

The model (M₃) below is obtained from the model (G) using a complete rank 1 Sherali-Adams reformulation-linearization of the constraints (25a) and (25b). In other words, the model (M₃) is obtained from the model (M₂) using, in addition, a complete rank 1 Sherali-Adams reformulation-linearization of the constraint (29d), where only the 1-factors $\{x_j : j = 1, \dots, \hat{L}\}$ are needed. We obtain the same constraints using the 1-factors $\{1 - x_j : j = 1, \dots, \hat{L}\}$.
$$
\begin{equation}
\begin{aligned}
& \left(\mathbf{M}_3\right) \left\{
\begin{array}{@{}l@{}}
\displaystyle \min \quad \zeta \\[1ex]
\text{s.t.} \quad \begin{array}{@{}l@{}}
\displaystyle kx_k \le v_k, \quad k = 1, \dots, \hat{L}, \hfill (30a) \\
\displaystyle kw_{kj} \le v_j, \quad 1 \le k < j \le \hat{L}, \hfill (30b) \\
\displaystyle kx_k - kw_{kj} \le \zeta - v_j, \quad 1 \le k < j \le \hat{L}, \hfill (30c) \\
\displaystyle \quad \sum_{k=1}^{\hat{L}} x_k = n-1, \hfill (30d) \\
\displaystyle \quad \sum_{k=1}^{j-1} w_{kj} + \sum_{k=j+1}^{\hat{L}} w_{jk} = (n-2)x_j, \quad j = 1, \dots, \hat{L} \hfill (30e) \\
\displaystyle \quad x_j + \sum_{k=1}^{\hat{L}-j} w_{k,k+j} \le 1, \quad j = 1, \dots, \hat{L}-1, \hfill (30f) \\
\displaystyle \quad \zeta \in \mathbb{R}_+, (x,w) \in \mathcal{M}, (x,w,v) \in \mathcal{V}, \hfill (30g) \\
\displaystyle \quad x_k \in \{0,1\}, k = 1, \dots, \hat{L}. \hfill (30h)
\end{array}
\right\}
\end{aligned}
\end{equation}
$$

Finally, we introduce the model (M₄), which is obtained through a partial rank-2 Sherali-Adams reformulation
of the base model (G) as outlined below.

$$
\begin{equation}
\left(\mathbf{M}_4\right) \left\{
\begin{array}{@{}l@{}}
\displaystyle \min \quad \zeta \\[1ex]
\text{s.t.} \quad \begin{array}{@{}l@{}}
\displaystyle kx_k \le v_k, \quad 1 \le k \le \hat{L}, \hfill (31a) \\
\displaystyle kw_{kj} \le u_{kj}, \quad 1 \le k < j \le \hat{L}, \hfill (31b) \\
\displaystyle kw_{kj} - kx_k \le v_k - u_{kj}, \quad 1 \le k < j \le \hat{L}, \hfill (31c) \\
\displaystyle u_{kj} \le \zeta, \quad 1 \le k < j \le \hat{L}, \hfill (31d) \\
\displaystyle u_{kj} \le \hat{L}w_{kj}, \quad 1 \le k < j \le \hat{L}, \hfill (31e) \\
\displaystyle u_{kj} \ge \zeta + \hat{L}(w_{kj} - 1), \quad 1 \le k < j \le \hat{L}, \hfill (31f) \\
\displaystyle \quad \sum_{k=1}^{\hat{L}} x_k = n-1, \hfill (31g) \\
\displaystyle \quad x_j + \sum_{k=1}^{\hat{L}-j} w_{k,k+j} \le 1, \quad j = 1, \dots, \hat{L}-1, \hfill (31h) \\
\displaystyle \quad \zeta \in \mathbb{R}_+, (x,w) \in \mathcal{M}, (x,w,v) \in \mathcal{V}, \hfill (31i) \\
\displaystyle \quad u_{kj} \ge 0, \quad 1 \le k < j \le \hat{L}, \hfill (31j) \\
\displaystyle \quad x_k \in \{0,1\}, k = 1, \dots, \hat{L}. \hfill (31k)
\end{array}
\right\}
\end{equation}
$$

The constraints (25a) of the model (G) are reformulated using the factors:

$$
\{x_k : 1 \le k \le \hat{L}\} \quad \text{and} \quad \{x_k x_j, x_k (1-x_j) : 1 \le k < j \le \hat{L}\}. \qquad (32)
$$

The new variables $u_{kj}$ are used to linearize the new products $\zeta x_k x_j$. The variables $v$ and $w$ are as defined previously.
## 5. COMPUTATIONAL RESULTS

The computational results presented in this section have two purposes. The first one is to provide the correct outputs of the greedy heuristic presented in [12] for computing feasible Golomb rulers. The second purpose is to compare the computational efficiency of the models (G), (M₁), (M₂), (M₃), (M₄), and (K) in solving the GRP. Moreover, we also correct the false conclusions stated or implied in [12].

### 5.1. The heuristic

The computational results reported in this subsection were obtained using a Dell-Optiplex desktop with an Intel-Core-i7-9700 CPU running at 2.0 GHz with 8 cores, and 32 GB of RAM. The desktop is operated by a Linux Ubuntu 18.05.06 LTS operating system.

In [12], the authors proposed a greedy heuristic (referred to as H) to compute feasible Golomb rulers. For the sake of completeness, we provide its pseudo-code below. The variables `mark` and `dist` are two boolean arrays such that `mark(k) = 1` (resp. `dist(k) = 1`) if and only if the mark (resp. distance) `k` is not used.

<caption>**Algorithm 1:** Greedy heuristic H.</caption>

1. Input $n$ (number of marks)
2. Outputs $\text{ruler}(\text{set containing ruler's marks})$; $\text{lruler}(\text{ruler's length})$
3. begin
4. &nbsp;&nbsp;&nbsp;&nbsp;limit $\leftarrow \text{MaxInt}$ &nbsp;&nbsp;&nbsp;&nbsp; // Upper-bound to the Golomb ruler's length
5. &nbsp;&nbsp;&nbsp;&nbsp;for $k \in \{0, 1\}$ do
6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lfloor \text{mark}(k) \leftarrow 0; \text{dist}(k) \leftarrow 0$&nbsp;&nbsp;&nbsp;&nbsp;
7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for $k \in \{2, \dots, \text{limit}\}$ do
8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lfloor \text{mark}(k) \leftarrow 1; \text{dist}(k) \leftarrow 1$&nbsp;&nbsp;&nbsp;&nbsp;
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{lruler} \leftarrow 1; k \leftarrow 1$
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while $k < n-1$ do
11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lfloor d \leftarrow 1; \text{infeasible} \leftarrow 1$&nbsp;&nbsp;&nbsp;&nbsp;
12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while $\text{infeasible}$ do
13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $\text{dist}(d)$ then
14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lfloor \text{length} \leftarrow \text{lruler} + d \rfloor$ &nbsp;&nbsp;&nbsp;&nbsp;
15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow 0$ &nbsp;&nbsp;&nbsp;&nbsp; // Check if length is feasible.
16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while $(\text{mark}(i) \text{ or } \text{dist}(\text{length} - i)) \text{ and } i < \text{length} + 1$ do
17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lfloor i \leftarrow i + 1 \rfloor$&nbsp;&nbsp;&nbsp;&nbsp;
18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $i = \text{length} + 1$ then
19. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lfloor \text{lruler} \leftarrow \text{length} \rfloor$
20. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{mark}(\text{lruler}) \leftarrow 0$
21. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for $i \in \{0, \dots, \text{lruler} - 1\}$ do
22. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lfloor \text{if not mark}(i) \text{ then } \text{dist}(\text{lruler} - i) \leftarrow 0 \rfloor$&nbsp;&nbsp;&nbsp;&nbsp;
23. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{infeasible} \leftarrow 0$
24. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lfloor d \leftarrow d + 1 \rfloor$
25. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k \leftarrow k + 1$
26. &nbsp;&nbsp;&nbsp;&nbsp;$\text{ruler} \leftarrow \{\}$ &nbsp;&nbsp;&nbsp;&nbsp; // Extract ruler's marks
27. &nbsp;&nbsp;&nbsp;&nbsp;for $k \in \{0, \dots, \text{lruler}\}$ do
28. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lfloor \text{if not mark}(k) \text{ then } \text{ruler} \leftarrow \text{ruler} \cup \{k\} \rfloor$&nbsp;&nbsp;&nbsp;&nbsp;
29. &nbsp;&nbsp;&nbsp;&nbsp;return $\text{ruler}$, $\text{lruler}$&nbsp;&nbsp;&nbsp;&nbsp; // Extract ruler's marks
<table><caption>TABLE 1. Correct lengths obtained using the greedy heuristic H.</caption><thead><tr><th rowspan="2">n</th><th colspan="2">Length</th><th colspan="2">Gap</th><th rowspan="2">n<sup>2</sup></th></tr><tr><th>Opt</th><th>H</th><th>abs.</th><th>rel.(%)</th></tr></thead><tbody><tr><td>5</td><td>11</td><td>12</td><td>1</td><td>8.33</td><td>25</td></tr><tr><td>6</td><td>17</td><td>20</td><td>3</td><td>15.00</td><td>36</td></tr><tr><td>7</td><td>25</td><td>30</td><td>5</td><td>16.67</td><td>49</td></tr><tr><td>8</td><td>34</td><td>44</td><td>10</td><td>22.72</td><td>64</td></tr><tr><td>9</td><td>44</td><td>65</td><td>21</td><td>32.31</td><td>81</td></tr><tr><td>10</td><td>55</td><td>80</td><td>25</td><td>31.25</td><td>100</td></tr><tr><td>11</td><td>72</td><td>96</td><td>24</td><td>25.00</td><td>121</td></tr><tr><td>12</td><td>85</td><td>122</td><td>37</td><td>30.33</td><td>144</td></tr><tr><td>13</td><td>106</td><td>147</td><td>41</td><td>27.89</td><td>169</td></tr><tr><td>14</td><td>127</td><td>181</td><td>54</td><td>29.83</td><td>196</td></tr><tr><td>15</td><td>151</td><td>203</td><td>52</td><td>25.62</td><td>225</td></tr><tr><td>16</td><td>177</td><td>251</td><td>74</td><td>29.48</td><td>256</td></tr><tr><td>17</td><td>199</td><td>289</td><td>90</td><td>31.14</td><td>289</td></tr><tr><td>18</td><td>216</td><td>360</td><td>144</td><td>40.00</td><td>324</td></tr><tr><td>19</td><td>246</td><td>400</td><td>154</td><td>38.50</td><td>361</td></tr><tr><td>20</td><td>283</td><td>474</td><td>191</td><td>40.30</td><td>400</td></tr><tr><td>21</td><td>333</td><td>564</td><td>231</td><td>40.96</td><td>441</td></tr><tr><td>22</td><td>356</td><td>592</td><td>236</td><td>39.86</td><td>484</td></tr><tr><td>23</td><td>372</td><td>661</td><td>289</td><td>43.72</td><td>529</td></tr><tr><td>24</td><td>425</td><td>774</td><td>349</td><td>45.09</td><td>576</td></tr><tr><td>25</td><td>480</td><td>821</td><td>341</td><td>41.53</td><td>625</td></tr><tr><td>26</td><td>492</td><td>915</td><td>423</td><td>46.23</td><td>676</td></tr><tr><td>27</td><td>553</td><td>969</td><td>416</td><td>42.93</td><td>729</td></tr><tr><td>28</td><td>585</td><td>1015</td><td>430</td><td>42.36</td><td>784</td></tr></tbody></table>

Unfortunately, the implementation proposed in https://github.com/luizleduino/golombruler/blob/master/heuristic is buggy and the lengths reported in [12] are incorrect. Indeed, as implemented, the heuristic H returns non-Golomb rulers for $n \ge 9$. In the case of $n = 9$, it returns the ruler (0, 1, 3, 7, 12, 20, 30, 44, 59), which is not a Golomb ruler because 59 - 30 is equal to 30 - 1. Additionally, the computed rulers with $n \ge 10$ all have as their first 10 marks the marks of the ruler above. Thus, all these rulers are not Golomb rulers.

The correct lengths of the Golomb ruler computed by the heuristic H are shown in Table 1, where for a given integer $n$, the entry $Opt(n)$ in the column $Opt$ (resp. $H(n)$ in the column $H$) is the length of an optimal Golomb ruler (resp. the length of the Golomb ruler computed by the heuristic H) featuring $n$ marks. The meaning of the other columns is straightforward. From the aforementioned table, one can observe that for $n \ge 17$, the difference between $n^2$ and lengths $H(n)$ tends to increase, contrary to the computational results reported in Table 1 of [12]. Thus, the conclusion drawn in [12] regarding the good performances of the heuristic H to compute Golomb rulers (see Sect. 5, second paragraph) is wrong.

## 5.2. Numerical efficiency of the proposed models

The computational results presented in this subsection aim to investigate the numerical efficiency of, first, the model (K), and then the models (G), (M₁), (M₂), (M₃), and (M₄) to solve the GRP. These computational results were obtained using an HPC cluster featuring 2xIntel-Xeon-5690 processors with 12 cores and 24 threads. The solution time was limited to 24 hours. All the BMILP models (G), (M₁), (M₂), (M₃), and (M₄) were solved using the solver Gurobi (ver-10.0.1) [14] with its default settings, while the solvers Baron (ver-23.3.11) [15] and Knitro (ver-13.2.1) [6] were used to solve the model (K). These solvers were all used via the AMPL interface [1, 29].
<table><caption>TABLE 2. Computational efficiency of the model ($\hat{K}$) to solve the GRP.</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Opt</th><th rowspan="2">L̂</th><th colspan="2">Size</th><th colspan="2">Knitro</th><th colspan="2">Baron</th></tr><tr><th>nv</th><th>nc</th><th>Objval</th><th>Time (m:s)</th><th>Lb</th><th>Ub</th><th>Gap (%)</th><th>Time (h:m:s)</th></tr></thead><tbody><tr><td>5</td><td>11</td><td>12</td><td>13</td><td>36</td><td>11.00</td><td>4.08</td><td>11.00</td><td>11</td><td>0.00</td><td>10.92</td></tr><tr><td>6</td><td>17</td><td>20</td><td>21</td><td>60</td><td>17.00</td><td>8.41</td><td>14.46</td><td>17</td><td>14.94</td><td>24:06:55</td></tr><tr><td>7</td><td>25</td><td>30</td><td>31</td><td>90</td><td>25.00</td><td>17.69</td><td>15.34</td><td>25</td><td>38.62</td><td>24:00:05</td></tr><tr><td>8</td><td>34</td><td>44</td><td>45</td><td>132</td><td>34.00</td><td>39.63</td><td>14.74</td><td>37</td><td>60.18</td><td>24:00:06</td></tr><tr><td>9</td><td>44</td><td>65</td><td>66</td><td>195</td><td>45.00</td><td>1:10</td><td>15.47</td><td>49</td><td>68.44</td><td>24:00:07</td></tr><tr><td>10</td><td>55</td><td>80</td><td>81</td><td>240</td><td>62.00</td><td>2:09</td><td>17.48</td><td>63</td><td>72.26</td><td>24:00:02</td></tr><tr><td>11</td><td>72</td><td>96</td><td>97</td><td>288</td><td>78.00</td><td>3:45</td><td>18.55</td><td>79</td><td>76.52</td><td>24:00:03</td></tr><tr><td>12</td><td>85</td><td>122</td><td>123</td><td>366</td><td>94.00</td><td>8:03</td><td>20.06</td><td>106</td><td>81.08</td><td>24:00:02</td></tr><tr><td>13</td><td>106</td><td>147</td><td>148</td><td>441</td><td>113.00</td><td>13:32</td><td>21.12</td><td>123</td><td>82.83</td><td>24:00:01</td></tr><tr><td>14</td><td>127</td><td>181</td><td>182</td><td>543</td><td>133.00</td><td>28:12</td><td>22.09</td><td>147</td><td>84.97</td><td>24:00:09</td></tr></tbody></table>

Firstly, in [12], the authors advocated that to solve the GRP, it is more promising to solve the continuous relaxation ($\hat{K}$) than solving the model ($K$) (see Sect. 5, first paragraph). This is rather counterintuitive because the nonlinear model ($\hat{K}$) is non-convex. As an argument, they showed computational results using the solver Knitro with a particular setting (multi-start enabled with 5000 random points).

In Table 2, we reproduced the computational results obtained after solving the non-convex model ($\hat{K}$) using the two solvers Knitro (with the same setting used in [12]) and Baron (with its default settings). For the Knitro solver, we reported the solution time in seconds (column Time) and the objective value (column Objval). For the Baron solver, we reported the lower bounds (column Lb), the upper bounds (column Ub), the relative gap (column Gap) between the upper and lower bounds, and the solution time in a human-readable format (column Time). The meaning of the other columns is as follows: the columns n, Opt, L̂ are respectively the number of marks, the length of an optimal Golomb rulers, and the used upper bound to the length of an optimal Golomb ruler. The content of the two columns nv and nc are respectively the number of variables and constraints of the model ($\hat{K}$).

The solver Knitro, as observed in [12], solves the model ($\hat{K}$) quickly. However, it returns only feasible solutions, as indicated in the column Objval. This is not surprising because Knitro guarantees a global optimal solution only if the model is convex, which is not the case for the model ($\hat{K}$). In contrast to the Knitro solver, the Baron solver guarantees a global optimal solution of the model ($\hat{K}$). It is notable that the relative gap after 24 hours (time limit) of computational efforts is at least 70% for instances with a number of marks $n \ge 10$. As we will demonstrate latter, better performances can be obtained using BMILP models to solve the GRP, contrary to what is suggested in [12] (see Sect. 5, first paragraph).

Secondly, let us compare the relative performance of the models (G), (M₁), (M₂), and (M₃) to solve the GRP. The results of our computational experiments are compiled in Table 3, where for each instance, we reported the number of marks (column n), the length of an optimal Golomb ruler (column Opt), and the upper bound to the length of an optimal Golomb ruler used (column L̂). For each model, we report its size: number of binary and continuous variables (columns nbv and ncv, respectively); total number of variables and constraints (columns nv and nc, respectively); the value of the best bound (column Best bnd.); the value of the best incumbent found (column Best sol.); the relative gap computed as $1 - \frac{\text{Best bnd.}}{\text{Best sol.}}$ (column Gap); the solution time (column Time); and the number of explored nodes in the branch-and-bound tree (column Nbr. nodes).

From Table 3, one can observe that the model (M₁) outperforms the other three models if one considers the number of optimal Golomb rulers found (the number of optimal Golomb rulers found by the models (M₁), (G), (M₂), and (M₃) are 8, 7, 6, 6, respectively), the values of the best lower bounds (except for the ruler with 13 marks for which the lower bound computed by (G) is better), or the running time (except for the ruler with 11 marks
<table><caption>TABLE 3. Computational performance of the models G, M₁, M₂, and M₃ to solve the GRP.</caption><thead><tr><th rowspan="3">n</th><th rowspan="3">Opt.</th><th rowspan="3">L̃</th><th colspan="10">Model G</th><th colspan="10">Model M₁</th></tr><tr><th colspan="4">Size of the model</th><th rowspan="2">Best bnd.</th><th rowspan="2">Best sol.</th><th rowspan="2">Gap (%)</th><th rowspan="2">Time (h:m:s)</th><th rowspan="2">Nbr. Nodes</th><th colspan="4">Size of the model</th><th rowspan="2">Best bnd.</th><th rowspan="2">Best sol.</th><th rowspan="2">Gap (%)</th><th rowspan="2">Time (h:m:s)</th><th rowspan="2">Nbr. Nodes</th></tr><tr><th>nbv</th><th>ncv</th><th>nv</th><th>nc</th><th>nbv</th><th>ncv</th><th>nv</th><th>nc</th></tr></thead><tbody><tr><td>5</td><td>11</td><td>12</td><td>12</td><td>67</td><td>79</td><td>222</td><td>11.00</td><td>11</td><td>0.00</td><td>0.25</td><td>1</td><td>12</td><td>79</td><td>91</td><td>258</td><td>11.00</td><td>11</td><td>0.00</td><td>0.28</td><td>1</td></tr><tr><td>6</td><td>17</td><td>20</td><td>20</td><td>191</td><td>211</td><td>610</td><td>17.00</td><td>17</td><td>0.00</td><td>0.37</td><td>1</td><td>20</td><td>211</td><td>231</td><td>670</td><td>17.00</td><td>17</td><td>0.00</td><td>0.26</td><td>1</td></tr><tr><td>7</td><td>25</td><td>30</td><td>30</td><td>436</td><td>466</td><td>1365</td><td>25.00</td><td>24</td><td>0.00</td><td>1.9</td><td>193</td><td>30</td><td>466</td><td>496</td><td>1455</td><td>25.00</td><td>25</td><td>0.00</td><td>2.46</td><td>1</td></tr><tr><td>8</td><td>34</td><td>44</td><td>44</td><td>947</td><td>991</td><td>2926</td><td>34.00</td><td>34</td><td>0.00</td><td>9.31</td><td>1893</td><td>44</td><td>991</td><td>1035</td><td>3058</td><td>34.00</td><td>34</td><td>0.00</td><td>16.4</td><td>2277</td></tr><tr><td>9</td><td>44</td><td>65</td><td>65</td><td>2081</td><td>2146</td><td>6370</td><td>44.00</td><td>44</td><td>0.00</td><td>1.03</td><td>12481</td><td>65</td><td>2146</td><td>2211</td><td>6565</td><td>44.00</td><td>43</td><td>0.00</td><td>1.15</td><td>9555</td></tr><tr><td>10</td><td>55</td><td>80</td><td>80</td><td>3161</td><td>3241</td><td>9640</td><td>55.00</td><td>55</td><td>0.00</td><td>12.24</td><td>35994</td><td>80</td><td>3241</td><td>3321</td><td>9880</td><td>55.00</td><td>55</td><td>0.00</td><td>7.46</td><td>35817</td></tr><tr><td>11</td><td>72</td><td>96</td><td>96</td><td>4561</td><td>4657</td><td>13872</td><td>72.00</td><td>72</td><td>0.00</td><td>1:39:34</td><td>1593120</td><td>96</td><td>4657</td><td>4753</td><td>14160</td><td>72.00</td><td>72</td><td>0.00</td><td>3:32:15</td><td>1241720</td></tr><tr><td>12</td><td>85</td><td>122</td><td>122</td><td>7382</td><td>7504</td><td>22387</td><td>76.00</td><td>94</td><td>19.15</td><td>limit</td><td>18006203</td><td>122</td><td>7504</td><td>7626</td><td>22753</td><td>85.00</td><td>85</td><td>0.00</td><td>15:24:35</td><td>4815450</td></tr><tr><td>13</td><td>106</td><td>147</td><td>147</td><td>10732</td><td>10879</td><td>32487</td><td>94.00</td><td>115</td><td>18.26</td><td>limit</td><td>14230945</td><td>147</td><td>10879</td><td>11026</td><td>32928</td><td>71.00</td><td>117</td><td>39.32</td><td>limit</td><td>485739</td></tr><tr><td>14</td><td>127</td><td>181</td><td>181</td><td>16291</td><td>16472</td><td>49232</td><td>75.32</td><td>140</td><td>46.20</td><td>limit</td><td>987556</td><td>181</td><td>16472</td><td>16653</td><td>49775</td><td>84.00</td><td>143</td><td>41.26</td><td>limit</td><td>757324</td></tr><tr><th colspan="16">Model M₂</th><th colspan="16">Model M₃</th></tr><tr><th rowspan="3">n</th><th rowspan="3">Opt.</th><th rowspan="3">L̃</th><th colspan="4">Size of the model</th><th rowspan="2">Best bnd.</th><th rowspan="2">Best sol.</th><th rowspan="2">Gap (%)</th><th rowspan="2">Time (h:m:s)</th><th rowspan="2">Nbr. Nodes</th><th colspan="4">Size of the model</th><th rowspan="2">Best bnd.</th><th rowspan="2">Best sol.</th><th rowspan="2">Gap (%)</th><th rowspan="2">Time (h:m:s)</th><th rowspan="2">Nbr. Nodes</th></tr><tr><th>nbv</th><th>ncv</th><th>nv</th><th>nc</th><th>nbv</th><th>ncv</th><th>nv</th><th>nc</th></tr><tr><td>5</td><td>11</td><td>12</td><td>12</td><td>145</td><td>157</td><td>588</td><td>11.00</td><td>11</td><td>0.00</td><td>0.34</td><td>1</td><td>12</td><td>145</td><td>157</td><td>600</td><td>11.00</td><td>11</td><td>0.00</td><td>0.31</td><td>1</td></tr><tr><td>6</td><td>17</td><td>20</td><td>20</td><td>401</td><td>421</td><td>1620</td><td>17.00</td><td>17</td><td>0.00</td><td>0.7</td><td>1</td><td>20</td><td>401</td><td>421</td><td>1640</td><td>17.00</td><td>17</td><td>0.00</td><td>0.78</td><td>1</td></tr><tr><td>7</td><td>25</td><td>30</td><td>30</td><td>901</td><td>931</td><td>3630</td><td>25.00</td><td>25</td><td>0.00</td><td>4.55</td><td>1</td><td>30</td><td>901</td><td>931</td><td>3660</td><td>25.00</td><td>25</td><td>0.00</td><td>8.55</td><td>221</td></tr><tr><td>8</td><td>34</td><td>44</td><td>44</td><td>1937</td><td>1981</td><td>7788</td><td>34.00</td><td>34</td><td>0.00</td><td>35.12</td><td>2031</td><td>44</td><td>1937</td><td>1981</td><td>7832</td><td>34.00</td><td>34</td><td>0.00</td><td>23.95</td><td>1988</td></tr><tr><td>9</td><td>44</td><td>65</td><td>65</td><td>4226</td><td>4291</td><td>16965</td><td>44.00</td><td>44</td><td>0.00</td><td>3:21</td><td>12244</td><td>65</td><td>4226</td><td>4291</td><td>17030</td><td>44.00</td><td>43</td><td>0.00</td><td>2:45</td><td>4239480</td></tr><tr><td>10</td><td>55</td><td>80</td><td>80</td><td>6401</td><td>6481</td><td>25680</td><td>55.00</td><td>55</td><td>0.00</td><td>42:53</td><td>35195100</td><td>80</td><td>6401</td><td>6481</td><td>25760</td><td>55.00</td><td>55</td><td>0.00</td><td>44:13</td><td>2840990</td></tr><tr><td>11</td><td>72</td><td>96</td><td>96</td><td>9217</td><td>9313</td><td>36960</td><td>71.00</td><td>74</td><td>4.05</td><td>limit</td><td>439260</td><td>96</td><td>9217</td><td>9313</td><td>37056</td><td>65.00</td><td>72</td><td>9.72</td><td>limit</td><td>241217</td></tr><tr><td>12</td><td>85</td><td>122</td><td>122</td><td>14885</td><td>15007</td><td>59658</td><td>63.99</td><td>95</td><td>32.64</td><td>limit</td><td>186046</td><td>122</td><td>14885</td><td>15007</td><td>59780</td><td>64.31</td><td>95</td><td>32.31</td><td>limit</td><td>131492</td></tr><tr><td>13</td><td>106</td><td>147</td><td>147</td><td>21610</td><td>21757</td><td>86583</td><td>61.56</td><td>122</td><td>49.54</td><td>limit</td><td>70359</td><td>147</td><td>21610</td><td>21757</td><td>86730</td><td>67.45</td><td>123</td><td>45.16</td><td>limit</td><td>49950</td></tr><tr><td>14</td><td>127</td><td>181</td><td>181</td><td>32762</td><td>32943</td><td>131225</td><td>52.75</td><td>153</td><td>65.52</td><td>limit</td><td>18043</td><td>181</td><td>32762</td><td>32943</td><td>131406</td><td>47.07</td><td>147</td><td>67.98</td><td>limit</td><td>26898</td></tr></tbody></table>

for which the running time to compute the optimal Golomb ruler by the model (G) is approximately half the running time of the model (M₁)).

When examining specific pairs of models, first, one can notice that the two models (K) and (M₁) perform rather similarly on rulers featuring a number of marks between 5 and 11. For the other rulers, the model (M₁) performs better than the model (K). Indeed, an optimal Golomb ruler with 12 marks is found in less than 16 hours using the model (M₁), while the relative gap of the feasible Golomb ruler found using the model (K) after 24 hours of computational efforts is 19.15%. For the ruler with 13 marks, the relative gap obtained using the model (K) is better than the one obtained using the model (M₁). However, a slightly better relative gap using the model (M₁) is obtained for the ruler with 14 marks. Second, the performances of the two models (M₂) and (M₃) are rather similar. Optimal Golomb rulers are obtained for the GRP with a number of marks between 5 and 10. For rulers with a number of marks between 11 and 14, the relative gaps are slightly the same.

Regarding the number of nodes explored during the branch-and-bound algorithm, the model (K) consistently exhibits the highest counts across almost all instances. In contrast, the number of nodes explored using the model (M₁) surpasses those of models (M₂) and (M₃). Comparing the number of nodes explored by the latter two models is more complex. However, the reduced count of explored nodes in models (M₂) and (M₃) compared to (K) and (M₁) can be attributed to the size (number of variables and constraints) of their continuous relaxations. This indicates that solving the continuous relaxation at each node of the branch-and-bound algorithm is more time-consuming.

Based on the aforementioned analysis, it appears that the model (M₁) exhibits superior performance in computing optimal Golomb rulers with a number of marks ranging from 5 to 14.

At this point of the discussion, one may wonder about the efficiency of the model (M₁) to solve instances with a number of marks $n \ge 15$. Moreover, one may ask about using a rank 2 partial Sherali-Adams relaxation.

In Table 4, we present computational results showing the performances of the two models, (M₁) and (M₄), in computing optimal Golomb rulers when the number of marks $n$ ranges from 13 to 18. The computation time was limited to 10 days.

One can observe that computing optimal Golomb rulers for instances featuring a number of marks $n$ between 13 and 18 is time-consuming. Even after 10 days of computational efforts, the relative gap remains high for instances with 14 marks or more.
<table><caption>TABLE 4. Computational performance of the models $M_1$ and $M_4$.</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Opt.</th><th rowspan="2">L̂</th><th colspan="4">Size of the model</th><th rowspan="2">Best bnd.</th><th rowspan="2">Best sol.</th><th rowspan="2">Gap (%)</th><th rowspan="2">Time (h:m:s)</th><th rowspan="2">Nbr. Nodes</th></tr><tr><th>nbv</th><th>ncv</th><th>nv</th><th>nc</th></tr></thead><tbody><tr><td colspan="12" style="text-align: left; font-weight: bold;">Model M<sub>1</sub></td></tr><tr><td>13</td><td>106</td><td>147</td><td>147</td><td>10879</td><td>11026</td><td>32928</td><td>98.00</td><td>109</td><td>10.09</td><td>240:00:01</td><td>21738900</td></tr><tr><td>14</td><td>127</td><td>181</td><td>181</td><td>16472</td><td>16653</td><td>49775</td><td>99.00</td><td>138</td><td>28.26</td><td>240:00:10</td><td>23501800</td></tr><tr><td>15</td><td>151</td><td>203</td><td>203</td><td>20707</td><td>20910</td><td>62524</td><td>93.52</td><td>170</td><td>44.99</td><td>240:00:04</td><td>2368570</td></tr><tr><td>16</td><td>177</td><td>251</td><td>251</td><td>31627</td><td>31878</td><td>95380</td><td>100.00</td><td>204</td><td>50.98</td><td>240:00:03</td><td>696569</td></tr><tr><td>17</td><td>199</td><td>289</td><td>289</td><td>41906</td><td>42195</td><td>126293</td><td>78.39</td><td>242</td><td>67.61</td><td>240:00:05</td><td>550219</td></tr><tr><td>18</td><td>216</td><td>360</td><td>360</td><td>64981</td><td>65341</td><td>195660</td><td>52.64</td><td>287</td><td>81.72</td><td>240:00:04</td><td>45491</td></tr><tr><td colspan="12" style="text-align: left; font-weight: bold;">Model M<sub>4</sub></td></tr><tr><td>13</td><td>106</td><td>147</td><td>147</td><td>21610</td><td>21757</td><td>86583</td><td>74.00</td><td>119</td><td>37.82</td><td>240:00:03</td><td>1898050</td></tr><tr><td>14</td><td>127</td><td>181</td><td>181</td><td>32762</td><td>32943</td><td>131225</td><td>69.50</td><td>148</td><td>53.04</td><td>240:00:05</td><td>1162260</td></tr><tr><td>15</td><td>151</td><td>203</td><td>203</td><td>41210</td><td>41413</td><td>165039</td><td>83.00</td><td>175</td><td>52.84</td><td>240:00:04</td><td>286779</td></tr><tr><td>16</td><td>177</td><td>251</td><td>251</td><td>63002</td><td>63253</td><td>252255</td><td>62.24</td><td>209</td><td>70.22</td><td>240:00:05</td><td>45</td></tr><tr><td>17</td><td>199</td><td>289</td><td>289</td><td>83522</td><td>83811</td><td>334373</td><td>80.22</td><td>256</td><td>68.67</td><td>240:00:06</td><td>38518</td></tr><tr><td>18</td><td>216</td><td>360</td><td>360</td><td>129601</td><td>129961</td><td>518760</td><td>85.54</td><td>293</td><td>70.81</td><td>240:00:09</td><td>47880</td></tr></tbody></table>

Additionally, the results obtained using the model ($M_1$) are competitive with those obtained by the model ($M_4$). The model ($M_1$) finds Golomb rulers with better lengths compared to those found by the model ($M_4$). Also, except for the two last rulers, the values of the lower bounds computed by the model ($M_1$) are better than those computed by the model ($M_4$). Regarding the number of explored nodes during the branch-and-bound algorithm, the model ($M_1$) explores more nodes than the model ($M_4$), because the latter features a continuous relaxation that is stronger but time-consuming to solve.

To gain a better understanding of the time necessary to compute Golomb rulers using the models ($M_1$) and ($M_4$), we fitted the values of the relative gap for rulers with $n \in \{16, 17, 18\}$ using the model:

$$g_n(t) = 1 - \frac{1}{1 + \alpha_n t^{-\beta_n}}, \quad (33)$$

where $t$ is the time variable in days.

The values of the parameters $\alpha_n$ and $\beta_n$ are estimated based on the relative gaps recorded in Table 5. These relative gaps are those recorded after each day of computational effort during the 10 days. The estimated values of the parameters $\alpha_n$ and $\beta_n$ are given in the last two rows.

In Table 6, we reported the estimated time necessary to compute (with the same resources) Golomb rulers with a number of marks $n \in \{16, 17, 18\}$ and featuring a relative gap at most the value indicated in the first column. For instance, using the model ($M_1$), almost 8.5 years are necessary to obtain a Golomb ruler with 16 marks featuring a relative gap of at most 10%. One can observe that the estimated time increases drastically with the number of marks and the desired value of the relative gap. Computing Golomb rulers with 18 marks and a relative gap of at most 50% is out of reach using the model ($M_1$). In contrast, there is a better hope using the model ($M_4$), with at most 2 years to compute a Golomb ruler with a relative gap of at most 50%.

## 6. CONCLUSION

In this work, we proposed a straightforward proof of the conjecture stated in [12] regarding the optimal solutions of the model ($K$). Moreover, concerning the greedy heuristic proposed in [12] to compute Golomb rulers, we provided its correct outputs and corrected the erroneous facts and conclusions presented in [12].

As a second contribution, starting from the observation that the proposed model ($K$) is the continuous relaxation of the model ($K$), derived from the model ($G$) using the well-known RLT technique, we explored the computational efficiency of four models, all obtained by partial Sherali-Adams reformulation-linearization
<table><caption>TABLE 5. Values of the relative gaps recorded each day of the computational experiment and the estimated values of the parameters $\alpha_n$ and $\beta_n$.</caption><thead><tr><th rowspan="3">Day</th><th colspan="6">Instances</th></tr><tr><th colspan="3">Solved using M<sub>1</sub></th><th colspan="3">Solved using M<sub>4</sub></th></tr><tr><th>16</th><th>17</th><th>18</th><th>16</th><th>17</th><th>18</th></tr></thead><tbody><tr><td>1</td><td>0.798</td><td>0.804</td><td>0.822</td><td>0.761</td><td>0.786</td><td>0.788</td></tr><tr><td>2</td><td>0.542</td><td>0.803</td><td>0.822</td><td>0.735</td><td>0.708</td><td>0.775</td></tr><tr><td>3</td><td>0.536</td><td>0.773</td><td>0.822</td><td>0.722</td><td>0.707</td><td>0.737</td></tr><tr><td>4</td><td>0.529</td><td>0.692</td><td>0.822</td><td>0.702</td><td>0.698</td><td>0.731</td></tr><tr><td>5</td><td>0.524</td><td>0.684</td><td>0.822</td><td>0.702</td><td>0.696</td><td>0.724</td></tr><tr><td>6</td><td>0.523</td><td>0.680</td><td>0.821</td><td>0.702</td><td>0.687</td><td>0.723</td></tr><tr><td>7</td><td>0.522</td><td>0.679</td><td>0.821</td><td>0.702</td><td>0.687</td><td>0.710</td></tr><tr><td>8</td><td>0.522</td><td>0.678</td><td>0.821</td><td>0.702</td><td>0.687</td><td>0.708</td></tr><tr><td>9</td><td>0.522</td><td>0.677</td><td>0.820</td><td>0.702</td><td>0.687</td><td>0.708</td></tr><tr><td>10</td><td>0.510</td><td>0.676</td><td>0.817</td><td>0.702</td><td>0.687</td><td>0.708</td></tr><tr><td>α<sub>n</sub></td><td>2.16449</td><td>4.34312</td><td>4.652</td><td>3.01332</td><td>3.08277</td><td>3.68457</td></tr><tr><td>β<sub>n</sub></td><td>0.369887</td><td>0.355974</td><td>0.0093652</td><td>0.126109</td><td>0.173105</td><td>0.198012</td></tr></tbody></table>

<table><caption>TABLE 6. Estimated solution time in years using the models (M<sub>1</sub>) and (M<sub>4</sub>) to compute Golomb rulers with number of marks $n \in \{16, 17, 18\}$.</caption><thead><tr><th rowspan="3">Targeted gap (%)</th><th colspan="3">Number of marks</th></tr><tr><th>16</th><th>17</th><th>18</th></tr></thead><tbody><tr><th colspan="4">Model M<sub>1</sub></th></tr><tr><td>50</td><td>0.022098</td><td>0.169597</td><td>5.33463 &times; 10<sup>68</sup></td></tr><tr><td>25</td><td>0.430789</td><td>3.71317</td><td>4.713 &times; 10<sup>119</sup></td></tr><tr><td>10</td><td>8.398</td><td>81.2966</td><td>4.1638 &times; 10<sup>170</sup></td></tr><tr><td>5</td><td>63.3142</td><td>663.266</td><td>1.86307 &times; 10<sup>205</sup></td></tr><tr><th colspan="4">Model M<sub>4</sub></th></tr><tr><td>50</td><td>17.2329</td><td>1.8291</td><td>1.98642</td></tr><tr><td>25</td><td>104652</td><td>1043.5</td><td>510.067</td></tr><tr><td>10</td><td>6.35531 &times; 10<sup>8</sup></td><td>595312</td><td>130973</td></tr><tr><td>5</td><td>2.37895 &times; 10<sup>11</sup></td><td>4.4606 &times; 10<sup>7</sup></td><td>5.70199 &times; 10<sup>6</sup></td></tr></tbody></table>

technique. The computational results we provided indicate, among other things, that using BMILP models is more efficient than non-convex models, for obvious reasons. Also, they indicate that computing optimal Golomb rulers when $n \ge 13$ is time-consuming. This is not surprising if one recalls that the optimal Golomb Ruler with 28 marks was obtained after approximately 8.5 years of computational time. Perhaps an equivalent or greater amount of time is required to compute optimal Golomb rulers using Reformulation-Linearization-based models.

ACKNOWLEDGEMENTS

We are grateful to the referees for their careful reading and insightful, precise comments.
REFERENCES

[1] AMPL Optimization Inc, AMPL. https://AMPL.com (2023).

[2] W.C. Babcock, Intermodulation interference in radio systems frequency of occurrence and control by channel selection. *Bell Syst. Tech. J.* **32** (1953) 63–73.

[3] E. Balas, S. Ceria and G. Cornuéjols, A lift-and-project cutting plane algorithm for mixed 0-1 programs. *Math. Program.* **58** (1993) 295–324.

[4] S. Basu, R. Pollack and M.-F. Roy, Algorithms in Real Algebraic Geometry. Springer Berlin Heidelberg (2006).

[5] G. Bloom and S. Golomb, Applications of numbered undirected graphs. *Proc. IEEE* **65** (1977) 562–570.

[6] R.H. Byrd, J. Nocedal and R.A. Waltz, Knitro: An Integrated Package for Nonlinear Optimization. (2006) 35–59.

[7] D. Cox, J. Little and D. O’Shea, Using Algebraic Geometry, 2nd edition. Springer (2004).

[8] A. Dimitromanolakis, *Analysis of the golomb ruler and the sidon set problems, and determination of large, near-optimal golomb rulers*. Master's thesis, Department of Electronic and Computer Engineering, Technical University of Crete (2002).

[9] I. Dotú and P. Van Hentenryck, A simple hybrid evolutionary algorithm for finding golomb rulers. In *Vol. 3 2005 IEEE Congress on Evolutionary Computation*. IEEE (2005) 2018–2023.

[10] K. Drakakis, A review of the available construction methods for golomb rulers. *Adv. Math. Commun.* **3** (2009) 235–250.

[11] K. Drakakis, R. Gow and L. O'Carroll, On some properties of costas arrays generated via finite fields. In: *2006 40th Annual Conference on Information Sciences and Systems*. IEEE (2006) 801–805.

[12] P. Duxbury, C. Lavor and L.L. de Salles-Neto, A conjecture on a continuous optimization model for the golomb ruler problem. *RAIRO:RO* **55** (2021) 2241–2246.

[13] P. Galinier, A Constraint-Based Approach to the Golomb Ruler Problem. Université de Montréal, Centre de recherche sur les transports (2003).

[14] Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual. https://www.gurobi.com (2023).

[15] A. Khajavirad and N.V. Sahinidis, A hybrid lp/nlp paradigm for global optimization relaxations. *Math. Program. Comput.* **10** (2018) 383–421.

[16] B. Kocuk and W.-J. van Hoeve, A Computational Comparison of Optimization Methods for the Golomb Ruler Problem. (2019) 409–425.

[17] J.B. Lasserre, An Explicit Exact sdp Relaxation for Nonlinear 0-1 Programs. (2001) 293–303.

[18] T. Liu and C. Luo, The proof of a conjecture for a continuous golomb ruler model. DOI: https://doi.org/10.20944/preprints202211.0027.v2 (2022).

[19] R. Lorentzen and R. Nilsen, Application of linear programming to the optimal difference triangle set problem. *IEEE Trans. Inf. Theory* **37** (1991) 1486–1488.

[20] L. Lovász and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization. *SIAM J. Optim.* **1** (1991) 166–190.

[21] G.P. McCormick, Computability of global solutions to factorable nonconvex programs: part i - convex underestimating problems. *Math. Program.* **10** (1976) 147–175.

[22] C. Meyer and B. Jaumard, Equivalence of some lp-based lower bounds for the golomb ruler problem. *Discrete Appl. Math.* **154** (2006) 120–144.

[23] C. Meyer and P.A. Papakonstantinou, On the complexity of constructing golomb rulers. *Discrete Appl. Math.* **157** (2009) 738–748.

[24] M. Minoux and H. Ouzia, DRL*: A hierarchy of strong block-decomposable linear relaxations for 0–1 mips. *Discrete Appl. Math.* **158** (2010) 2031–2048.

[25] L. Monique, A comparison of the sherali-adams, lovász-schrijver, and lasserre relaxations for 0-1 programming. *Math. Oper. Res.* **28** (2003) 470–496.

[26] C.A.M. Ojeda, D.F.D. Urbano and C.A.T. Solarte, Near-optimal g-golomb rulers. *IEEE Access* **9** (2021) 65482–65489.

[27] H. Ouzia, Two new reformulation convexification based hierarchies for 0–1 mips. *Adv. Oper. Res.* (2015) (2015) 1–13.

[28] S. Prestwich, Trading completeness for scalability: Hybrid search for cliques and rulers. In: *Proceedings of the Third International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems*. (2001) 159–174.
[29] D.M.G. Robert Fourer and B.W. Kernighan, A modeling language for mathematical programming. *Manag. Sci.* **36** (1990) 519–554.

[30] J. Robinson and A. Bernstein, A class of binary recurrent codes with limited error propagation. *IEEE Trans. Inf. Theory* **13** (1967) 106–113.

[31] J. Shearer, Some new optimum golomb rulers. *IEEE Trans. Inf. Theory* **36** (1990) 183–184.

[32] H.D. Sherali and W.P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. *SIAM J. Discrete Math.* **3** (1990) 411–430.

[33] H.D. Sherali and W.P. Adams, A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. *Discrete Appl. Math.* **52** (1994) 83–106.

[34] M.R. Slusky and W.-J. van Hoeve, A Lagrangian Relaxation for Golomb Rulers. (2013) 251–267.

[35] B.M. Smith, K. Stergiou and T. Walsh, Using auxiliary variables and implied constraints to model non-binary problems. In: *Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence*. AAAI Press (2000) 182–187.

[36] S.W. Soliday, A. Homaifar and G.L. Lebby, Genetic algorithm approach to the search for golomb rulers. In: *ICGA*. (1995) 528–535.

<figure><img src="image_2.png" /></figure>

Please help to maintain this journal in open access!

This journal is currently published in open access under the **Subscribe to Open model (S2O)**. We are thankful to our subscribers and supporters for making it possible to publish this journal in open access in the current year, free of charge for authors and readers.

Check with your library that it subscribes to the journal, or consider making a personal donation to the S2O programme by contacting subscribers@edpsciences.org.

More information, including a list of supporters and financial transparency reports, is available at https://edpsciences.org/en/subscribe-to-open-s2o.