zbMATH — the first resource for mathematics

A Lagrangian relaxation for Golomb rulers. (English) Zbl 1382.68233
Gomes, Carla (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 10th international conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38170-6/pbk). Lecture Notes in Computer Science 7874, 251-267 (2013).
Summary: 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.
For the entire collection see [Zbl 1263.68017].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Full Text: DOI