Example channelling constraints ECLiPSe

Question

Can someone provide a simple example of channelling constraints?

Channelling constraints are used to combine viewpoints of a constraint problem. Handbook of Constraint Programming gives a good explanation of how it works and why it can be useful:

The search variables can be the variables of one of the viewpoints, say X1 (this is discussed further below). As search proceeds, propagating the constraints C1 removes values from the domains of the variables in X1. The channelling constraints may then allow values to be removed from the domains of the variables in X2. Propagating these value deletions using the constraints of the second model, C2, may remove further values from these variables, and again these removals can be translated back into the first viewpoint by the channelling constraints. The net result can be that more values are removed within viewpoint V1 than by the constraints C1 alone, leading to reduced search.

I do not understand how this is implemented. What are these constraints exactly, how do they look like in a real problem? A simple example would be very helpful.

Answer 1

As stated in Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems (P.A. Geelen):

Channelling constraints of two different models allows for the expression of a relationship between two sets of variables, one of each model.

This implies assignments in one of the viewpoints can be translated into assignments in the other and vice versa, as well as, when search initiates, excluded values from one model can be excluded from the other as well.

Let me throw in an example I implemented a while ago while writing a Sudoku solver.

Classic viewpoint

Here we interpret the problem in the same way a human would: using the integers between 1 and 9 and a definition that all rows, columns and blocks must contain every integer exactly once.

We can easily state this in ECLiPSe using something like:

% Domain
dim(Sudoku,[N,N]),
Sudoku[1..N,1..N] :: 1..N

% For X = rows, cols, blocks
alldifferent(X)

And this is yet sufficient to solve the Sudoku puzzle.

Binary boolean viewpoint

One could however choose to represent integers by their binary boolean arrays (shown in the answer by @jschimpf). In case it's not clear what this does, consider the small example below (this is built-in functionality!):

?­ ic_global:bool_channeling(Digit, [0,0,0,1,0], 1).
    Digit = 4
    Yes (0.00s cpu)
?­ ic_global:bool_channeling(Digit, [A,B,C,D], 1), C = 1.
    Digit = 3
    A = 0
    B = 0
    C = 1
    D = 0
    Yes (0.00s cpu)

If we use this model to represent a Sudoku, every number will be replaced by its binary boolean array and corresponding constraints can be written. Being trivial for this answer, I will not include all the code for the constraints, but a single sum constraint is yet enough to solve a Sudoku puzzle in its binary boolean representation.

Channelling

Having these two viewpoints with corresponding constrained models now gives the opportunity to channel between them and see if any improvements were made.

Since both models are still just an NxN board, no difference in dimension of representation exists and channelling becomes real easy.

Let me first give you a last example of what a block filled with integers 1..9 would look like in both of our models:

% Classic viewpoint
1 2 3
4 5 6
7 8 9

% Binary Boolean Viewpoint
[](1,0,0,0,0,0,0,0,0)  [](0,1,0,0,0,0,0,0,0)  [](0,0,1,0,0,0,0,0,0) 
[](0,0,0,1,0,0,0,0,0)  [](0,0,0,0,1,0,0,0,0)  [](0,0,0,0,0,1,0,0,0) 
[](0,0,0,0,0,0,1,0,0)  [](0,0,0,0,0,0,0,1,0)  [](0,0,0,0,0,0,0,0,1)

We now clearly see the link between the models and simply write the code to channel our decision variables. Using Sudoku and BinBools as our boards, the code would look something like:

( multifor([Row,Col],1,N), param(Sudoku,BinBools,N) 
do
  Value is Sudoku[Row,Col], 
  ValueBools is BinBools[Row,Col,1..N], 
  ic_global:bool_channeling(Value,ValueBools,1) 
).

At this point, we have a channelled model where, during search, if values are pruned in one of the models, its impact will also occur in the other model. This can then of course lead to further overall constraint propagation.

Reasoning

To explain the usefulness of the binary boolean model for the Sudoku puzzle, we must first differentiate between some provided alldifferent/1 implementations by ECLiPSe:

What this means in practice can be shown as following:

?­ [A, B, C] :: [0..1], ic:alldifferent([A, B, C]). 
  A = A{[0, 1]} 
  B = B{[0, 1]} 
  C = C{[0, 1]} 
  There are 3 delayed goals. 
  Yes (0.00s cpu) 

?­ [A, B, C] :: [0..1], ic_global:alldifferent([A, B, C]). 
  No (0.00s cpu)

As there has not yet occurred any assignment using the Forward Checking (ic library), the invalidity of the query is not yet detected, whereas the Bounds Consistent version immediately notices this. This behaviour can lead to considerable differences in constraint propagation while searching and backtracking through highly constrained models.

On top of these two libraries there is the ic_global_gac library intended for global constraints for which generalized arc consistency (also called hyper arc consistency or domain consistency) is maintained. This alldifferent/1 constraint provides even more pruning opportunities than the bounds consistent one, but preserving full domain consistency has its cost and using this library in highly constrained models generally leads to a loss in running performance.

Because of this, I found it interesting for the Sudoku puzzle to try and work with the bounds consistent (ic_global) implementation of alldifferent to maximise performance and subsequently try to approach domain consistency myself by channelling the binary boolean model.

Experiment results

Below are the backtrack results for the 'platinumblonde' Sudoku puzzle (referenced as being the hardest, most chaotic Sudoku puzzle to solve in The Chaos Within Sudoku, M. Ercsey­Ravasz and Z. Toroczkai) using respectively forward checking, bounds consistency, domain consistency, standalone binary boolean model and finally, the channelled model:

      (ic)   (ic_global)  (ic_global_gac)  (bin_bools)  (channelled)
BT    6 582      43             29             143           30

As we can see, our channelled model (using bounds consistency (ic_global)) still needs one backtrack more than the domain consistent implementation, but it definitely performs better than the standalone bounds consistent version.

When we now take a look at the running times (results are the product of calculating an average over multiple executions, this to avoid extremes) excluding the forward checking implementation as it's proven to no longer be interesting for solving Sudoku puzzles:

          (ic_global)  (ic_global_gac)  (bin_bools)  (channelled)
Time(ms)     180ms          510ms           100ms        220ms

Looking at these results, I think we can successfully conclude the experiment (these results were confirmed by 20+ other Sudoku puzzle instances):

Channelling the binary boolean viewpoint to the bounds consistent standalone implementation produces a slightly less strong constraint propagation behaviour than that of the domain consistent standalone implementation, but with running times ranging from just as long to notably faster.

EDIT: attempt to clarify

Imagine some domain variable representing a cell on a Sudoku board has a remaining domain of 4..9. Using bounds consistency, it is guaranteed that for both value 4 and 9 other domain values can be found which satisfy all constraints and thus provides consistency. However, no consistency is explicitly guaranteed for other values in the domain (this is what 'domain consistency' is).

Using a binary boolean model, we define the following two sum constraints:

• The sum of every binary boolean array is always equal to 1
• The sum of every N'th element of every array in every row/col/block is always equal to 1

The extra constraint strength is enforced by the second constraint which, apart from constraining row, columns and blocks, also implicitly says: "every cell can only contain every digit once". This behaviour is not actively expressed when using just the bounds consistent alldifferent/1 constraint!

Conclusion

It is clear that channelling can be very useful to improve a standalone constrained model, however if the new model's constraint strengthness is weaker than that of the current model, obviously, no improvements will be made. Also note that having a more constrained model doesn't necesarilly also mean an overall better performance! Adding more constraints will in fact decrease amounts of backtracks required to solve a problem, but it might also increase the running times of your program if more constraint checks have to occur.