WCSP file format

The WCSP format is a simple format which should be easy to parse by WCSP solvers. It is composed of a list of numerical terms (except for the first one which defines the problem name) separated by space, tabulation or end of line (see isspace and fscanf function in the C language). Instead of using names for making reference to variables, variable indexes are employed. The same for domain values. All indexes start at zero. All the constraints are defined in extension, by their list of tuples. A default cost value is defined per constraint in order to reduce the size of the list. Only tuples with a different cost value should be given. All the cost values must be positive. The structure of the format is: first, the problem name and dimensions, then the definition of the variables, and last, the definition of the constraints.

Files typically have the ending .wcsp.

Problem name and dimensions

A file in the wcsp format starts with the prologue:

<Problem name> <N> <K> <C> <UB>

where

Definition of the variables

The prologue is followed by the variable specifications:

<domain size of variable with index 0> ... <domain size of variable with index N-1>

Definition of the constraints

The constraints are specified as follows (in one line):

<Arity of the constraint>
<Index of the first variable in the scope of the constraint>
...
<Index of the last variable in the scope of the constraint>
<Default cost value>
<Number of tuples with a cost different than the default cost>

and for every tuple (again in one line):

<Index of the value assigned to the first variable in the scope>
...
<Index of the value assigned to the last variable in the scope>
<Cost of the tuple>

There can be several constraints with the same scope (the solver should combine them into one constraint). The arity of a constraint may be equal to zero. In this case, there is no tuples and the default cost value is added to the total solution cost. This can be used to represent a global lower bound of the problem. The goal is to find an assignment of all the variables with minimum cost, strictly lower than the global upper bound UB. Tuples with a cost greater than or equal to UB are forbidden (hard constraint) (see example below).

Example

A typical example is the 4-Queens problem. Place 4 queens on a 4x4 chessboard in such a way that no one queen could take another queen. There are 4 variables each taking 4 possible values.

4-QUEENS 4 4 7 1
4 4 4 4
4 0 1 2 3 1 24
0 1 2 3 0
0 1 3 2 0
0 2 1 3 0
0 2 3 1 0
0 3 1 2 0
0 3 2 1 0
1 0 2 3 0
1 0 3 2 0
1 2 0 3 0
1 2 3 0 0
1 3 0 2 0
1 3 2 0 0
2 0 1 3 0
2 0 3 1 0
2 1 0 3 0
2 1 3 0 0
2 3 0 1 0
2 3 1 0 0
3 0 1 2 0
3 0 2 1 0
3 1 0 2 0
3 1 2 0 0
3 2 0 1 0
3 2 1 0 0
2 0 1 0 6
0 1 1
1 0 1
1 2 1
2 1 1
2 3 1
3 2 1
2 0 2 0 4
0 2 1
1 3 1
2 0 1
3 1 1
2 0 3 0 2
0 3 1
3 0 1
2 1 2 0 6
0 1 1
1 0 1
1 2 1
2 1 1
2 3 1
3 2 1
2 1 3 0 4
0 2 1
1 3 1
2 0 1
3 1 1
2 2 3 0 6
0 1 1
1 0 1
1 2 1
2 1 1
2 3 1
3 2 1

WCSP_file_format (last edited 2008-03-18 00:42:49 by LarsOtten)