prob007: all-interval series

proposed by Holger Hoos
hoos@cs.ubc.ca

References

The musical all-interval series have a certain prominence in serial composition; they can be traced back to Alban Berg and have been extensively studied and used by Ernst Krenek, for example, in his orchestral piece op.170, ``Quaestio temporis'' (A Question of Time).

Hoos describes the generalization of the problem and its formulation as a CSP and SAT problem in his PhD thesis:

Stochastic Local Search - Methods, Models, Applications (PhD thesis, TU Darmstadt, 1998)

Simonis and Beldiceanu have shown that, using global constraints, CHIP can find one solution without search.

A note on CSPLIB prob007, by Simonis and Beldiceanu.

A followup note by Puget and Regin shows that all solutions can be found in ILOG's Solver 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.