Repository navigation
🧩 Constraint Solving POTD:Problem of the Day: Golomb Rulers (Optimal Sidon Sets) #79506
Closed
Replies: 2 comments
|
This discussion has been marked as outdated by Constraint Solving — Problem of the Day. A newer discussion is available at Discussion #79797. |
0 replies
|
Smoke run 44900023928 stopped by here: tests mostly pass, a couple fail. 🤖🎉 Warning Firewall blocked 1 domainThe following domain was blocked by the firewall during workflow execution:
To allow these domains, add them to the network:
allowed:
- defaults
- "host.docker.internal"See Network Configuration for more information.
|
0 replies
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
Problem Statement
A Golomb ruler with
nmarks is a set of integers0 = a_1 < a_2 < ... < a_nin which every pairwise differencea_j - a_i(fori < j) is distinct. The goal is to minimize the lengtha_n. Put simply: placentick marks on a ruler so that no distance can be measured in two different ways.Small instance:
[0, 1, 4, 6]is a 4-mark ruler. Its differences are 1, 4, 6, 3, 5, 2, all distinct, and its length of 6 is optimal.na_1 ... a_nthat minimizea_nOptimal lengths for
n = 2to8are 1, 3, 6, 11, 17, 25, 34 ([OEIS A003022]((oeis.org/redacted) Optima are proven only for smalln; the distributed.net OGR project has verified up to 28 marks.Why It Matters
Modeling Approaches
1. Constraint programming: integer marks with
alldifferentm_1 ... m_nin{0..L}, withm_1 = 0,m_n = L, andm_i < m_(i+1)alldifferent({ m_j - m_i | i < j })Lthis is a satisfaction problem. SearchLupward from the trivial boundn(n-1)/2.nvariables) and close to the statement, but difference expressions propagate weakly.2. Binary position model: MIP or SAT
x_pin{0,1}forpin{0..L}(mark at positionp), withx_0 = x_L = 1andsum_p x_p = nd, addz_(p,d) >= x_p + x_(p+d) - 1and requiresum_p z_(p,d) <= 1O(L^2)auxiliary variables, and its LP relaxation is weak because fractional marks slip past most distance constraints.Example Model (MiniZinc)
Key Techniques
Uof used distances. A candidate positionxis legal only if the new differences{x - a_i}avoidUand do not repeat each other. With bitmasks this is a few word operations, so search can test millions of candidates quickly. Many record-hunting searches rely on this pattern.m_2 - m_1 <= m_n - m_(n-1)keeps one orientation and halves the search space.L >= n(n-1)/2is loose, since optimal lengths grow roughly liken^2. Singer and Bose constructions from finite projective and affine planes yield near-optimal rulers for largen. Using such a length as an upper bound guarantees feasibility and caps how far the upward search must go.Challenge Corner
alldifferentmodel with the binary model onn = 7. Which proves infeasibility faster, and why?M. Which constraints change, and what does the change make easier?References
All reactions