Apports et Potentiels de la Programmation par Contraintes en Optimisation Globale sous Contraintes

Résumé : Dans cet expos e, nous présentons quelques apports et potentiels de la programmation par contraintes pour l'optimisation globale sous contraintes dans le domaine continu. Nous nous intéressons donc uniquement a des problèmes d'optimisation globale dont l'objectif est de minimiser une fonction objectif en respectant un ensemble d'inégalités et d' égalités. Formellement, ces problèmes sont dénis de la manière suivante : minimize f(x) subject to gi(x) = 0; i 2 f1; ::; kg hj(x) 0; j 2 f1; ::;mg (1) avec x 2 x, f : IRn ! IR gi : IRn ! IR et hj : IRn ! IR Les fonctions f, gi et hj peuvent être non-linéaires mais elles doivent être continues et diférentiables sur un vecteur x d'intervalles de IR. La principale dificulté de ces problèmes vient du fait qu'il existe de trés nombreux minimum locaux mais que peu d'entre eux sont des minimum globaux. Nous montrons d'abord que la PPC (Programmation par Contraintes) offre un cadre élégant et rigoureux pour la résolution de ces problèmes ; par cadre rigoureux nous entendons un cadre qui permet de garantir la correction des résultats. Cette correction, qui exige des calculs avec des arrondis conservatifs, repose sur l'utilisation de l'arithmétique sur les intervalles. Nous montrons ensuite que l'utilisation des techniques de filtrage et de réfutation permet de mettre en œuvre de manière élégante et rigoureuse des heuristiques comme l'OBR, qui sont non-rigoureuses, mais qui améliorent significativement les performances. Nous montrons aussi que l'utilisation de contraintes globales rigoureuses offre une alternative efficace aux méthodes locales pour la réduction de la borne supérieure et pour la recherche de points de départ bien adaptés a la méthode de Newton. Enfin nous discutons de quelques problèmes ouverts, en particulier des difficultés de la PPC a résoudre efficacement des problèmes de grande taille.
Type de document :
Documents associés à des manifestations scientifiques -- Hal-inria+
JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France
Liste complète des métadonnées

https://hal.inria.fr/hal-00742227
Contributeur : Michel Rueher <>
Soumis le : mardi 16 octobre 2012 - 11:33:18
Dernière modification le : jeudi 9 avril 2015 - 01:07:04
Document(s) archivé(s) le : jeudi 17 janvier 2013 - 11:35:09

Fichier

rueher.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00742227, version 1

Collections

Citation

Michel Rueher. Apports et Potentiels de la Programmation par Contraintes en Optimisation Globale sous Contraintes. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. <hal-00742227>

Partager

Métriques

Consultations de
la notice

119

Téléchargements du document

19