Generalised arc consistency for the AllDifferent constraint: an empirical survey

DOI10.1016/J.ARTINT.2008.10.006MaRDI QIDQ2389692zbMATH OpenOpenAlexFDO

Authors Ian Miguel, Ian P. Gent, Peter W. Nightingale

Publication date 17 July 2009

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.artint.2008.10.006

zbMATH Keywords

constraint programmingglobal constraintsconstraint satisfaction problemsalldifferent

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A parallel algorithm for GAC filtering of the Alldifferent constraint
• When is it worthwhile to propagate a constraint? A probabilistic analysis of \textsc{AllDifferent}
• Generalizing AllDifferent: The SomeDifferent Constraint
• Recent Advances in Constraints
• Principles and Practice of Constraint Programming – CP 2004

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 2084734 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Balance and filtering in structured satisfiable problems. (Preliminary report)
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Depth-First Search and Linear Graph Algorithms
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Persistency in maximum cardinality bipartite matchings
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004
• Recent Advances in Constraints
• Recent Advances in Constraints
• The Problem of Compatible Representatives
• Watched Literals for Constraint Propagation in Minion

Cited in

(18)

• When is it worthwhile to propagate a constraint? A probabilistic analysis of \textsc{AllDifferent}
• The \textsc{AllDifferent} constraint with precedences
• The extended global cardinality constraint: an empirical survey
• Arc-Consistency Checking with Bilevel Constraints: An Optimization
• Propagation engine prototyping with a domain specific language
• Redundant disequalities in the Latin square problem
• Modeling the Costas array problem in QUBO for quantum annealing
• Comparing QUBO models for quantum annealing: integer encodings for permutation problems
• Beyond Finite Domains: The All Different and Global Cardinality Constraints
• scientific article; zbMATH DE number 2088040 (Why is no real title available?)
• A parallel algorithm for GAC filtering of the Alldifferent constraint
• Implementing logical connectives in constraint programming
• Extending SMT solvers with support for finite domain \texttt{alldifferent} constraint
• scientific article; zbMATH DE number 2080326 (Why is no real title available?)
• A generic arc-consistency algorithm and its specializations
• Generalizing AllDifferent: The SomeDifferent Constraint
• scientific article; zbMATH DE number 2080315 (Why is no real title available?)
• Domain k-Wise Consistency Made as Simple as Generalized Arc Consistency

Describes a project that uses

Uses Software

• Hopcroft-Karp
• MINION
• CSPLib

This page was built for publication: Generalised arc consistency for the AllDifferent constraint: an empirical survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2389692)