Contraintes d'optimisation pour les problèmes d'arbres couvrants sous restrictions

Résumé : Bien que des méthodes de filtrage basées sur les coûts existent depuis peu pour les problèmes d'arbres couvrants sous incertitudes \cite{Aron2002,Dooms2006}, elles ne permettent pas la prise en compte de. restrictions additionnelles. Nous présentons dans cet article une contrainte d'optimisation pour les problèmes d'arbres couvrants de poids optimal sous restrictions fondée sur les travaux de \cite{Sellmann2004}. Nous améliorons tout d'abord la contrainte d'optimisation proposée par \cite{Aron2002,Dooms2006} pour les problèmes d'arbres couvrants en mettant en évidence l'analogie entre recherche de cycles, recherche de ponts et calcul de remplaçants. Puis nous décrivons les problèmes posés par l'ajout de restrictions lors de l'utilisation de ce type d'algorithme pour proposer ensuite, grâce aux travaux de Sellmann, une nouvelle contrainte d'optimisation basée sur une relaxation Lagrangienne. Nous fournissons une première expérimentation de cette contrainte sur un problème d'arbre couvrant sous restriction de degré.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, Rocquencourt, France. 2007, JFPC07
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00151233
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:50:10
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 8 avril 2010 - 18:45:26

Fichier

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

Identifiants

  • HAL Id : inria-00151233, version 1

Citation

Jérôme Brongniart, Dhaenens Clarisse, El-Ghazali Talbi. Contraintes d'optimisation pour les problèmes d'arbres couvrants sous restrictions. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, Rocquencourt, France. 2007, JFPC07. 〈inria-00151233〉

Partager

Métriques

Consultations de la notice

227

Téléchargements de fichiers

473