Solving weighted CSP by maintaining arc consistency

DOI10.1016/j.artint.2004.05.004zbMath1086.68592OpenAlexW2011617423MaRDI QIDQ814626

Javier Larrosa, Thomas Schiex

Publication date: 7 February 2006

Published in: Artificial Intelligence (Search for Journal in Brave)

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

zbMATH Keywords

Soft constraintsConstraint satisfactionLocal consistencyWeighted CSP

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 ⋮ Semiring induced valuation algebras: exact and approximate local computation algorithms ⋮ Redundant modeling in permutation weighted constraint satisfaction problems ⋮ Interleaving solving and elicitation of constraint satisfaction problems based on expected cost ⋮ Super-reparametrizations of weighted CSPs: properties and optimization perspective ⋮ A Max-SAT Inference-Based Pre-processing for Max-Clique ⋮ Maximum feasibility estimation ⋮ Triangle-based consistencies for cost function networks ⋮ A Cost-Based Model and Algorithms for Interleaving Solving and Elicitation of CSPs ⋮ Cost Propagation – Numerical Propagation for Optimization Problems ⋮ Computational protein design as an optimization problem ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ Comparing action descriptions based on semantic preferences ⋮ Solving weighted CSPs with meta-constraints by reformulation into satisfiability modulo theories ⋮ DARN! A weighted constraint solver for RNA motif localization ⋮ Global propagation of side constraints for solving over-constrained problems ⋮ \(N\)-level modulo-based CNF encodings of pseudo-Boolean constraints for MaxSAT ⋮ Inference with constrained hidden Markov models in PRISM ⋮ Probabilistic optimal solution assessment for DCOPs ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Soft Constraints Processing over Divisible Residuated Lattices ⋮ Solving finite domain constraint hierarchies by local consistency and tree search ⋮ Clique inference process for solving Max-CSP ⋮ AND/OR branch-and-bound search for combinatorial optimization in graphical models ⋮ Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction ⋮ Ultra-weak solutions and consistency enforcement in minimax weighted constraint satisfaction ⋮ Iterative and core-guided maxsat solving: a survey and assessment

Cites Work

• Arc consistency for soft constraints
• Consistency in networks of relations
• Maintaining reversible DAC for Max-CSP
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Radio link frequency assignment
• Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
• Scene Labeling by Relaxation Operations
• Semiring-based constraint satisfaction and optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item