Hybrid tractability of constraint satisfaction problems with global constraintsReport as inadecuate

Hybrid tractability of constraint satisfaction problems with global constraints - Download this document for free, or read online. Document in PDF available to download.

Reference: Evgenij Thorstensen, (2013). Hybrid tractability of constraint satisfaction problems with global constraints. DPhil. University of Oxford.Citable link to this page:


Hybrid tractability of constraint satisfaction problems with global constraints

Abstract: A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or intensionally, whether by an equation, propositional logic formula, or other means. Intensionally represented constraints, known as global constraints, are a powerful modelling technique, and many modern CSP solvers provide them. We give examples to show how problems that deal with product configuration can be modelled with such constraints, and how this approach relates to other modelling formalisms.The complexity of CSPs with extensionally represented constraints is well understood, and there are several known techniques that can be used to identify tractable classes of such problems. For CSPs with global constraints, however, many of these techniques fail, and far fewer tractable classes are known. In order to remedy this state of affairs, we undertake a systematic review of research into the tractability of CSPs. In particular, we look at CSPs with extensionally represented constraints in order to understand why many of the techniques that give tractable classes for this case fail for CSPs with global constraints. The above investigation leads to two discoveries.First, many restrictions on how the constraints of a CSP interact implicitly rely on a property of extensionally represented constraints to guarantee tractability. We identify this property as being a bound on the number of solutions in key parts of the instance, and find classes of global constraints that also possess this property. For such classes, we show that many known tractability results apply. Furthermore, global constraints allow us to treat entire CSP instances as constraints. We combine this observation with the above result, and obtain new tractable classes of CSPs by dividing a CSP into smaller CSPs drawn from known tractable classes.Second, for CSPs that simply do not possess the above property, we look at how the constraints of an instance overlap, and how assignments to the overlapping parts extend to the rest of the problem. We show that assignments that extend in the same way can be identified. Combined with a new structural restriction, this observation leads to a second set of tractable classes.We conclude with a summary, as well as some observations about potential for future work in this area.

Digital Origin:Born digital Type of Award:DPhil Level of Award:Doctoral Awarding Institution: University of Oxford


Prof Peter JeavonsMore by this contributor



Prof Georg GottlobMore by this contributor


 Bibliographic Details

Issue Date: 2013

Copyright Date: 2013 Identifiers

Urn: uuid:05707b54-69e3-40eb-97e7-63b1a178c701 Item Description

Type: thesis;

Language: en Keywords: configuration global constraints tractability complexity hypergraph constraint programmingSubjects: Combinatorics Computer science (mathematics) Artificial Intelligence Applications and algorithms Tiny URL: ora:7270


Author: Dr Evgenij Thorstensen - institutionUniversity of Oxford facultyMathematical,Physical and Life Sciences Division - Computer Scien

Source: https://ora.ox.ac.uk/objects/uuid:05707b54-69e3-40eb-97e7-63b1a178c701


Related documents