Dual Models in Constraint Programming
Research Report 2001.02, School of Computing, University of Leeds,
January 2001.
Barbara M Smith
Abstract
In modelling a problem as a constraint satisfaction problem, it is often possible
to find alternative models representing complementary views of the problem. It has been proposed that such dual models could be linked into a single model, with channelling constraints linking their variables. This can reduce search by allowing more constraint propagation than with either model separately. However, combining two complete models can increase overall running time because of the increased numbers of constraints and variables. We consider how much of the second model it
may be necessary to include; in the particular case of permutation problems it is
shown that additional constraint propagation is due to the channelling constraints themselves, and that the constraints of the dual model are not required. Combinations of models using integer variables and set variables are also considered. The derivation of dual models, including cases where more than two dual models exist, is discussed.
Back to "Barbara Smith
- Papers on Constraint Programming"