Propagating Soft Table Constraints

Autor: Christophe Lecoutre, Nicolas Paris, Sébastien Tabary, Olivier Roussel
Přispěvatelé: Chevallier, Francois, Centre de Recherche en Informatique de Lens (CRIL), Université d'Artois (UA)-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2012
Předmět:
Zdroj: Lecture Notes in Computer Science ISBN: 9783642335570
CP
18th International Conference on Principles and Practice of Constraint Programming (CP'12)
18th International Conference on Principles and Practice of Constraint Programming (CP'12), 2012, Québec, Canada. pp.390-405
DOI: 10.1007/978-3-642-33558-7_30
Popis: International audience; 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.
Databáze: OpenAIRE
Externí odkaz: