Bornes inférieures à base d'inégalités valides pour les WCSP

Résumé : La plus part des algorithmes de résolution efficace de WCSP se basent sur la notion de consistance d'arc utilisée pour transformer un WCSP en un WCSP équivalent et plus facile à résoudre. Dans ce but, plusieurs formes de consistance d'arc ont été proposées : AC* \cite{Schiex.00}, DAC* \cite{Larrosa.03}, FDAC* \cite{Larrosa.03},EDAC* \cite{deGivry.05}. Récemment, une consistance d'arc optimale (OSAC pour Optimal Soft Arc Consistency) \cite{Cooper.07} a été proposée. Elle se base sur la résolution d'un Programme Linéaire. Son inconvénient réside dans le fait qu'elle nécessite beaucoup de temps de calcul. Cet inconvénient est dû à la taille du programme linéaire résolu. Nous proposons une nouvelle technique de transformation d'un WCSP en un WCSP équivalent. Cette technique se base sur la modélisation du WCSP sous forme d'un programme linéaire plus facile à résoudre que le calcul de OSAC.
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 [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00151234
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:52:54
Dernière modification le : jeudi 11 janvier 2018 - 06:17:31
Document(s) archivé(s) le : jeudi 8 avril 2010 - 18:45:37

Fichier

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

Identifiants

  • HAL Id : inria-00151234, version 1

Collections

Citation

Mohand Ou Idir Khemmoudj, Hachemi Bennaceur. Bornes inférieures à base d'inégalités valides pour les WCSP. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, Rocquencourt / France, 2007, JFPC07. 〈inria-00151234〉

Partager

Métriques

Consultations de la notice

126

Téléchargements de fichiers

87