Régions intérieures et linéarisations par intervalles en optimisation globale

Gilles Trombettoni 1, 2 Ignacio Araya 3 Bertrand Neveu 1, 4 Gilles Chabert 5, 6
1 COPRIN - Constraints solving, optimization and robust interval analysis
CRISAM - Inria Sophia Antipolis - Méditerranée , ENPC - École des Ponts ParisTech
6 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
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.
Type de document :
Communication dans un congrès
Association Française de Programmation par Contraintes. JPFC 2011, Jun 2011, Lyon, France. pp.299-306, 2011
Liste complète des métadonnées


https://hal-enpc.archives-ouvertes.fr/hal-00654307
Contributeur : Gilles Trombettoni <>
Soumis le : mercredi 21 décembre 2011 - 15:42:45
Dernière modification le : mercredi 29 juillet 2015 - 01:24:05
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 16:20:17

Fichier

299.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00654307, version 1

Citation

Gilles Trombettoni, Ignacio Araya, Bertrand Neveu, Gilles Chabert. Régions intérieures et linéarisations par intervalles en optimisation globale. Association Française de Programmation par Contraintes. JPFC 2011, Jun 2011, Lyon, France. pp.299-306, 2011. <hal-00654307>

Partager

Métriques

Consultations de
la notice

451

Téléchargements du document

531