Parsing XCSP3 instance files

XCSP3 instance files can be found here (2022). Instance files are XML documents with the following appearance:

<instance format="XCSP3" type="COP">
  <variables>
    <array id="x" note="x[i] is the landing time of the ith plane" size="[10]">
      <domain for="x[0]"> 129..559 </domain>
      <domain for="x[1]"> 195..744 </domain>
      <domain for="x[2]"> 89..510 </domain>
      <domain for="x[3]"> 96..521 </domain>
      <domain for="x[4]"> 110..555 </domain>
      <domain for="x[5]"> 120..576 </domain>
      <domain for="x[6]"> 124..577 </domain>
      <domain for="x[7]"> 126..573 </domain>
      <domain for="x[8]"> 135..591 </domain>
      <domain for="x[9]"> 160..657 </domain>
    </array>
    <array id="e" note="e[i] is the earliness of the ith plane" size="[10]">
      <domain for="e[0]"> 0..26 </domain>
      <domain for="e[1]"> 0..63 </domain>
      <domain for="e[2]"> 0..9 </domain>
      <domain for="e[3]"> 0..10 </domain>
      <domain for="e[4]"> 0..13 </domain>
      <domain for="e[5] e[8]"> 0..15 </domain>
      <domain for="e[6] e[7]"> 0..14 </domain>
      <domain for="e[9]"> 0..20 </domain>
    </array>
    <array id="t" note="t[i] is the tardiness of the ith plane" size="[10]">
      <domain for="t[0]"> 0..404 </domain>
      <domain for="t[1]"> 0..486 </domain>
      <domain for="t[2]"> 0..412 </domain>
      <domain for="t[3]"> 0..415 </domain>
      <domain for="t[4]"> 0..432 </domain>
      <domain for="t[5] t[8]"> 0..441 </domain>
      <domain for="t[6]"> 0..439 </domain>
      <domain for="t[7]"> 0..433 </domain>
      <domain for="t[9]"> 0..477 </domain>
    </array>
  </variables>
  <constraints>
    <allDifferent note="planes must land at different times"> x[] </allDifferent>
    <block note="the separation time required between any two planes must be satisfied:">
      <extension>
...

The first line <instance format="XCSP3" type="COP"> indicates the instance format and the type. In general the type can be COP (constrained optimization problem) or CSP (constrained satisfaction problem).

The XML files have the the following 2nd level tags (is this the right way to call those?) :

• variables : The variables contained in the instance
• constraints: The constraints contained in the instance
• objectives: The objective.s contained in the file

We'll cover the structure of variables, constraints and objectives. There is documentation on the XCSP3 website, but this is just a brain dump to remember better.

Variables

Variables can be integers:

• <var id="foo"> 0 1 2 3 4 5 6 </var>

....or arrays:

<array id="x" size="[10]">
      <domain for="x[0]"> 129..559 </domain>
      <domain for="x[1]"> 195..744 </domain>
      <domain for="x[2]"> 89..510 </domain>
      <domain for="x[3]"> 96..521 </domain>
      <domain for="x[4]"> 110..555 </domain>
      <domain for="x[5]"> 120..576 </domain>
      <domain for="x[6]"> 124..577 </domain>
      <domain for="x[7]"> 126..573 </domain>
      <domain for="x[8]"> 135..591 </domain>
      <domain for="x[9]"> 160..657 </domain>
</array>

In arrays, the variable domains can be assigned to more than one variable at a time. For example:

• <domain for="e[5] e[8]"> 0..15 </domain> assigns the domain [1, 2, 3, ..., 14, 15] to variables e[5] and e[8]
• <array id="x" size="[10]"> 1..100 </array>: array of size 10 where all variables can take values 1 - 100
• <array id="y" size="[5][8]"> 0 1 </array>: 5 x 8 array of binary variables

Other examples include:

<array id="x" size="[3][5]"> 
  <domain for="x[0][]"> 1..10 </domain>
  <domain for="x[1][]"> 1..20 </domain>
  <domain for="x[2][]"> 1..15 </domain>
</array> 
<array id="y" size="[10]"> 
  <domain for="y[4]"> 0 1 </domain> 
  <domain for="others"> 2 4 6 </domain>
</array> 
<array id="z" size="[5][5][5]"> 
  <domain for="z[][0..1][] z[][2][2..4]"> 0..10 </domain> 
  <domain for="others"> 0 1 </domain>
</array>

For more detail about the domains, please refer to the XCSP3 variable doc

Constraints

Constraints are grouped by block to help when reading the instance. Every constraint type follows a specific signature, but this repo focuses on

• Element
• AllDifferent
• Sum
• Extension
• Intension

Objectives

Speaks for itself ;)