Corrigé de l'exercice 1 : Retour de monnaie

On définit le CSP (X,D,C) tel que Dans cette modélisation, nous avons utilisé une contrainte arithmétique linéaire sur les entiers. Cette contrainte est globale dans le sens où elle fait intervenir toutes les variables du problème. Une autre modélisation possible consisterait à définir le domaine des variables par l'ensemble des entiers positifs ou nuls, et d'ajouter en contraintes que la quantité de pièces retournées doit être inférieure ou égale au nombre de pièces en réserve (pour chaque type de pièce différent).

Pour exprimer le fait que l'on souhaite que le distributeur rende le moins de pièces possibles, on pourrait ajouter à ce CSP une fonction "objectif" à minimiser

f(X) = XE2 + XE1 + XC50 + XC20 + XC10

Dans ce cas, résoudre le CSP revient à chercher une affectation de X complète et consistante qui minimise f(X).