Partial reformulation-linearization based optimization models for the Golomb ruler problem - Sorbonne Université
Journal Articles RAIRO - Operations Research Year : 2024

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.
Fichier principal
Vignette du fichier
ro240128.pdf (528.37 Ko) Télécharger le fichier
Origin Publication funded by an institution
Licence

Dates and versions

hal-04681114 , version 1 (29-08-2024)

Licence

Identifiers

Cite

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⟩
34 View
6 Download

Altmetric

Share

More