Golomb Ruler

This is an example showing how to solve the Golomb ruler problem using numberjack.


The Golomb Ruler problem is the task of putting n marks on a ruler of length m such that the distance between any two pairs of marks is distinct. See prob006 in the CSPLib.


from Numberjack import *

def model_golomb_ruler(nbMarks):
    rulerSize = 2**(nbMarks-1)

    marks = VarArray(nbMarks,rulerSize)
    model = Model(
        Minimise( marks[nbMarks-1] ), #objective function

        [marks[i-1] < marks[i] for i in range(1,nbMarks)],
        AllDiff([marks[i] - marks[j] for i in range(1, nbMarks) for j in range(i)]),
        marks[0] == 0 # symmetry breaking
    return (marks,model)

def solve_golomb_ruler(param):
    (marks,model) = model_golomb_ruler(param['marks'])
    solver = model.load(param['solver'])
    print marks
    print 'Nodes:', solver.getNodes(), ' Time:', solver.getTime()