Bridging the Gap between Different Consistencies

Roland Yap

School of Computing

National University of Singapore

Abstract

Filtering constraint networks to reduce search space is one of the main cornerstones of Constraint Programming and among them (Generalized) Arc Consistency has been the most prevalent. While stronger consistencies have also been the subject of considerable attention, in practice, higher consistency algorithms do not match GAC. For this reason, GAC algorithms/implementations continues to advance at a steady pace and has become the popular choice of consistency for filtering algorithms. In this project, we build on the success of GAC by proposing ways to transform a constraint network into another such that enforcing GAC on the latter is equivalent to enforcing a stronger consistency on the former. Thus, this has the advantage that existing solvers and GAC algorithms can be used with minimal effort.

We call the transformed constraint network, the factor encoding (FE) or the factor decomposition encoding (FDE). The key idea of the new encodings is to factor out commonly shared variables from constraints' scopes, form new variables, then re-attach them back to the constraints where they come from or decompose the constraints into smaller ones with fewer variables. Experiments show that these methods are superior to the specialized algorithms and other techniques when it comes to full pair-wise consistency (FPWC).

Keywords: Local consistencies, higher-order consistency, CSP transformation and decomposition, table constraints

People

Roland Yap

Xia Wei

Publications

  • "Decomposition of the Factor Encoding for CSPs" [pdf]
    by Chavalit Likitvivatanavong, Wei Xia and Roland H. C. Yap
    The 24th International Joint Conference on Artificial Intelligence (IJCAI'15)

  • "Higher-Order Consistencies through GAC on Factor Variables" [pdf]
    by Chavalit Likitvivatanavong, Wei Xia and Roland H. C. Yap
    The 24th International Joint Conference on Artificial Intelligence (CP'14)

    • Experimental results

    Description: ddeg-dom on random benchmarksDescription: ddeg-dom on random benchmarks

    Description: ddeg-dom on random benchmarksDescription: ddeg-dom on random benchmarks

    Figure 1: Runtime distribution for unstructured instances.

    Description: ddeg-dom on random benchmarksDescription: ddeg-dom on random benchmarks

    Description: ddeg-dom on random benchmarksDescription: ddeg-dom on random benchmarks

    Figure 2: Runtime distribution for structured instances.

    Benchmarks: available from Christophe Lecoutre's webpage: here