Martin J. Green

In Dechter's paper, `From local to global consistency', we see that there exists a certain level of local consistency for a Constraint Satisfaction Problem, or CSP, which if achieved (or bettered) implies that the CSP is in fact globally consistent.

In this paper we will revisit Dechter's proof of the theorem and then give a second, constructive, proof of the same property. This constructive proof gives rise to a strategy for setting an initial assignment to each variable for use in stochastic search methods, which applies to less locally consistent Constraint Satisfaction Problems.

We present this heuristic, the Local Consistency Heuristic (LCH) Algorithm and discuss some properties of it. Finally, we give a complexity analysis of this new algorithm with reference to the number of constraint checks.

In this project we will consider the effect of modelling problems as Constraint Satisfaction Problems and then implementing these in the Optimization Programming Language.

This report contains two parts. In the first four chapters we will consider the background work required to implement some problems in a Constraints Programming Language. We will discuss constraints and the Constraint Satisfaction paradigm. We will explore the effect of consistency and symmetry on the resulting search for any solutions and consider the algorithms that may be used for this search. One problem exhibiting a high degree of symmetry is an Indicator Problem, used to determine the expressibility of a relational language. In this first section, we will describe this problem. Finally, we will see what decisions need to be made when implementing a problem in a Constraints Programming Language, such as the Optimization Programming Language.

In the second half of the report we will look at three distinct implementations of Constraint Satisfaction Problems in the Optimization Programming Language. We will begin by implementing an Indicator Problem to show how we might use these to determine expressibility. We will then describe a modified implementation of the Frequency Assignment Problem, showing the changes made to minimise the span for the model. Finally, we will look at an interesting problem, that of packing a Master Cube with cuboids. We will show that by exploiting the vast symmetries of the problem, we can find a solution in a reasonably quick time.

A constraint satisfaction problem instance (CSP) consists of a collection of variables that need to have values assigned to them. The assignments are limited by constraints that force the values taken by certain collections of variables (the constraint scopes) to satisfy specified properties (the constraint relations). Many practical problems, such as scheduling, timetabling, frequency assignment, etc. can be formulated in this framework.

As the general constraint satisfaction problem is NP-hard there has been significant effort devoted to discovering tractable subproblems of the constraint satisfaction problem.

The structure of a CSP is defined to be the hypergraph formed by the constraint scopes. Restricting the possible structure of CSPs has been a successful way of identifying tractable subproblems.

The language of a CSP is defined to be the set of constraint relations of the instance. Restricting the language allowed for CSPs has also yielded many interesting tractable subproblems.

Almost all known tractable subproblems are either structural or relational. In this paper we construct tractable subproblems of the general constraint satisfaction problem that are neither defined by structural nor relational properties.

These new tractable classes are related to tractable languages in much the same way that general decompositions (cutset, tree-clustering, etc.) are related to acyclic decompositions. It may well be that our results will begin to make language based tractability of more practical interest.

We show that our theory allows us to properly extend the binary max-closed language based tractable class, which is maximal as a tractable binary constraint language. Our theory also explains the tractability of the constraint representation of the Stable Marriage Problem which has not been amenable to existing explanations of tractability. In fact we provide a uniform explanation for the tractability of the class of max-closed CSPs and the SMP.

There has been much work done on so called renamable HORN theories which are a tractable subproblem of SAT. It has been shown that renamable HORN theories are tractably identifiable and solvable. It has also been shown that finding the largest sub-theory that is renamable HORN is NP-hard. These results also follow immediately from our theory.

A constraint satisfaction problem instance consists of a collection of variables that need to have values assigned to them. The assignments are limited by constraints that force the values taken by certain collections of variables (the constraint scopes) to satisfy specified properties (the constraint relations).

As the general CSP problem is NP-hard there has been significant effort devoted to discovering tractable subproblems of the CSP.

The structure of a CSP instance is defined to be the hypergraph formed by the constraint scopes. Restricting the possible structure of the CSP instances has been a successful way of identifying tractable subproblems.

