Constraint Network Tractability: Beyond Structure and Language
Lead Research Organisation:
University of Oxford
Department Name: Computer Science
Abstract
The Constraint Satisfaction Problem (or CSP) is a general framework for all kinds of computational problems that involve searching for a set of values that together satisfy some specified restrictions, known as constraints. Such problems are encountered in a very large range of applications, including classic problems in operations research and artificial intelligence, many forms of scheduling and planning problems, and problems in cryptography, computer vision, chemical synthesis and gene matching.
The Maximum Constraint Satisfaction Problem (or Max-CSP) is a generalisation of the CSP whose range of application is even greater: it includes many combinatorial optimisation problems that are not easily expressed in the basic CSP framework. In this problem the aim is to find an assignment of values to the variables of the problem which maximises the number of satisfied constraints.
Both the CSP and the Max-CSP are NP-hard, which means that it is unlikely that there exist efficient general algorithms that can solve all instances of such problems. Thus one can try to design heuristics which perform well on certain kinds of instances, or else one can restrict the general problem in order to obtain a more tractable problem (for example, a problem which can be solved in polynomial time). Most of our research is concerned with the second approach: we try to identify the restrictions on constraint satisfaction problems which are sufficient to ensure they can be solved efficiently.
In this project we aim to find a novel approach to defining such restrictions that is more powerful than anything that has been considered before, and allows us to identify many more kinds of tractable problems. In the past, the only kinds of tractable problems that have been considered fall into two distinct classes. In the first, the constraints are arbitrary, but they can only be applied to the variables in limited ways. In the second, the constraints fall into a restricted family of constraint types, but they can be applied to the variables in an arbitrary way. Both of these kinds of restrictions have led to interesting mathematical theories, and some important special cases which can be solved efficiently. However, we believe that it is now possible to combine these approaches and obtain a much more general theory that unifies the previous approaches, and provides a more flexible way to define the restrictions on problems.
By developing this more powerful approach we hope to be able to describe much more accurately which kinds of constraint problems can be solved efficiently, and to use this information to improve the available software tools and analytical techniques.
The Maximum Constraint Satisfaction Problem (or Max-CSP) is a generalisation of the CSP whose range of application is even greater: it includes many combinatorial optimisation problems that are not easily expressed in the basic CSP framework. In this problem the aim is to find an assignment of values to the variables of the problem which maximises the number of satisfied constraints.
Both the CSP and the Max-CSP are NP-hard, which means that it is unlikely that there exist efficient general algorithms that can solve all instances of such problems. Thus one can try to design heuristics which perform well on certain kinds of instances, or else one can restrict the general problem in order to obtain a more tractable problem (for example, a problem which can be solved in polynomial time). Most of our research is concerned with the second approach: we try to identify the restrictions on constraint satisfaction problems which are sufficient to ensure they can be solved efficiently.
In this project we aim to find a novel approach to defining such restrictions that is more powerful than anything that has been considered before, and allows us to identify many more kinds of tractable problems. In the past, the only kinds of tractable problems that have been considered fall into two distinct classes. In the first, the constraints are arbitrary, but they can only be applied to the variables in limited ways. In the second, the constraints fall into a restricted family of constraint types, but they can be applied to the variables in an arbitrary way. Both of these kinds of restrictions have led to interesting mathematical theories, and some important special cases which can be solved efficiently. However, we believe that it is now possible to combine these approaches and obtain a much more general theory that unifies the previous approaches, and provides a more flexible way to define the restrictions on problems.
By developing this more powerful approach we hope to be able to describe much more accurately which kinds of constraint problems can be solved efficiently, and to use this information to improve the available software tools and analytical techniques.
Planned Impact
In an advanced industrial society decisions have to be made constantly about the allocation of resources to achieve complex goals efficiently. These range from the planning of complex construction projects, to the allocation of energy resources, and from the deployment of personnel in large organisations to the configuration of consumer products or electronic devices. In many cases, especially in large organisations or scientific investigations, special-purpose software is being developed and deployed to try to make the appropriate decisions optimally. A new generation of software tools is emerging, based on new techniques for the solution of combinatorial optimisation problems: SAT-solvers, and general constraint solvers.
However, very little is known about when such tools can be used effectively, and when they will fail due to combinatorial explosion - where the number of potential solutions grows too rapidly to be effectively explored, even by the most efficient software tools.
Computational complexity theory can shed some light on this issue by distinguishing those problems that are inherently difficult from those which will yield to an appropriate carefully-chosen efficient algorithm. Constraint satisfaction problems provide a very clean generic framework where such theory can be developed. Considerable progress has already been made, but the results obtained so far are often too specific and too sensitive to the details of the problem formulation to be widely applicable. In this grant we will explore whether a new analytical tool, based on local patterns in problem instances, can be used to provide a much more widely applicable theory. This approach should result in many more cases that can be shown to be efficiently solvable, and hence the development of more effective tools. Many of todays information technology companies are investing heavily in constraint research and looking for new ways of understanding and tackling constraint problems. This research offers one such new approach.
As well as its practical applicability, research in this area has the potential to shed light on some fundamental issues about the nature of computation. One of the great unsolved mathematical problems listed by the Clay Institute as "Millenium Problems" is the problem of distinguishing computational problems according to their inherent difficulty, and hence establishing the limits of efficient algorithms (this is the heart of the so-called "P versus NP" problem). By developing a general theory to distinguish tractable and intractable constraint satisfaction problems we hope to develop new tools for approaching this fundamental problem.
However, very little is known about when such tools can be used effectively, and when they will fail due to combinatorial explosion - where the number of potential solutions grows too rapidly to be effectively explored, even by the most efficient software tools.
Computational complexity theory can shed some light on this issue by distinguishing those problems that are inherently difficult from those which will yield to an appropriate carefully-chosen efficient algorithm. Constraint satisfaction problems provide a very clean generic framework where such theory can be developed. Considerable progress has already been made, but the results obtained so far are often too specific and too sensitive to the details of the problem formulation to be widely applicable. In this grant we will explore whether a new analytical tool, based on local patterns in problem instances, can be used to provide a much more widely applicable theory. This approach should result in many more cases that can be shown to be efficiently solvable, and hence the development of more effective tools. Many of todays information technology companies are investing heavily in constraint research and looking for new ways of understanding and tackling constraint problems. This research offers one such new approach.
As well as its practical applicability, research in this area has the potential to shed light on some fundamental issues about the nature of computation. One of the great unsolved mathematical problems listed by the Clay Institute as "Millenium Problems" is the problem of distinguishing computational problems according to their inherent difficulty, and hence establishing the limits of efficient algorithms (this is the heart of the so-called "P versus NP" problem). By developing a general theory to distinguish tractable and intractable constraint satisfaction problems we hope to develop new tools for approaching this fundamental problem.
Organisations
Publications
Carbonnel C
(2015)
Tractability in constraint satisfaction problems: a survey
in Constraints
Carbonnel C
(2019)
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns.
in Algorithmica
Carbonnel C
(2014)
Principles and Practice of Constraint Programming
Carbonnel C.
(2018)
On singleton arc consistency for CSPs defined by monotone patterns
in Leibniz International Proceedings in Informatics, LIPIcs
Cohen D
(2016)
The power of propagation: when GAC is enough
in Constraints
Cohen D
(2017)
Binarisation for Valued Constraint Satisfaction Problems
in SIAM Journal on Discrete Mathematics
Cohen D
(2019)
Binary constraint satisfaction problems defined by excluded topological minors
in Information and Computation
Cohen D
(2015)
Variable and value elimination in binary constraint satisfaction via forbidden patterns
in Journal of Computer and System Sciences
| Description | This grant was concerned with finding ways to define restrictions on the constraint satisfaction problem that ensure that it can be solved efficiently. Two types of restrictions have previously been studied in detail: restrictions on the kind of constraints that can be used (these are called constraint language restrictions) and restrictions on how the constraints are arranged (these are called structural restrictions). Our project explored novel ways to combine these two kinds of restrictions in a more general framework of hybrid restrictions in order to be able to identify a much wider class of tractable constraint satisfaction problems. During the period of this grant other researchers finally completed the proof of the dichotomy for constraint languages, showing that every constraint language is either NP-complete or gives rise to problems that can be solved in polynomial time. This, together with the known characterisation (both for standard complexity and for fixed parameter complexity) of tractable constraint structures justified our assertion that the time is right for hybrid approaches. The most common approach to hybrid tractability has been based on the use of forbidden elements in the problems, which we called "patterns". This is the approach behind the most successful work on hybrid restrictions so far, the identification of a pattern called a "broken triangle" which we introduced in our earlier work. Several publications on the broken triangle pattern and its various extensions have now appeared, and this work is being continued by several other researchers. During this grant we put patterns into a strong theoretical context, and this work was presented in a number of publications. For example, we have identified all patterns that allow variable and value elimination, and this has received much attention in the community. Furthermore we have characterised the patterns that are solved by arc consistency. This led directly to our work characterising all constraint satisfaction problems that are solved by arc consistency, which was one of three selected from the international conference on constraint programming in 2016 for journal publication. Using our new framework we also published work establishing a very strong theoretical reason why binary CSP instances are sufficient for understanding the tractability of all instances. A consequence of our work has been that we now have new tools for establishing the complexity of fragments of the CSP problem, which will be of use to the community in understanding the tractability landscape. We also explored more generalised notions of patterns, and published results on extending the broken triangle property to higher order problems (where constraints are not limited to be binary). Towards the end of the project we began work on a Galois connection for patterns which we hope will link descriptive logic with the kinds of problems found useful in the proof of the constraint language dichotomy. This unification was described in the final and most adventurous work package of the grant. |
| Exploitation Route | Constraint satisfaction problems are a very broad class of computational problems used in many areas for describing combinatorial search problems such as timetabling and configuration problems. Understanding when such problems can be solved efficiently allows larger problems to be tackled effectively, and may contribute to the design of special-purpose solution software. |
| Sectors | Digital/Communication/Information Technologies (including Software) |