
## 5.4 Constraints

For any WCSP instance, it is required to introduce an attribute maximalCost to the element <constraints>. The value of this attribute is of type integer
(and must be strictly positive) and represents the maximum cost of the WCSP
framework (the k value). Remember that it corresponds to a total violation and may be equal to 'infinity' (whereas 0 corresponds to a total satisfaction). Also, an optional attribute initialCost to the element <constraints> is introduced. If present, the value of this attribute is of type integer and represents a constant cost that must be added to the sum of constraints cost. This is the cost of the 0-ary constraint of the WCSP framework which is sometimes assumed (e.g. see
[12]). When not present, it is assumed to be equal to 0.

Remark 2 *When representing a WCSP instance, it is possible to refer to hard* constraints (defined in extension or intension). For such constraints, an allowed tuple has a cost of 0 *while a disallowed tuple has a cost equal to the value of the* attribute maximalCost.

## 5.5 Illustration

The representation in XCSP 2.1 of an illustrative WCSP instance is given by Figure 12.

## Acknowledgments

We would like to thank very much Nicolas Beldiceanu, Marco Beneditti, Marc van Dongen, Simon de Givry, Fred Hemery, Arnaud Lallouet, Radoslaw Szymanek and J´er´emie Vautard for helpful suggestions and comments.

## References

[1] K.R. Apt. *Principles of Constraint Programming*. Cambridge University Press, 2003.

[2] N. Beldiceanu, M. Carlsson, and J. Rampon. Global constraint catalog.

Technical report, Swedish Institute of Computer Science, 2005.

[3] M. Benedetti, A. Lallouet, and J. Vautard. QCSP made practical by virtue of restricted quantification. In *Proceedings of IJCAI'07*, pages 6–12, 2007.

[4] S. Bistarelli, U. Montanari, F. Rossi, T. Schiex, G. Verfaillie, and H. Fargier. Semiring-based csps and valued csps: Frameworks, properties, and comparison. *Constraints Journal*, 4(3):199–240, 1999.

[5] L. Bordeaux and E. Monfroy. Beyond NP: Arc-Consistency for quantified constraints. In *Proceedings of CP'02*, pages 371–386, 2002.