\input zb-basic
\input zb-ioport
\iteman{io-port 05250239}
\itemau{Elbassioni, Khaled; Katriel, Irit}
\itemti{Multiconsistency and robustness with global constraints.}
\itemso{Bart\'ak, Roman (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems.; Second international conference, CPAIOR 2005, Prague, Czech Republic, May 31 -- June 1, 2005. Refereed proceedings. Berlin: Springer (ISBN 978-3-540-26152-0/pbk). Lecture Notes in Computer Science 3524, 168-182 (2005).}
\itemab
Summary: 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 strictly harder than finding arbitrary solutions and suggest multiconsistency as an alternative way to search for robust solutions.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/11493853\_14}
\end