Apports et Potentiels de la Programmation par Contraintes en Optimisation Globale sous Contraintes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Document Associé À Des Manifestations Scientifiques Année : 2010

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.
Fichier principal
Vignette du fichier
rueher.pdf (1.7 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00742227 , version 1 (16-10-2012)

Identifiants

  • HAL Id : hal-00742227 , version 1

Citer

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⟩
99 Consultations
23 Téléchargements

Partager

Gmail Facebook X LinkedIn More