hal-00654307, version 1
Régions intérieures et linéarisations par intervalles en optimisation globale
JPFC 2011 - Septièmes Journées Francophones de Programmation par Contraintes (2011) 299-306
Résumé : Les communautés d'analyse par intervalles et de pro- grammation (logique) par contraintes ont exploité les intervalles pour leur capacité à représenter des ensembles infi nis de solutions dans les systèmes de contraintes continus. En particulier, les boîtes ou régions intérieures permettent de représenter des sous-ensembles de l'espace de recherche dans lesquels tout point est solution. Notre première contribution est l'utilisation d'algorithmes récents et nouveaux d'extraction de régions intérieures dans la phase d'amelioration du majorant (faisable) en optimisation globale sous contraintes. La relaxation linéaire est également un ingrédient majeur, utilisé notamment pour minorer la fonction objectif. Nous avons adapté la taylorisation sur intervalles convexe - relaxation linéaire proposée par Lin et Stadtherr - pour produire des approximations polyhédrales fiables intérieure et extérieure de l'ensemble solution ainsi qu'une linéarisation de la fonction objectif. Enfi n, d'autres ingrédients originaux font partie de notre optimiseur, comme un algorithme de propagation de contraintes sur intervalles exploitant la monotonie des fonctions. Nous proposons au finnal un nouveau schéma fiable d'optimisation globale continue sous contraintes. Une implantation est disponible en tant qu'extension de l'outil Ibex (bibliothèque libre en C++ de résolution par intervalles). En termes de performances, notre stratégie dépasse de manière signi cative les meilleurs optimiseurs globaux fiables.
- 1 :
- Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
- 2 :
- INRIA – Ecole des Ponts ParisTech
- 3 :
- Universidad Técnica Federico Santa María (UTFSM)
- 4 :
- Université Paris-Est Marne-la-Vallée (UPEMLV) – ESIEE – Ecole des Ponts ParisTech – Fédération de Recherche Bézout – CNRS : UMR8049
- 5 :
- CSTB – Ecole des Ponts ParisTech – Université Paris-Est Créteil Val-de-Marne (UPEC)
- 6 :
- CNRS : UMR6241 – Université de Nantes – École Nationale Supérieure des Mines - Nantes
- 7 :
- INRIA – École Nationale Supérieure des Mines - Nantes – Université de Nantes – CNRS : UMR6241
- Domaine : Informatique/Intelligence artificielle
- hal-00654307, version 1
- http://hal-enpc.archives-ouvertes.fr/hal-00654307
- oai:hal-enpc.archives-ouvertes.fr:hal-00654307
- Contributeur :
- Soumis le : Mercredi 21 Décembre 2011, 15:42:45
- Dernière modification le : Jeudi 1 Mars 2012, 12:03:21




Documents associés
Exporter