| proposed by | Holger Hoos hoos@cs.ubc.ca |
These problems appear to be hard for local search methods.
Stochastic Local Search - Methods, Models, Applications (PhD thesis, TU Darmstadt, 1998) shows that the order 12 problem (which encodes into just 265 variables and 5666 clauses) causes great difficulties even for the very best local search methods for SAT.
Complete methods using global constraints like the all-different and cycle constraints have little difficulty finding single solutions. Finding all solutions appears to remain a challenge, and may be a good test bed for symmetry methods. One analysis of symmetry in this problem (including a previously unnoticed symmetry) is in Gent, McDonald and Smith's paper in the proceedings of SymCon03.
A Note on CSPLIB prob007 by Simonis and Beldiceanu shows that CHIP, using global constraints, can find a single solution without search.
In musical composition, we usually might want to find more than one solution (if it exists); furthermore, the very regular interval structure of the single solutions found by Simonis and Beldiceanu makes them potentially less interesting than other, more irregular solutions. The context of the composition may also add additional constraints on the series.
A subsequent note by Puget and Regin show that all solutions can be found with reasonable efficiency.
Gent, McDonald and Smith have shown, in a paper in the proceedings of SymCon03, that a reformulation of the problem yields all solutions 50 times faster than previous techniques.