Modelling the Golomb Ruler Problem
Research Report 1999.12, School of Computer Studies, University of Leeds,
June 1999.
Barbara M Smith, Kostas Stergiou and Toby Walsh
Abstract
The Golomb ruler problem has been proposed as a challenging constraint
satisfaction problem. We consider a large number of different models of
this problem, both binary and non-binary. The problem can be modelled
using quaternary constraints, but in practice using a set of auxiliary
variables and ternary constraints gives better results. A binary
encoding of the problem gives a smaller search tree, but is impractical
because it takes far longer to run. We compare variable ordering
heuristics and consider the use of implied constraints to improve
propagation. We believe that more case studies such as this are
essential to reduce the skill currently required for successful
modelling.
Back to "Barbara Smith
- Papers on Constraint Programming"