Skip to Main content Skip to Navigation
Conference papers

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é.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151233
Contributor : Sylvain Soliman <>
Submitted on : Friday, June 1, 2007 - 6:50:10 PM
Last modification on : Thursday, May 28, 2020 - 9:22:09 AM
Document(s) archivé(s) le : Thursday, April 8, 2010 - 6:45:26 PM

File

45.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00151233⟩

Share

Metrics

Record views

275

Files downloads

706