Gecode is one of the most e cient libraries that can be used for constraint solving. However, using it requires dealing with C++ programming details. On the other hand several formats for representing constraint networks have been proposed. Among them, XCSP has been proposed as a format based on XML which allows us to represent constraints de ned either extensionally or intensionally, permits global constraints and has been the standard format of the international competition of constraint satisfaction problems solvers. In this paper we present a plug-in for solving problems speci ed in XCSP by exploiting the Gecode solver. This is done by dynamically translating constraints into Gecode library calls, thus avoiding the need to interact with C++.
Constraint Programming [
XCSP is a language structurally very similar to FlatZinc. XCSP was de ned
with the purpose of being a unique constraint model that could be used by all
the CP solvers. It was rst proposed in 2005 for the solvers competing in the
International CSP Solver Competition [
The need of a standard is also caused by the huge number and diversity
of solvers. Today only few solvers support natively FlatZinc or XCSP.
Unfortunately, Gecode [
In the reset of this paper, we present in Section 2 a brief overview of the XCSP language and of the Gecode solver. In Section 3 we describe the idea behind the x4g plug-in. Section 4 concludes by mentioning some directions for future works. 2
An extensive presentation of the XCSP format and the Gecode solver is beyond the scope of this paper. Here we just give a short overview of XCSP and Gecode. 2.1
XSCP is an extended format to represent constraint networks using XML. The Extensible Markup Language (XML) is a simple and exible text format playing an increasingly important role in the exchange of a wide variety of data on the Web. The objective of the XML representation (in XCSP) is to ease the e ort required to test and compare di erent algorithms by providing a common testbed of constraint satisfaction instances. The proposed representation is low-level: for each instance the domains, variables, relations (if any), predicates (if any) and constraints are exhaustively de ned. No control ow constructs like\for" cycles or \if then else" statements can be used.
Roughly speaking, there exist two variants of this format: a fully-tagged representation and an abridged representation. The rst one is a full XML, completely structured representation which is suitable for using generic XML tools but is quite verbose and tedious to use for a human being. The second representation is just a shorthand notation of the rst one and it is easier to read and to write for a human being, but less suitable for generic XML tools. 1 The MiniZinc Challenge has a smaller benchmark of instances and fewer participants than the International Solver Competition.
As an example of an XCSP program consider the following one where the well known \all di erent" constraint is applied to two variables A1 and A2 which can assume values only in the domain [1; 2]. <domains nbDomains="1">
<domain name="d0" nbValues="2">1..2</domain> </domains> <variables nbVariables="2"> <variable name="A1" domain="d0"/> <variable name="A2" domain="d0"/> </variables> <constraint name="c0" arity="2" scope="A1 A2" reference="global:alldifferent"/> 2.2
Gecode (Generic Constraint Development Environment) provides a constraint solver with state-of-the-art performance while being modular and extensible. It supports the programming of new propagators, branching strategies, and search engines. New domains can be programmed at the same level of e ciency as nite domain and integer set variables that are already prede ned. Furthermore Gecode is distributed under a very permissive license, it is portable and well documented, and comes with a complete tutorial. All these features have made Gecode one of the preferred choices for solving CSPs.
Gecode is written in C++ and supports the FlatZinc format through an
external plug-in that is able to parse a FlatZinc instance and solve it using
Gecode library calls. The use of this plug-in allowed Gecode to participate to
the 2010 MiniZinc challenge [
x4g
In principle the translation of XCSP instances into Gecode is similar to the task
performed by the Gecode/FlatZinc plug-in [
To use Gecode in order to solve CSPs de ned in XCSP, one could try
implement a XCSP to FlatZinc compiler. However, in order to avoid potential loss
of information, to be more exible and less dependent on the Gecode/FlatZinc
plug-in, we chose to provide a direct translation from XCSP into Gecode. Hence
we have developed x4g; a plug-in that parses an XCSP instance and, for
every constraint de ned within the XCSP le, generates an equivalent number of
Gecode constraints. When all the XCSP constraints are translated into Gecode
constraints, a Gecode Space Object is returned. This object can later be used to
get a solution to the CSP problem by using one of the many prede ned search
strategies provided by Gecode or local search strategies following [
To develop the x4g plug-in we used the XCSP parser provided by the
International CSP competition organizers. This parser, developed in particular
to support the abridged notation, is written in C++ by using the well known
libxml2 libraries [
The XCSP format is mainly used to specify CSPs but it also supports extensions to de ne weighted constraints or quanti ers over constraints. x4g was designed to target only CSPs, hence it does not support these additional features.
XCSP supports only nite domains. Since Gecode supports nite domains
too, the domain encoding from XCSP to Gecode was straightforward. XCSP
provides a construct which allows one to de ne relations over variables. These
could be seen as constraints listing all the admissible values that some variables
can take. XCSP relations are mapped into Gecode by using extensional
constraints. In XSCP the semantics of a relation can also be given by stating all
the non admissible values of the variables (i.e. con icts between variables). We
used inequality constraints for translating these relations into Gecode. Another
construct of XCSP is predicate, a boolean parametric expression that is
considered satis ed if and only if it evaluates to true. The number of parameters
in a predicate is xed and, di erently from relations, predicates allow integer
parameters. The mapping of the predicates was also straightforward because,
with only few exceptions, Gecode has for every predicate an API for posting an
equivalent constraint. As far as global constraints are concerned, XCSP supports
the majority of the global constraints de ned in the Global Constraint Catalog
[
Finally, to give an example of how x4g could be used, we developed a program
that takes as input a XCSP instance and, by using x4g, allows us to nd a
solution by using the deep rst strategy natively implemented in Gecode. Since
the output of this program follows the output rules of the International Solver
Competition, it could be used to let Gecode enter the next International CSP
Competition.
2 Note that the XCSP format speci es only the constraints, the choice of the search
strategy is left to the user.
3 For a precise de nition of these constraints see [
This work has to be considered as a rst step in the direction of providing a full translation of XCSP constraints into Gecode constraints. As a future work, we would like to support more global constraints and to de ne e cient ways of decomposing them by using Gecode constraints. We also would like to extend our tool in order to use Gecode for solving the optimization problems that can be de ned in XCSP exploiting weighted constraints.
Moreover, we are interested in the development of a FlatZinc/XCSP conveyer that will allow us to add FlatZinc instances into the benchmarks that could be used for comparing Gecode with other constraint solvers. Furthermore, with such a converter it could be also possible to compare the e ciency of our x4g translation with the one of the Gecode/FlatZinc plug-in.