# Substituabilité au voisinage pour le cadre WCSP

Abstract : WCSP is an optimization problem for which many forms of soft local (arc) consistencies such as existential directional arc consistency (EDAC) and virtual arc consistency (VAC) have been proposed these last years. In this paper, we adopt a different perspective by revisiting the well-known property of (soft) substitutability. First, we provide a clear picture of the relationships existing between soft neighborhood substitutability (SNS) and a tractable property called $pcost$ which is based on the concept of overcost of values (through the use of so-called cost pairs). We prove that under certain assumptions, $pcost$ is equivalent to SNS but weaker than SNS in the general case since we show that SNS is coNP-hard. We also show that SNS preserves the property VAC but not the property EDAC. Finally, we introduce an optimized algorithm and we show on various series of WCSP instances, the practical interest of maintaining $pcost$ together with AC*, FDAC or EDAC, during search.
Document type :
Conference papers

Cited literature [22 references]

https://hal.inria.fr/hal-00818527
Contributor : Djamel-Eddine Dehani <>
Submitted on : Monday, April 29, 2013 - 1:26:26 PM
Last modification on : Thursday, September 9, 2021 - 3:10:46 PM
Long-term archiving on: : Monday, August 19, 2013 - 9:46:33 AM

### File

subFinalJFPC2012.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00818527, version 1

### Citation

Christophe Lecoutre, Djamel-Eddine Dehani, Olivier Roussel. Substituabilité au voisinage pour le cadre WCSP. JFPC - Huitièmes Journées Francophones de Programmation par Contraintes - 2012, Apr 2013, Toulouse, France. ⟨hal-00818527⟩

Record views