Contrainte globale pour le problème de recouvrement d'ensemble

Sébastien Mouthuy 1 Yves Deville 1 Grégoire Dooms 1
1 Département d'informatique
Résumé : Ce papier propose une approche par Programmation par Contrainte pour résoudre le problème de recouvrement d'ensemble. Ce problème d'optimisation combinatoire est fort utile pour formuler un grand nombre d'applications concrètes (assignation d'équipages, planification de tâches et de véhicules, construction de circuits imprimés) ainsi que des problèmes de graphes (Recouvrement par noeuds, ensemble de noeuds dominants et indépendants). Le problème de recouvrement d'ensemble est NP-difficile. Ce papier propose une contrainte globale SC pour le problème de recouvrement d'ensemble et un propagateur qui utilise une borne inférieure calculée par des relaxations empruntées à la Programmation Entière. Nous présentons aussi un algorithme incrémental pour calculer cette borne qui utilise une structure de données qui peut être mise à jour très vite pour des petits changements, la rendant très bien adaptée aux arbres de recherche. Notre approche est comparée avec deux autres propagateurs basés sur la relaxation linéaire et sur une approche gloutonne.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00151182
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 17:06:24
Dernière modification le : vendredi 1 juin 2007 - 17:15:06
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 16:05:22

Fichier

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

Identifiants

  • HAL Id : inria-00151182, version 1

Collections

JFPC07

Citation

Sébastien Mouthuy, Yves Deville, Grégoire Dooms. Contrainte globale pour le problème de recouvrement d'ensemble. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151182〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

247

Téléchargements de fichiers

418

Contact


archive-ouverte@inria.fr