Concepts and Methods of Programming

Constraints Programming

Useful links

Mozart/Oz home page
Finite Domain Constraint Programming in Oz -tutorial Oz
The Global Index in the Oz tutorial - the best language reference.
In Polish

Short introduction

based on chapter 12 of Concepts, Techniques, and Models of Computer Programming

Constraint programming consists of a set of techniques for solving constraint satisfaction problems. A constraint satisfaction problem, or CSP, consists of a set of constraints on a set of variables. A constraint, in this setting, is simply a logical relation, such as "X is less than Y" or "X is a multiple of 3Y". The first problem is to find whether there exists a solution, without necessarily constructing it.The second problem is to find one or more solutions.
Constraint programming is very close to the ideal of declarative programming: to say what we want without saying how to achieve it.
Propagate-and-search
The propagate-and-search approach is based on three important ideas:
1. Keep partial information. During the calculation, we might have partial information about a solution (such as, "in any solution, X is greater than 100"). We keep as much of this information as possible.
2. Use local deduction. Each of the constraints uses the partial information to deduce more information. For example, combining the constraint "X is less than Y" and the partial information "X is greater than 100" we can deduce that "Y is greater than 101"(assuming Y is an integer).
3. Do controlled search. When no more local deductions can be done, then we have to search. The idea is to search as little as possible. We will do just a small search step and then we will try to do local deduction again.A search step consists in splitting a CSP P into two new problems, (P^¬C) and (P^C), where C is a new constraint. Since each new problem has an additional constraint, it can do new local deductions. To find the solutions of P, it is enough to take the union of the solutions to the two new problems.The choice of C is extremely important. A well-chosen C will often lead to a solution in just a few search steps.
Basic definitions:
- A constraint is a formula of predicate logic. Here are typical examples of constraints occurring with finite domain problems:
```
 
declare X Y in
X::90#110
Y::48#53
```
  The notation X::90#110 means x belongs to {90, 91, . . . , 110}.
- Constraint propagation is an inference rule for finite domain problems that narrows the domains of variables. For instance, given the inequation
```
    X<:Y
```
  and the domain constraints
```
    X::23#100
    Y::1#33
```
  constraint propagation can narrow the domains of X and Y to
```
    X::23#32
    Y::24#33
```

Search tree example

Constraints:

X<>7 Z<>2 X-Z=3*Y
X belongs to {1, 2, ... 8}
Y belongs to {1, 2, ... 10}
Z belongs to {1, 2, ... 10}

Basic constraints
- equality =: <: >: =<: =>: \=:
- {FD.distinct Xs} - All elements in Xs are pairwise distinct.
- other propagators
Example: how can I make a rectangle out of 24 unit squares so that the perimeter is exactly 20?
We have constraints:
```
         X*Y=:24
         X+Y=:10
         X=<:Y %we can assume that
         X::1#9 %because of sum X+Y
         X::1#9  
```
Solution in Oz
```
      proc {Rectangle ?Sol}
        sol(X Y)=Sol
      in
        X::1#9 Y::1#9
        X*Y=:24 X+Y=:10 X=<:Y
        {FD.distribute naive Sol}
      end

      {Browse {SearchAll Rectangle}}
```
FD.distribute - selects the distribution strategy.The chosen strategy (naive) selects the first nondetermined variable in Sol, and picks the leftmost element in the domain as a guess e.g in:
```
      X=4
      Y::5#6
```
X is determined, Y is nondetermined and the naive strategy chooses Y=5 as a quess
Example: a cryptarithmetic problem - assign digits to letters such that the following addition makes sense:
```
        S E N D
      + M O R E
      ---------
      M O N E Y
```
There are two conditions: each letter is assigned to a different digit and the leading digits of the numbers are different from zero.
Solution in Oz

More cryptarithms
Example: Zebra Puzzle

Assignments

Pythagoras: how many triples (A,B,C) exist such that A^2+B^2=C^2 and A≤B≤C≤1000? Compare your solution with that in Mozart documentation

Write a solution to "Two twos" cryptarithmetic problem. Star could be any digit except for 2, leading digits are different from 0.

                * * *
            x   * * *
       -----------------
                * 2 *
            * * 2 *
          * * * *      
          * * * * * *

Write a solution to a Tiny Transportation Problem (explanation in this presentation).
Hint: study the Branch and Bound chapter. Modify the `Locating Warhehouses' example.

Bibliography

Combining constraing programming and linear programming to optimize bus driver schedule.

Bartosz Baliś, balis at agh.edu.pl
Katarzyna Rycerz, kzajac at agh.edu.pl