| < Précédent | Suivant > |
|---|
Publication year: 2011
Source: Artificial Intelligence, Volume 175, Issues 9-10, June 2011, Pages 1555-1569
Martin C. Cooper, Stanislav Živný
The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligen it provides a common framework for many theoretical problems as well as for many real-life applications. Valued 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 valued constraint problems; that is, properties which guarantee tractability of the given valued 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 valued constraints in the instance (such as submodularity). We present several novel hybrid classes of valued constraint problems in which all unary constraints are allowed, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and theSoftAllDiffconstraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.
Source: Artificial Intelligence, Volume 175, Issues 9-10, June 2011, Pages 1555-1569
Martin C. Cooper, Stanislav Živný
The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligen it provides a common framework for many theoretical problems as well as for many real-life applications. Valued 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 valued constraint problems; that is, properties which guarantee tractability of the given valued 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 valued constraints in the instance (such as submodularity). We present several novel hybrid classes of valued constraint problems in which all unary constraints are allowed, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and theSoftAllDiffconstraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.
