Formulating Constraint Satisfaction Problems on Part-Whole Relations: The Case of Automatic Musical Harmonization

We address the issue of formulating constraint problems in structured domains, and focus on the exploitation of part-whole relations. We describe and compare two approaches in problem formulation in this context; one using a flattened repre-sentation of domains, and one using a naturally occurring part-whole relation. We show that the second approach may be much more efficient than the flattened representation, thanks to a judicious partitioning of the constraint problem in several phases. We give a theoretical measure of the respective complexities of the two approaches, and illustrate our result on a difficult and naturally structured musical problem: automatic harmonization of melodies. The resulting system outperforms previous attempts on the same problem. Finally, we propose other applications of our approach for generating automatically musical programs