An XML Representation

Index:

 Introduction 

 Syntax 

 Conditions 

 Examples 


 CPAI'2005 

Introduction

This document describes an xml format for CSP specification. For more information, see Full Description.

[ Back to index ]

Syntax

<instance>
   <presentation
     name = 'put here the instance name'
     description = 'put here the instance description'
     nbSolutions = 'put here the number of solutions'
     solution = 'put here a solution'
     format = 'XCSP1.1'
   />
   <domains nbDomains='q'>
     <domain
       name = 'put here the domain name'
       nbValues = 'put here the number of values'
       values = 'domainDescription'
     />
    .
    .
   </domains>
   <variables nbVariable='n'>
     <variable
       name = 'put here the variable name'
       domain = 'put here the name of a domain'  
     />
    .
    .
   </variables>
   <relations nbRelations='r'>
     <relation
       name = 'put here the name of the relation'
       domain = 'put here the domain of the relation'
       nbSupports | nbConflicts = 'put here the number of supports or the number of conflicts'
       supports | conflicts = 'put here either the set of supports or the set of conflicts'
    />
    .
    .
   </relations>
   <constraints nbConstraints='m'>
     <constraint
       name = 'put here the name of the constraint'
       scope = 'put here the names of the variables involved in the constraint'
       relation = 'put here the name of the relation'
    />
    .
    .
   </constraints>
</instance>

 where q, n, r and m respectively denote the number of distinct domains, the number of variables, the number of distinct relations and the number of constraints.

[ Back to index ]

Conditions

In addition it is assumed that the specification satisfies the following conditions.

  • The order of the values in a domain definition will obey the usual lexical ordering.
  • Variables are numbered from X0–Xn-1, where n is the number of variables.
  • Values in the domains are numbered from -214–214.
  • The number of relations for a given fixed scope is equal to one.
  • The ith value of any tuple in a constraint or nogood constraint should be a member of the ith domain that that constraint or nogood constraint is defined on.
  • The order of the tuples in the relation definition will obey the usual lexicographical ordering.

[ Back to index ]

Examples

Example: 4-queens problem

<instance >
   <presentation
     name="4-queens"
     description="This problem involves placing 4 queens on a chessboard"
     nbSolutions="at least 1"
     format="XCSP1.1 (XML CSP Representation 1.1)"
   />
   <domains nbDomains="1">
     <domain name="dom0" nbValues="4" values="1..4" />
   </domains>
   <variables nbVariables="4">
     <variable name="X0" domain="dom0"/>
     <variable name="X1" domain="dom0"/>
     <variable name="X2" domain="dom0"/>
     <variable name="X3" domain="dom0"/>
   </variables>  
   <relations nbRelations="3">
     <relation
       name="rel0"
       domain="dom0 dom0"
       nbConflicts="10"
       conflicts="(1,1)(1,2)(2,1)(2,2)(2,3)(3,2)(3,3)(3,4)(4,3)(4,4)"
     />
     <relation
       name="rel1"
       domain="dom0 dom0"
       nbConflicts="8"
       conflicts="(1,1)(1,3)(2,2)(2,4)(3,1)(3,3)(4,2)(4,4)"
    />
     <relation
       name="rel2"
       domain="dom0 dom0"
       nbConflicts="6"
       conflicts="(1,1)(1,4)(2,2)(3,3)(4,1)(4,4)"
     />
   </relations >
   <constraints nbConstraints="6">
     <constraint name="C0" scope="X0 X1" relation="rel0"/>
     <constraint name="C1" scope="X0 X2" relation="rel1"/>
     <constraint name="C2" scope="X0 X3" relation="rel2"/>
     <constraint name="C3" scope="X1 X2" relation="rel0"/>
     <constraint name="C4" scope="X1 X3" relation="rel1"/>
     <constraint name="C5" scope="X2 X3" relation="rel0"/>
   </constraints>
</instance>

[Same example in table format]


Example: an instance involving non binary constraints

<instance>
   <presentation
     name="Test"
     description="Illustration instance of the XML representation of CSPS"
     nbSolutions="at least 1"
     format="XCSP1.1 (XML CSP Representation 1.1)"
   />
   <domains nbDomains="3">
     <domain name="dom0" nbValues="7" values="0..6"/>
     <domain name="dom1" nbValues="3" values="1 5 10"/>
     <domain name="dom2" nbValues="10" values="1..5 11..15"/>
   </domains>
   <variables nbVariables="5">
     <variable name="X0" domain="dom0"/>
     <variable name="X1" domain="dom0"/>
     <variable name="X2" domain="dom1"/>
     <variable name="X3" domain="dom2"/>
     <variable name="X4" domain="dom0"/>
   </variables>  
   <relations nbRelations="4">
    <relation
       name="rel0"
       domain="dom0 dom0"
       nbConflicts="7"
       conflicts="(0,0)(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)"
    />
    <relation
       name="rel1"
       domain="dom2 dom0"
       nbConflicts="25"
       conflicts="(1,0)(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)(2,1)(2,2)(2,3)(2,4)(2,5)(2,6)(3,2)(3,3)(3,4)(3,5)(3,6)(4,3)(4,4)(4,5)(4,6)(5,4)(5,5)(5,6)"
    />
     <relation
       name="rel2"
       domain="dom1 dom0"
       nbConflicts="1"
       supports="(5,3)"
    />
    <relation
       name="rel3"
       domain="dom0 dom1 dom2"
       nbSupports="17"
       supports="(0,1,3)(0,5,3)(0,10,12)(1,1,4)(1,5,2)(1,10,13)(2,1,5)(2,5,1)(2,10,14)(3,10,5)(3,10,15)(4,5,11)(4,10,4)(5,5,12)(5,10,3)(6,5,13)(6,10,2)"
    />
  </relations>
  <constraints nbConstraints="5">
     <constraint name="C0" scope="X0 X1" relation="rel0"/>
     <constraint name="C1" scope="X3 X0" relation="rel1"/>
     <constraint name="C2" scope="X2 X0" relation="rel2"/>
     <constraint name="C3" scope="X1 X2 X3" relation="rel3"/>
     <constraint name="C4" scope="X1 X4" relation="rel0"/>
   </constraints>
</instance>

[Same example in table format]

[ Back to index ]