Hybrid tractability of soft constraint problems

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.

A full version of a CP'10 paper, 26 pages

References in corpus (2)

• MAP Estimation, Message Passing, and Perfect Graphs
• Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms

Cited by in corpus (12)

• The complexity of finite-valued CSPs
• The complexity of conservative valued CSPs
• An Algebraic Theory of Complexity for Discrete Optimisation
• The tractability of CSP classes defined by forbidden patterns
• Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
• Binary Constraint Satisfaction Problems Defined by Excluded Topological Minors
• The quadratic M-convexity testing problem
• On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
• Discrete Convexity in Joint Winner Property
• Greedy Strategies and Larger Islands of Tractability for Conjunctive Queries and Constraint Satisfaction Problems
• A tractable class of binary VCSPs via M-convex intersection
• Point-width and Max-CSPs