| proposed by | Peter van Beek vanbeek@cs.ualberta.ca |
Optimal Golomb rulers have been found for rulers with up to 21 marks and non-optimal rulers are known for rulers with up to 150 marks, all found using specialized programs.
Tables showing the current best Golomb rulers can be found at:
My experience with these problems suggests that even quite small problems (fewer than fifteen marks) are very difficult for complete methods such as backtracking search. The difficulty lies in both proving optimality and in finding a solution (since the problems have either a unique solution or just a handful of solutions).
Jean-Francois Puget reports finding a solution for a 12 mark rule with ILOG Solver after 2042000 backtracks. The total number of backtracks including the proof of optimality is 3143316. A 13 mark ruler was found after 156478 seconds on a sparc 20 and more than 26969000 backtracks. Finding the solution and proving optimality took 53108352 backtracks and 330643 seconds on a sparc 20 (almost 4 days).
More recently, promising results are given for up to 13 tick rulers using the Koalog constraint toolkit.