High-order consistency in valued constraint satisfaction

DOI10.1007/s10601-005-2240-3zbMath1112.68118OpenAlexW1976533903MaRDI QIDQ816687

Martin C. Cooper

Publication date: 23 February 2006

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-005-2240-3

zbMATH Keywords

soft constraintsMAX-CSPconsistency enforcingdiscrete optimisationvalued constraint satisfaction

Mathematics Subject Classification ID

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

Related Items

Tractability-preserving transformations of global cost functions ⋮ A logical approach to efficient Max-SAT solving ⋮ Modularity-based decompositions for valued CSP ⋮ Classes of submodular constraints expressible by graph cuts ⋮ Virtual pairwise consistency in cost function networks ⋮ Triangle-based consistencies for cost function networks ⋮ Computational protein design as an optimization problem ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ Mendelian error detection in complex pedigrees using weighted constraint satisfaction tech\-niques ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ Soft arc consistency revisited ⋮ A note on some collapse results of valued constraints ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction ⋮ High-order consistency in valued constraint satisfaction

Cites Work

• Unnamed Item
• Arc consistency for soft constraints
• Cyclic consistency: A local reduction operation for binary valued constraints
• High-order consistency in valued constraint satisfaction
• Network-based heuristics for constraint-satisfaction problems
• An optimal k-consistency algorithm
• Linear-time algorithms for testing the realisability of line drawings of curved objects
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
• Reduction operations in fuzzy or valued constraint satisfaction
• Nonserial dynamic programming
• Scene Labeling by Relaxation Operations