Multiconsistency and Robustness with Global Constraints |
| |
Authors: | Khaled Elbassioni Irit Katriel |
| |
Affiliation: | 1. Max-Planck-Institut für Informatik, Saarbrücken, Germany 2. BRICS, University of Aarhus, ?rhus, Denmark
|
| |
Abstract: | We propose a natural generalization of arc-consistency, which we call multiconsistency: a value v in the domain of a variable x is k-multiconsistent with respect to a constraint C if there are at least k solutions to C in which x is assigned the value v. We present algorithms that determine which variable-value pairs are k-multiconsistent with respect to several well known global constraints. In addition, we show that finding super solutions is sometimes strictly harder than finding arbitrary solutions for these constraints and suggest multiconsistency as an alternative way to search for robust solutions.Supported by the Danish Research Agency (grant # 272-05-0081).Basic Research in Computer Science, funded by the Danish National Research Foundation. |
| |
Keywords: | Multi-consistency Arc-consistency Global constraints Filtering algorithms Robust solutions Alldifferent Global cardinality constraint |
本文献已被 SpringerLink 等数据库收录! |