Skip to Main content Skip to Navigation
Conference papers

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

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151234
Contributor : Sylvain Soliman <>
Submitted on : Friday, June 1, 2007 - 6:52:54 PM
Last modification on : Saturday, February 15, 2020 - 1:56:13 AM
Long-term archiving on: : Thursday, April 8, 2010 - 6:45:37 PM

File

28.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

152

Files downloads

186