A New Incomplete Method for CSP Inconsistency Checking

Belaid Benhamou, Mohamed Réda SaïdiAAAI 2008

Introduction

Proving that a Constraint Satisfaction Problem (CSP) has no solution—known as inconsistency—is a fundamental challenge in computer science. Traditionally, solvers fall into two categories: complete methods, which perform exhaustive searches to guarantee a proof of inconsistency at high computational cost, and incomplete methods, which use local search to find solutions quickly but typically cannot prove unsatisfiability. This paper, presented at AAAI 2008, introduces the Dominance-Coloration method to bridge this gap, addressing the long-standing goal of efficiently proving CSP inconsistency without exponential-time search.

The Dominance-Coloration Method

The core innovation of this work is the transformation of a complex CSP into a simpler, "dominating" problem. A CSP $P'$ is said to dominate $P$ if the inconsistency of $P'$ implies the inconsistency of $P$. The authors leverage the "micro-structure" of a CSP—a graph where vertices represent variable-value pairs—to build this relationship.

The Iterative Algorithm

The Dominance-Coloration algorithm follows a multi-step loop to refine the problem and search for a proof of inconsistency:

  1. Micro-structure Generation: The algorithm first constructs the micro-structure graph of the CSP.
  2. Graph Coloration: Using a heuristic like DSATUR, the algorithm finds a $k$-coloration of the micro-structure. If $k$ is less than the number of variables $n$, the problem is immediately proven inconsistent.
  3. Mapping to Alldifferent: If $k \ge n$, the algorithm constructs a new CSP, Alldiff(P, fk), where each variable must choose a unique color from the $k$ available colors.
  4. Filtering and Refinement: Generalized Arc Consistency (GAC) is applied to this Alldifferent constraint. If GAC proves the constraint is unsatisfiable, the original CSP is inconsistent. If GAC removes specific values, these are propagated back to the original CSP, and the process repeats.
The iterative process of the Dominance-Coloration method, showing the mapping between the original CSP and the derived Alldifferent problem.

This iterative approach allows the solver to progressively simplify the problem, potentially uncovering an inconsistency that was not apparent in the initial state.

Experimental Evaluation

The method was evaluated using random CSP instances with 20 variables and a domain size of 10, varying constraint density and tightness. The researchers compared Dominance-Coloration against standard Arc Consistency (AC), Path Consistency (Path), and previous coloration-based methods.

Key Results

The Dominance-Coloration method demonstrated a significantly higher detection rate for inconsistent instances compared to other incomplete methods. Notably, its performance closely matched that of complete solvers like Forward Checking (FC) in terms of identifying unsatisfiable problems.

Comparison of solver performance across varying levels of constraint tightness, highlighting the robustness of the Dominance-Coloration method in the hard phase transition region.

As shown in the performance metrics, the method remains robust in the "hard" phase transition region—the point where problems are neither trivially satisfiable nor obviously over-constrained. While previous coloration methods were only effective on very tight, over-constrained instances, this new approach maintains high detection rates across a broader spectrum of problem difficulty.

Conclusion

The Dominance-Coloration method represents a significant step forward in incomplete CSP solving. By combining graph coloring with global constraint filtering, it provides a powerful tool for proving inconsistency. Future work will focus on optimizing coloration heuristics and exploring other types of dominating constraints to further enhance the scalability and efficiency of the approach. Integration as a preprocessing step for complete solvers like MAC (Maintaining Arc Consistency) also remains a promising avenue for research.

Summary updated

BibTeX
@inproceedings{benhamou2008new,
  author = {Belaid Benhamou and Mohamed Réda Saïdi},
  title = {{A New Incomplete Method for CSP Inconsistency Checking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure