<XML><RECORDS><RECORD><REFERENCE_TYPE>31</REFERENCE_TYPE><REFNUM>6477</REFNUM><AUTHORS><AUTHOR>Prosser,P.</AUTHOR><AUTHOR>Selensky,E.</AUTHOR></AUTHORS><YEAR>2002</YEAR><TITLE>A Study of Encodings of Constraint Satisfaction Problems with 0/1 Variables</TITLE><PLACE_PUBLISHED> ERCIM workshop on Constraint Solving and Constraint Logic Programming
</PLACE_PUBLISHED><PUBLISHER>N/A</PUBLISHER><LABEL>Prosser:2002:6477</LABEL><ABSTRACT>Many constraint satisfaction problems (csp's) are formulated with
0/1 variables. Sometimes this is a natural encoding, sometimes
it is as a result of a reformulation of the problem, other times 0/1
variables make up only a part of the problem. Frequently we have constraints
that restrict the sum of the values of variables. This can be encoded
as a simple summation of the variables. However, since variables
can only take 0/1 values we can also use an occurrence constraint,
e.g. the number of occurrences of 1 must be $k$.
Would this make a difference? Similarly, problems
may use channelling constraints and encode these as a biconditional such as
$P \leftrightarrow Q$ (i.e. $P$ if and
only if $Q$). This can also be encoded in a number of ways. Might this make
a difference as well? We attempt to answer these questions, using a variety
of problems and two constraint programming toolkits. We show that even minor
changes to the formulation of a constraint can have a profound effect on the
run time of a constraint program and that these effects are not consistent
across constraint programming toolkits.
This leads us to a cautionary note for constraint programmers: take note
of how you encode constraints, and don't assume computational behaviour is toolkit independent.
</ABSTRACT><NOTES>to appear</NOTES></RECORD></RECORDS></XML>