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

Michel Rueher 1
1 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe CEP
Laboratoire I3S - MDSC - Modèles Discrets pour les Systèmes Complexes
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.
Document type :
Documents associated with scientific events
Liste complète des métadonnées

https://hal.inria.fr/hal-00742227
Contributor : Michel Rueher <>
Submitted on : Tuesday, October 16, 2012 - 11:33:18 AM
Last modification on : Monday, November 5, 2018 - 3:48:02 PM
Document(s) archivé(s) le : Thursday, January 17, 2013 - 11:35:09 AM

File

rueher.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

174

Files downloads

25