Variable and value elimination in binary constraint satisfaction via forbidden patterns
Variable or value elimination in a constraint satisfaction problem (CSP) can be used in preprocessing or during search to reduce search space size. A variable elimination rule (value elimination rule) allows the polynomial-time identification of certain variables (domain elements) whose elimination, without the introduction of extra compensatory constraints, does not affect the satisfiability of an instance. We show that there are essentially just four variable elimination rules and three value elimination rules defined by forbidding generic sub-instances, known as irreducible existential patterns, in arc-consistent CSP instances. One of the variable elimination rules is the already-known Broken Triangle Property, whereas the other three are novel. The three value elimination rules can all be seen as strict generalisations of neighbourhood substitution.
Code (0)
등록된 구현이 없습니다.
Tasks
ARCSimilar Papers 제목 키워드 기반
Efficient Algorithms for Partial Constraint Satisfaction Problems over Control-flow Graphs
In this work, we focus on the Partial Constraint Satisfaction Problem (PCSP) over control-flow graphs (CFGs) of programs. PCSP serves as a generalization of the well-known Constraint Satisfaction Problem (CSP). In the CS…
M-best solutions for a class of fuzzy constraint satisfaction problems
The article considers one of the possible generalizations of constraint satisfaction problems where relations are replaced by multivalued membership functions. In this case operations of disjunction and conjunction are r…
Solving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms
A weighted constraint satisfaction problem (WCSP) is a constraint satisfaction problem in which preferences among solutions can be expressed. Bucket elimination is a complete technique commonly used to solve this kind of…
Exploring Directional Path-Consistency for Solving Constraint Networks
Among the local consistency techniques used for solving constraint networks, path-consistency (PC) has received a great deal of attention. However, enforcing PC is computationally expensive and sometimes even unnecessary…
Scene LabelingConsistency Techniques for Flow-Based Projection-Safe Global Cost Functions in Weighted Constraint Satisfaction
Many combinatorial problems deal with preferences and violations, the goal of which is to find solutions with the minimum cost. Weighted constraint satisfaction is a framework for modeling such problems, which consists o…