TL;DR
This paper introduces a unified, generic framework for defining and implementing "inverse local consistency" levels in Constraint Satisfaction Problems (CSPs). This framework allows for the creation of new, highly tailored consistency levels and provides a general algorithm that can enforce them, potentially improving CSP solving efficiency.
What Problem Does This Paper Address?
Solving Constraint Satisfaction Problems (CSPs) often involves simplifying the problem by removing values or combinations of values that cannot be part of any solution. This is typically done using "local consistency enforcing" techniques. While arc consistency is widely used, more powerful levels like path consistency or k-consistency exist but are often avoided due to high computational costs (time and memory) and the need to modify constraint definitions or graphs.
The authors address the limitations of existing powerful local consistency methods by focusing on "inverse local consistency" levels. These levels, unlike traditional ones, don't remove value combinations or alter the constraint structure. They achieve simplification by identifying values that cannot be extended to form a solution within specific sub-problems. The challenge is that these inverse levels have been defined and implemented in a fragmented manner, making comparison and generalization difficult. This paper aims to unify these concepts into a single, flexible framework.
Methods
The core contribution is a generic framework for inverse local consistency. This framework is built upon the notion of viability: a value is "viable" in a sub-instance if it can be consistently extended to a solution within that sub-instance.
The framework defines an inverse local consistency level (ilc) by a function defilc. This function maps an instance P to a set of (sub-instance, set of variables) pairs whose viability must hold. This abstract definition allows for the unification of many existing inverse local consistency levels (like arc consistency, neighborhood inverse consistency, and global consistency) and the creation of new ones.
Associated with this framework is a generic algorithm for inverse local consistency enforcing. This algorithm is an extension of the AC7 algorithm for arc consistency. It uses the concept of supporting assignments (an assignment that satisfies a sub-instance) to check for value viability. If a value is found to be non-viable (i.e., lacks a supporting assignment), it's removed from the variable's domain. The algorithm employs several data structures (CL, SIL, SSL, SVL, SAL, MSA) to manage the checking process and efficiently reuse information from previous searches, particularly when dealing with sub-instances involving multiple constraints where a tree search is performed.
Datasets
Not discussed in the paper. The paper focuses on the theoretical framework and algorithmic generalization rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Unification of Inverse Local Consistency: The framework provides a single, elegant way to define and understand a wide range of inverse local consistency levels, moving away from ad-hoc definitions.
- Flexibility for Users: The
defilcfunction allows users to define custom consistency levels tailored to specific problem instances or types, offering a powerful customization tool. - Generic Algorithm: The development of a single algorithm that can enforce any defined inverse local consistency level simplifies implementation and potentially offers efficiency gains through shared logic and data structures.
- Reversal of CSP Solving Paradigm: The paper highlights how the generic algorithm can be seen as a tree search subroutine for local consistency enforcing, reversing the more common view of local consistency as a subroutine for tree search. This suggests new ways to structure CSP solvers.
- Addressing Drawbacks of Traditional Methods: By focusing on inverse consistency, the framework inherently avoids the prohibitive memory requirements and constraint graph/definition modifications associated with some traditional, more powerful consistency levels.
Key Results
The paper presents a theoretical framework and a generic algorithm. It demonstrates how existing inverse local consistency levels can be expressed within this framework and suggests how new levels can be defined. The authors state that the algorithm, when implemented, turns any instance P into a simplified, equivalent, and locally consistent instance P. The time and space complexity are generalized from AC7, being roughly O(p.dn".dn'−1) and O(p.dn".n') respectively, where p is the number of sub-problems to check, n' and n" are variable counts in sub-instances, and d is domain size.
Limitations and Future Work
- Specific Inverse Levels: The authors acknowledge that their framework does not directly include specific levels like restricted path consistency or max restricted path consistency, as their inclusion would require significant changes and potentially reduce simplicity.
- Efficiency Comparison: While a generic algorithm is presented and implemented in an interactive tool, no direct efficiency comparisons are made against specialized algorithms for specific inverse local consistency levels. The authors suggest that while genericity might introduce some overhead, a carefully implemented generic algorithm can still be efficient.
- Language for Defining Levels: The paper proposes the development of a small language to allow users to easily express custom consistency levels.
- Interactive CSP Solving: The framework is well-suited for interactive CSP solving, allowing users to define and test various levels.
- Recursive Definitions: The paper introduces recursive definitions for inverse local consistency (e.g.,
ilc1-ilc2-consistent) to incorporate more complex levels and suggests that this opens avenues for defining new, potentially powerful, consistency combinations.
Summary updated