Bornes inférieures à base d'inégalités valides pour les WCSP - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

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.
Fichier principal
Vignette du fichier
28.pdf (193.59 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00151234 , version 1 (01-06-2007)

Identifiants

  • HAL Id : inria-00151234 , version 1

Citer

Mohand Ou Idir 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. ⟨inria-00151234⟩
67 Consultations
94 Téléchargements

Partager

Gmail Facebook X LinkedIn More