The language of a CSP instance is defined to be the set of constraint relations of the instance. Restricting the language allowed for CSP instances has also yielded many interesting tractable subproblems.

Almost all known tractable subproblems are either structural or relational. In this paper we construct tractable subproblems of the general CSP that are neither defined by structural nor relational properties.

These new tractable classes are related to tractable languages in much the same way that general decompositions (cutset, tree-clustering, etc.) are related to acyclic decompositions. It may well be that our results will begin to make language based tractability of more practical interest.

We show that our theory allows us to properly extend the binary max-closed language based tractable class, which is maximal as a tractable binary constraint language. Our theory also explains the tractability of the constraint representation of the Stable Marriage Problem which has not been amenable to existing explanations of tractability. In fact we provide a uniform explanation for the tractability of the class of max-closed CSPs and the SMP.

There has been much work done on so called renamable HORN theories which are a tractable subproblem of SAT. It has been shown that renamable HORN theories are tractably identifiable and solvable. It has also been shown that finding the largest sub-theory that is renamable HORN is NP-hard. These results also follow immediately from our theory.

The constraint satisfaction paradigm models real world problems as a set of variables that need to be assigned values from some domain, satisfying some constraints. We model a real world problem as a Constraint Satisfaction Problem (CSP) by choosing an appropriate set of variables, domains for these variables and a set of constraints. We put a great deal of work into the design of data structures when programming software so that they are accessed and searched efficiently. We feel that the same effort should be given to the design of models in the constraint satisfaction paradigm.

There are many problems for which the natural model has an enormously large search space, and where natural or simple models are inadequate. For instance there may be many similar variables and the constraints may not be very restrictive, and there may still be few solutions. In this situation it is common for the search routine to thrash, meaning that it manages to assign many of the variables successfully but cannot find a complete solution. This results in a large number of reassignments to the last few variables.

We can often reduce search times and avoid thrashing by avoiding symmetry in our models. One approach is to break symmetry during search, or to add symmetry breaking constraints during modelling.

The approach we take in this paper is new. We use a constraint design pattern, tiling, which eliminates symmetry. This design pattern exploits the uniformity of the problem domain: solutions remain valid if translated across the domain, and then we can use so called tiles. These tiles are multiple assignments to similar variables and may be slid up and down the uniform domain in order to find solutions.

We have applied the tiling design pattern to a hard problem, the Model Aircraft Tournament and successfully solved a real world example which was not solved in a reasonable time using a more natural, simpler model. We expect that this constraint design pattern will have applications in other areas where there is both symmetry amongst subsets of the variables and in their domains.

This thesis is concerned with the area of constraint satisfaction. A constraint satisfaction problem instance has a collection of variables to which we wish to assign values chosen from a domain. There are also constraints, each of which limits the simultaneous assignment of values to some group of variables. A solution is an assignment to all of the variables that satisfies all of the constraints.

In this thesis we discuss the tractability of subclasses of the general constraint satisfaction problem. In particular, we are interested in the question of whether a problem instance can be reduced to an equivalent instance of a given tractable subclass.

This thesis contains three parts. The first part gives the necessary background information and definitions. We must consider what it means for a subclass to be tractable and what it means to reduce one problem instance to another.

In the second part we consider a new relational reduction to tractable constraint languages. Our approach uses domain permutations to transform a problem instance over one set of relations into an equivalent problem instance over a tractable constraint language. The new relations are simply domain permutations of the original relations. We define a transformation method, the lifted problem instance, whose solutions define the successful domain permutations, which we use to transform the original problem instance. We solve the original problem instance by solving the transformed instance. Tractable lifted problems can explain known tractability results as well as generate new tractable subclasses.

The final part of this thesis considers future directions and ideas. In particular, we introduce a new framework, the combination problem, that allows us to begin to describe more generalised decompositions and generate new tractable subclasses.