A generic arc-consistency algorithm and its specializations
From MaRDI portal
Publication:1199922
DOI10.1016/0004-3702(92)90020-XzbMath0763.68059MaRDI QIDQ1199922
Yves Deville, Choh Man Teng, Pascal Van Hentenryck
Publication date: 17 January 1993
Published in: Artificial Intelligence (Search for Journal in Brave)
constraint satisfaction problemsconstraint logic programmingfinite domainsarc-consistency algorithms
Related Items (48)
Fast parallel constraint satisfaction ⋮ Partition search for non-binary constraint satisfaction ⋮ Model-based inference in CHARME. ⋮ Range and Roots: two common patterns for specifying and propagating counting and occurrence constraints ⋮ Image interpretation with a conceptual graph: labeling over-segmented images and detection of unexpected objects ⋮ From chaotic iteration to constraint propagation ⋮ On the speed of constraint propagation and the time complexity of arc consistency testing ⋮ No more ``Partial and ``Full Looking Ahead ⋮ Path consistency in clp(FD) ⋮ Local and global relational consistency ⋮ An algebraic characterization of tractable constraints ⋮ Constraint satisfaction problem with bilevel constraint: Application to interpretation of over-segmented images ⋮ The essence of constraint propagation ⋮ Bounds of graph parameters for global constraints ⋮ On the arc consistency problem ⋮ Unnamed Item ⋮ Domain consistency with forbidden values ⋮ The complexity of soft constraint satisfaction ⋮ An optimal coarse-grained arc consistency algorithm ⋮ A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems ⋮ Interval propagation to reason about sets: Definition and implementation of a practical language ⋮ New model and heuristics for safety stock placement in general acyclic supply chain networks ⋮ On the Number of Rule Applications in Constraint Programs ⋮ A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem ⋮ A distributed optimization method for the geographically distributed data centres problem ⋮ A new tractable class of constraint satisfaction problems ⋮ Tractable constraints on ordered domains ⋮ Tractable constraints on ordered domains ⋮ Constraint satisfaction problems: Algorithms and applications ⋮ The job shop scheduling problem: Conventional and new solution techniques ⋮ Arc-Consistency Checking with Bilevel Constraints: An Optimization ⋮ Inequality-sum: a global constraint capturing the objective function ⋮ Constraints, consistency and closure ⋮ Using constraint metaknowledge to reduce arc consistency computation ⋮ A branch and bound algorithm for agile earth observation satellite scheduling ⋮ Timetable planning using the constraint-based reasoning ⋮ Using recipe classes for supporting detailed planning in food industry: A case study ⋮ From MDD to BDD and arc consistency ⋮ Constraint propagation techniques for the disjunctive scheduling problem ⋮ Efficient Algorithms for Functional Constraints ⋮ Decomposable constraints ⋮ STR3: a path-optimal filtering algorithm for table constraints ⋮ Propagation engine prototyping with a domain specific language ⋮ Optimal and efficient filtering algorithms for table constraints ⋮ Fast parallel constraint satisfaction ⋮ Backjump-based backtracking for constraint satisfaction problems ⋮ Characterising tractable constraints ⋮ An efficient algorithm for a class of constraint satisfaction problems
Uses Software
Cites Work
- Unnamed Item
- Network-based heuristics for constraint-satisfaction problems
- Solving a cutting-stock problem with the constraint logic programming language CHIP
- Consistency in networks of relations
- A language and a program for stating and solving combinatorial problems
- A microkernel architecture for constraint programming
- Networks of constraints: Fundamental properties and applications to picture processing
- On the parallel complexity of discrete relaxation in constraint satisfaction networks
- Amortized Computational Complexity
- Synthesizing constraint expressions
- Solving large combinatorial problems in logic programming
This page was built for publication: A generic arc-consistency algorithm and its specializations
