Hybrid tractability of valued constraint problems

• Published in: Artificial intelligence 2011-06, Vol.175 (9), p.1555-1569
• Main Authors: Cooper, Martin C., Živný, Stanislav
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Artificial intelligence; Computational complexity; Computer science; control theory; systems; Computer simulation; Constraint optimisation; Exact sciences and technology; Expert systems; Forbidden substructures; Graphical models; Learning and adaptive systems; Mathematical models; Optimization; Scheduling; Soft constraints; Substructures; Theoretical computing; Tractability; Valued constraint satisfaction problems
• ISSN: 0004-3702; 1872-7921
• DOI: 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. 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 the SoftAllDiff constraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.