Carnegie Mellon University
A Lagrangian Relaxation for Golomb Rulers.pdf.pdf' (181.19 kB)
Download file

A Lagrangian Relaxation for Golomb Rulers

Download (181.19 kB)
journal contribution
posted on 1998-02-01, 00:00 authored by Marla R. Slusky, Willem-Jan Van HoeveWillem-Jan Van Hoeve

The Golomb Ruler Problem asks to position n integer marks on a ruler such that all pairwise distances between the marks are distinct and the ruler has minimum total length. It is a very challenging combinatorial problem, and provably optimal rulers are only known for n up to 26. Lower bounds can be obtained using Linear Programming formulations, but these are computationally expensive for large n. In this paper, we propose a new method for finding lower bounds based on a Lagrangian relaxation. We present a combinatorial algorithm that finds good bounds quickly without the use of a Linear Programming solver. This allows us to embed our algorithm into a constraint programming search procedure. We compare our relaxation with other lower bounds from the literature, both formally and experimentally. We also show that our relaxation can reduce the constraint programming search tree considerably.




Usage metrics