Name
Abstract | ||
|---|---|---|
WCSP is a framework that has attracted a lot of attention during the last decade. In particular, many filtering approaches have been developed on the concept of equivalence-preserving transformations (cost transfer operations), using the definition of soft local consistencies such as, for example, node consistency, arc consistency, full directional arc consistency, and existential directional arc consistency. Almost all algorithms related to these properties have been introduced for binary weighted constraint networks, and most of the conducted experiments typically include networks with binary and ternary constraints only. In this paper, we focus on extensional soft constraints (of large arity), so-called soft table constraints. We propose an algorithm to enforce a soft version of generalized arc consistency (GAC) on such constraints, by combining both the techniques of cost transfer and simple tabular reduction, the latter dynamically maintaining the list of allowed tuples in constraint tables. On various series of problem instances containing soft table constraints of large arity, we show the practical interest of our approach. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-33558-7_30 | CP |
Keywords | Field | DocType |
arc consistency,existential directional arc consistency,generalized arc consistency,node consistency,extensional soft constraint,full directional arc consistency,large arity,soft local consistency,so-called soft table constraint,soft table constraint | Mathematical optimization,Local consistency,Arity,Tuple,Computer science,Algorithm,Filter (signal processing),Ternary operation,Extensional definition,Binary number | Conference |
Citations | PageRank | References |
0 | 0.34 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christophe Lecoutre | 1 | 709 | 45.10 |
| Nicolas Paris | 2 | 4 | 1.16 |
| Olivier Roussel | 3 | 283 | 21.63 |
| Sébastien Tabary | 4 | 66 | 6.58 |