Computer Science – Artificial Intelligence
Scientific paper
2010-08-24
Artificial Intelligence 175(9-10) 1555-1569 (2011)
Computer Science
Artificial Intelligence
A full version of a CP'10 paper, 26 pages
Scientific paper
10.1016/j.artint.2011.02.003
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.
Cooper Martin C.
Zivny Stanislav
No associations
LandOfFree
Hybrid tractability of soft constraint problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Hybrid tractability of soft constraint problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid tractability of soft constraint problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-394091