Construction of a combined Model

The idea of combining mutually redundant models was first introduced by Cheng, Choi, Lee and Wu [9]. Let V1 = (X1, D1) and V2 = (X2, D2) two viewpoints for the same problem. From each viewpoint a complete model can be constructed, say M1 = ( X1, D1, C1), M2 = ( X2, D2, C2). So, they are mutually redundant.

If you combine these two models, you get a new model M3 = ( X3, D3, C3), where X3 = X1 $ \cup$ X2, D3 = D1 $ \cup$ D2 and C3 = C1 $ \cup$ C2 $ \cup$ Cc. Cc is a set of channeling constraints.

You should always choose constraints that are of low arity, i.e. that assignments in one viewpoint can be propagated in the other when only a few variables have been assigned. The combination of viewpoints is useless if propagation via channeling constraints can only occur when a complete assignment has been made. It can also be an advantage to do a combined model without constraints that are hard to express in one viewpoint, provided that the constraints of the other viewpoint together with the channeling constraints take on their work.

Channeling constraints

Channeling constraints relate the variables of two viewpoints. Usually, they are of binary form, i.e. they relate a single variable in one viewpoint to a single variable in the other. If an assignment is made in the model constructed from one viewpoint, it can be translated into an assignment in the other and vice versa.

Hence, the advantage of a combined model is the strenghtened propagation caused by these channeling constraints. If in one model, say M1 = ( X1, D1, C1), the values from the variables in X1 are reduced by the constraints in C1, their removal is propagated by the channeling constraints to the variables of the other model M2 = ( X2, D2, C2). So, the propagated removals from the first viewpoint together with the constraints in C2 may remove more values from the domains of X2's variables than the constraints in C2 alone.

Andreas Rossberg 2006-08-28