If there is no better value then mark V Tabu, else replace V by its better value.
Until the global cost is zero.

Written so, there is absolutely no reason why the algorithm should end. It does not when there is no solution, and even when there are solutions nothing guarantees the ending. To avoid this, one can count the iterations and stop when a maximum number is reached.

4.3 Use of this algorithm for musical CSPs

This algorithm satisfies many of our goals, mainly because the assignments are directed towards improvement of the configuratio, and it uses a notion of distance which is very natural in music. First, it deals naturally with partial solutions. The user can choose a treshold, and ask for the best local minimum reached so far to be printed, provided the global error is lower than this treshold. When there is no exact solution to the CSP, it naturally allows to get partial solutions. For the harmonization problem, the composer even directly used this possibility to compose : he collected the partial solutions, sorted them from the one with largest error to the one with lowest error, and put them in the score (remember that in this problem the canon is played repetitively). This gives a convergence toward the final texture.

The representation with costs, instead of boolean constraints, gives the possibility to put weight on the constraints, by multiplying their cost by a chosen weight. Thus, playing with the treshold, we can make a distinction between the constraints that must be satisfied and the constraints that may be (preferences). Finally, the global constraints are easily handled. Their only feature is their cost functions being constants, which is not a problem for the solver.

Finally, this algorithm has been proven to be very fast on some classical CSPs (see Codognet et al., 2002) for some benches.

The main disadvantage of this method is the translation from the constraints to cost-functions. It is straightforward for composers who work with distance or optimization, but not in the general case. To solve this, we defined a transduction grammar that we won’t describe here (see Truchet et al., 2001).

5 Conclusion

We have presented in this article some possible uses of constraint programming for musical composition and analysis, both from the modelling and the resolution sides. It shows that CSP modelling is very well suited to musical applications. We believe that contrary to complete methods, a local search algorithm fits particularly well the needs of the composers.

The future work is to design an architecture including visual definition of constraints, resolution, edition of the partial results, so that musician users can feel comfortable with CP.