Hybrid tractability of valued constraint problems

DOI10.1016/J.ARTINT.2011.02.003zbMATH Open1225.68243arXiv1008.4071OpenAlexW2146944439MaRDI QIDQ646503FDOQ646503

S. Zivny, M. C. Cooper

Publication date: 17 November 2011

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

Abstract: The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems as well as for many real-life applications. Soft constraint problems are a generalisation of the CSP which allow the user to model optimisation problems. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this work, we initiate the study of hybrid tractability of soft constraint problems; that is, properties which guarantee tractability of the given soft constraint problem, but which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of soft constraints in the instance (such as submodularity). We present several novel hybrid classes of soft constraint problems, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and the SoftAllDiff constraint with arbitrary unary soft constraints. An important tool in our investigation will be the notion of forbidden substructures.

Full work available at URL: https://arxiv.org/abs/1008.4071

Recommendations

• Hybrid tractable classes of constraint problems
• The tractability of CSP classes defined by forbidden patterns
• The complexity of valued constraint satisfaction
• Hybrid VCSPs with crisp and valued conservative templates
• The complexity of valued constraint satisfaction problems

zbMATH Keywords

computational complexitygraphical modelstractabilitysoft constraintsforbidden substructuresvalued constraint satisfaction problemsconstraint optimisation

Mathematics Subject Classification ID

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

Cites Work

• Graphical Models, Exponential Families, and Variational Inference
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Title not available (Why is that?)
• Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
• The ellipsoid method and its consequences in combinatorial optimization
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Cost-based arc consistency for global cardinality constraints
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Network-based heuristics for constraint-satisfaction problems
• On the algebraic structure of combinatorial problems
• The complexity of soft constraint satisfaction
• Recognizing Berge graphs
• The complexity of conservative valued CSPs
• Technical Note—Minimizing Average Flow Time with Parallel Machines
• Scheduling independent tasks to reduce mean finishing time
• Independent Sets of Maximum Weight in Apple-Free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• On global warming: Flow-based soft global constraints
• Title not available (Why is that?)
• Semiring-based constraint satisfaction and optimization
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Title not available (Why is that?)
• Generalizing AllDifferent: The SomeDifferent Constraint
• A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
• Principles and Practice of Constraint Programming – CP 2003

Cited In (17)

• Hybrid Tractable Classes of Constraint Problems
• Tractability in constraint satisfaction problems: a survey
• On singleton arc consistency for CSPs defined by monotone patterns
• The Broken-Triangle Property with Adjoint Values
• The Complexity of Valued CSPs
• Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection.
• Binary constraint satisfaction problems defined by excluded topological minors
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• Title not available (Why is that?)
• Tractability of explaining classifier decisions
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
• Galois connections for patterns: an algebra of labelled graphs
• Discrete convexity in joint winner property
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• The quadratic M-convexity testing problem
• A Tractable Class of Binary VCSPs via M-Convex Intersection

This page was built for publication: Hybrid tractability of valued constraint problems

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