LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Dago, Pierre (1997)
Languages: French
Types: Article
Subjects: CSP, VCSP, Optimisation, Ordonnancement, Satellites, 000, Optimization, Scheduling
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.
  • No references.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article