Extension d'algorithmes dans le cadre des problèmes de satisfaction de contraintes valués : application à l'ordonnancement de systèmes satellitaires

Dans cette étude, nous nous intéressons à la résolution des "Problèmes de Satisfaction de Contraintes valués" (CSP valués). Cette modélisation extrêmement simple, intuitive et riche s’adapte facilement à une grande variété de problèmes d'optimisation. De nombreux travaux ont par ailleurs fourni toute une bibliothèque d'algorithmes de résolution. Dans le cadre classique de la satisfaction des CSP, l'efficacité de ces méthodes n’est plus à démontrer et leur domaine d'application est assez bien connu. L'introduction d'une valuation des contraintes dans le modèle CSP, qui donne naissance aux CSP valués, est cependant trop récente pour que les possibilités et les limites d'efficacité soient clairement identifiées. L'ordonnancement des satellites d'observation de la Terre fait partie des CSP valués à la frontière des compétences actuelles en matière d'optimisation. Cette application est pour nous un prétexte au développement d’outils de résolution nouveaux étendant le champ des CSP valués accessibles. Notre travail est centré sur la notion de "contrainte induite", largement utilisée dans le cadre classique, et dont l'extension difficile aux CSP valués limite actuellement l'amélioration des algorithmes de recherche complets. Afin de dépasser ces difficultés, directement liées à la non idempotence de l'agrégation des valuations des contraintes, nous proposons un formalisme minimal pour les contraintes induites. Nous montrons ensuite comment il peut être mis en œuvre pour étendre l'essentiel des algorithmes développés dans le cadre classique. Enfin, l'utilité de ces nouveaux outils est illustré sur les problèmes d'ordonnancement du satellite SPOT 5. In this study, we are interested in “Valued Constraint Satisfaction Problems”(Valued CSPs) solving. This model which is extremely genuine, intuitive and rich matches easily most of optimization problems. Many works have produced a full library of solving algorithms. In the CSP framework, the efficiency of these methods is admitted and their limits well known. The adjunction of a valuation to the constraints in the CSP model that brought Valued CSPs is quite recent and the possibilities and the solving limits are not well identified. Earth observation satellite scheduling is a problem that is on the border of the optimization abilities at the present time. For us, this application is a pretense to extend the field of accessible Valued CSPs. Our work focuses on the concept of “induced constraint" that is widely used in the classical CSP framework but is hard to extend to the Valued CSP framework. So that the improvement of the complete solving tools is limited for the present. In order to overcome these difficulties, directly linked to the non idempotency of the aggregation of the constraints valuations, we propose a minimal formalism for induced constraints. Then, we show how to extend the main algorithms developped in the classical CSP framework. At last, the usefullness of these new tools is illustrated on the satellite SPOT 5 scheduling problems.