Hybrid tractability of valued constraint problems

DOI10.1016/J.ARTINT.2011.02.003MaRDI QIDQ646503zbMATH OpenOpenAlexFDO

Authors M. C. Cooper, S. Zivny

Publication date 17 November 2011

Published in Artificial Intelligence (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1322793 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1134987 (Why is no real title available?)
• scientific article; zbMATH DE number 2084723 (Why is no real title available?)
• A dichotomy theorem for the general minimum cost homomorphism problem
• A new class of binary CSPs for which arc-consistency is a decision procedure
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Classifying the Complexity of Constraints Using Finite Algebras
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Cost-based arc consistency for global cardinality constraints
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Generalizing AllDifferent: The SomeDifferent Constraint
• Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
• Graphical models, exponential families, and variational inference
• Independent sets of maximum weight in apple-free graphs
• Network-based heuristics for constraint-satisfaction problems
• On global warming: Flow-based soft global constraints
• On the algebraic structure of combinatorial problems
• Recognizing Berge graphs
• Scheduling independent tasks to reduce mean finishing time
• Semiring-based constraint satisfaction and optimization
• Technical Note—Minimizing Average Flow Time with Parallel Machines
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of conservative valued CSPs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of satisfiability problems
• The complexity of soft constraint satisfaction
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(19)

• Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
• Tractability in constraint satisfaction problems: a survey
• On singleton arc consistency for CSPs defined by monotone patterns
• On singleton arc consistency for CSPs defined by monotone patterns
• The Broken-Triangle Property with Adjoint Values
• Binary constraint satisfaction problems defined by excluded topological minors
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• Valued constraint satisfaction problems
• A tractable class of binary VCSPs via M-convex intersection
• Tractability of explaining classifier decisions
• Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
• Hybrid tractable classes of constraint problems
• Discrete convexity in joint winner property
• Galois connections for patterns: an algebra of labelled graphs
• Effectiveness of structural restrictions for hybrid CSPs
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• The complexity of valued CSPs
• Hybrid VCSPs with crisp and valued conservative templates
• The quadratic M-convexity testing problem

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)