3
$\begingroup$

In Constraint programming we have Variables and their Domains and then all the constraints, but if you at the concept of a domain of a variable it is nothing but another type of constraint, you are saying that this variable can take all these values. Is there any particular reason why domain is defined as a different concept than constraints?

$\endgroup$
  • $\begingroup$ May I ask what is the context of your question? Is it a general question about the logic of constraint programming and the design of constraint programming languages. Or is it a more mundane question on how to use domains and constraints in constraint programming? $\endgroup$ – babou May 28 '15 at 15:27
2
$\begingroup$

As you observe, restricting the domain of a variable has exactly the same effect as applying a unary constraint to it.

One situation where you might prefer to use unary constraints rather than restricted domains is when you want to control very tightly the relations that are allowed to be used in constraints. For example, if you want to investigate the computational complexity of CSP with a particular class of constraint languages. On the other hand, such investigations often assume that all unary relations are included in the constraint language, which is equivalent to fixing a global domain but allowing the domain of any variable to be any subset of that. (This is known as the "conservative" case because of certain algebraic properties of the constraint langauges.)

$\endgroup$
1
$\begingroup$

Even though a domain may be considered just another type of constraint, there do exist good reasons to keep them separated, and it may be easier to think of them from a pure mathematical standpoint. Domains should in a sense be seen as the definition of the variable in terms of Type - e.g. Integer or Real etcetera. The domains can also be seen as the Master bounds. Defining the domain type (Integer / Real) is also important to help the constraint solver determine what solving method to use for each specific constraint.

I would like to illustrate it with the following example;

Consider the following constraint problem for Pythagoras theorem.

Variables: a b c

Domains: a [1..10] Integer b [1..10] Integer c [1..10] Integer

Constraint: a x a + b x b = c x c

We actually have three unknowns but the finite sets of the domains will allow the constraint solver to find the following solutions for a,b,c;

a = 3,4,6,8 b = 3,4,6,8 c = 5,10

Now let us change the domains from Integer to Real, to the following;

a [1..10] Real b [1..10] Real c [1..10] Real

Simply by changing the domains, it will no longer be possible to find all solutions as there do exist an infinite number of solutions.

Therefore, the domains should in general be seen as the main definition of the total search space (in terms of type and bounds) while the constraints should be seen as the definition of the problem.

$\endgroup$
0
$\begingroup$

I suppose what is called domain for constraint programming corresponds to what would be called type in most contexts, and particularly in most programming languages.

The issue of types is an old one, and I am unfortunately not knowledgeable enough to give you a precise account. But this may hopefully serve as an introduction.

The idea of theorizing types is attributed to Bertrand Russell, to serve as an alternative to set theory and do away with some paradoxes of naive set theory.

What it says, intuitively, is that terms are always supposed to be typed and that operators or predicate make sense only when applied to the proper types. The idea is quite close to static type checking in programming languages. But I suggest you read at least the beginning of the wilipedia page on Type Theory, which seems rather clear.

Thus, as a first approximation, it seems quite possible to do as suggested in the question: consider the domains as simple constraints, on a universal sets of values. That is just returning to naive set theory and its paradoxes, which was however sufficient to do a lot of good mathematics for some time.

But it seems that a cleaner way to do things is to separate values into domains were operations and predicates have meaning. Otherwise, is the value true odd or even, and what is its square root? This is the way to ensure that the language you use (whether constraints or other) will have properly defined semantics, relying hopefully on a consistent logic.

But can we have both consistency and domains as constraints, and is there a cost?

The benefits of typing may come at the cost of Turing Completeness. For example, while (untyped) $\lambda$-calculus is Turing complete, simply typed $\lambda$-calculus is more restricted. Whether typing can be consistent with Turing Completeness is an issue I would not address at my competence level.

An important point of all this however is that typing systems have been shown to be isomorphic to logical predicates, through what is known as the Curry-Howard isomorphism. So this would vindicate from a theoretical perspective the view that domains can be seen as a constraint expressed by some predicate to be satisfied. From this point of view, there is no difference between a formula (to be satisfied) and a type, given appropriate formalization apparatus with a consistent logic.

However, it may be (I do not know) that distinguishing domains from other predicates may be a way of enforcing consistency of the underlying logical system (to be checked).

Now, if you wish for more details, it would be best to asked a full-fledged type theorist, as I am getting onto grounds for which I have no chart.

From a more mundane point of view, you may consider that expressing constraints makes sense only with respect to some domain, and there is in practice a hierarchical structures that enforces the existence of some sense (semantics) to what can be written, and also allows for more efficient implementations. That is pretty much, I believe, why static types were introduced in programming languages, as they had to refer to the encoding techniques used for the corresponding values (though I would not underestimate the influence of logicians on early programming language design, especially Lisp and Algol, that were both extremely influencial).

Of course, if the kind of domains you are willing to consider in your constraint programming language is very restricted, you are probably safe from paradoxes, and could, if you wish, freely see domains as unary constraints as already suggested by David Richerby's answer.

$\endgroup$
  • $\begingroup$ I don't think that most of this is really relevant to constraints. In particular, the question isn't asking for a type theory of constraints, or really about how one might design a constraint language. And, in the constraint world, it's not really an issue that there's no such thing as the square root of a Boolean value: "square root" is a relation between integers so there's no $y$ such that $\mathrm{sqrt}(\mathrm{true},y)$ holds, so you'll never satisfy a constraint about square roots by assigning a Boolean to something that's supposed to be an integer. $\endgroup$ – David Richerby May 28 '15 at 11:42
  • $\begingroup$ And the paradoxes of set theory will never come up because there's no mechanism for self-reference. $\endgroup$ – David Richerby May 28 '15 at 11:42
  • $\begingroup$ @DavidRicherby I realize that constraint programming does not necessarily get into such issues, though it does mix with other programming paradigms. However, I do believe it may be useful to take a larger view and see whether what works because it is "simple" (I do not mean easy, or trivial) can be inscribed into a more general view of things. In this sense, I do believe that what I said is relevant. I do realize that this can deal with "type errors" such as sqrt(true,x), and my example may not be pedagogical since the real issue is not a naive one. But I think what I said does stand. $\endgroup$ – babou May 28 '15 at 12:15
  • $\begingroup$ @DavidRicherby You are saying there are no problem in doing it because there is no mechanism for self reference. This justification was not in your answer, which would lead me to think that it said "yes, we can!", but not really why we can. So possibly my answer contributed as much. One purpose of my answer is to suggest that there are probably deep reasons why it makes sense to do it, and keep a consistent system, rather than, yes, we can hack it. Maybe such as having no mechanism for self-reference. $\endgroup$ – babou May 28 '15 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.