**********************************************************************
This  file explains  the `.ds'  file format  used to  encode  CSPs and
VCSPs.
**********************************************************************

Variables and  domain values are  represented in a symbolic  way: they
are  symbols  (strings  without   any  blanks)  rather  than  indexes.
Constraints   are  defined   either  in   extension  by   a   list  of
permitted/forbidden tuples  or in intension by a  function name chosen
in a list of precompiled  functions. A single file may contain several
instancies, each one is a subset of the constraints.

The `.ds' is structured into  four blocks, each one corresponds to one
or more lines of text:

`.ds' -> <Problem> 
         <Variables&Domains> 
	 <Constraints> 
	 <Instancies>

Note  that `[  x ]'  means element  `x' is  optional, `(  x  )*' means
element `x'  can be repeated several  times and `x |  y' means element
`x' or element `y'.

**********************************************************************
1) Problem name and special flags (on the same line of text)

<Problem>  ->  <problem_name>  [  "classic"  |  "valued"  |  "tabu"  |
"tabu_classic" | "tabu_valued" ]

Flag "valued"  means that  a cost is  associated with  each constraint
(VCSP case);  if this flag is  missing or "classic" is  used, then all
constraints are  hard (CSP case,  by default). Flag "tabu"  means that
constraints in extension  are defined by a list  of forbidden tuples ;
if this  flag is  missing, constraints in  extension are defined  by a
list of permitted tuples (by default).

**********************************************************************
2) Variables and domains

<Variables&Domains> -> ( <Variable&Domain> )*

<Variable&Domain> -> <variable_name> ( <value_name> )*

Each variable and its domain takes one line of text.

**********************************************************************
3) Constraints

<Constraints> -> ( <Constraint> )*

<Constraint>  -> "#"  
	         <constraint_name> [ <cost> ] ( "extension" | <intension> ) ( <variable_name> )*
		 [ <Tuples> ]

<cost> -> "top" | <number>

<intension> -> "fct_equal" | "fct_diff" | ...

<Tuples> -> ( <Tuple> )* 

<Tuple> -> ( <value_name> )*

The  first   "#"  separates  variables   definition  from  constraints
definition. Every tuple is on a different line of text. If "extension"
is used then a list of  tuples must be provided. They are permitted or
forbidden tuples depending  on the flag "tabu". In  the case of VCSPs,
if  "top" is  used  as  a cost,  it  means it  is  a hard  constraint,
otherwise it is  a soft constraint and <number>  corresponds to a cost
of  the constraint  violation in  additive CSPs  or to  a  priority in
lexicographic and possibilistic CSPs.

Precompiled functions and their semantics are:

Every constraint is  ternary or nary and applies  to ordered variables
x,y,z,... `int(x)' means the name  of the value assigned to variable x
is converted to integer.

Integer comparisons:
"fct_equal" <=> int(x) = int(y) = int(z) = ...
"fct_diff" <=> alldiff(int(x),int(y),int(z),...)
"fct_inf" <=> int(x) < int(y) < int(z) < ...
"fct_sup" <=> int(x) > int(y) > int(z) > ...

Distance constraints:
"fct_absdiffequ" <=> | int(x) - int(y) | = int(z)
"fct_absdiffsup" <=> | int(x) - int(y) | > int(z)
"fct_absdiffinf" <=> | int(x) - int(y) | < int(z)

Special distance constraints:
"fct_absdiffsup1" <=> | int(trans[pos(x)]) - int(y) | > int(z)
"fct_absdiffsup2" <=> | int(x) - int(trans[pos(y)]) | > int(z)
"fct_absdiffsup12" <=> | int(trans[pos(x)]) - int(trans[pos(y)]) | > int(z)

The  constraint  name defines  a  list  of  constants called  `trans'.
`pos(x)' returns the  index of the value assigned to  x in its domain.
`trans[pos(x)]'  returns  the  `pos(x)'  element  of  `trans'.   These
special constraints are used  to eliminate even variables and distance
equality constraints when encoding the CELAR problem.

Sequence constraints:
"fct_diffsup" <=> int(x) - int(y) >= int(z)
"fct_diffinf" <=> int(x) - int(y) <= int(z)

Mutual exclusion:
"fct_diffsup2" <=> int(x) - int(y) >= int(z) or int(y) - int(x) >= int(z)
"fct_diffinf2" <=> int(x) - int(y) <= int(z) or int(y) - int(x) <= int(z)

Special constraint for the Golomb problem:
"fct_alldiff" <=> y - x != w - z

Lexicographic comparisons (based on the name of values assigned to variables)
"fct_equal_lex" <=> x = y = z = ...
"fct_diff_lex" <=> alldiff(x,y,z,...)
"fct_inf_lex" <=> x < y < z < ...
"fct_sup_lex" <=> x > y > z > ...

**********************************************************************
4) Instancies

<Instancies> -> ( <Instancy> )*

<Instancy> -> "% " <number> ( <constraint_name> )*

The  first  "%"   separates  constraints  definition  from  instancies
definition.  <number>   defines  the  instancy  number   used  by  the
program. A blank between "%" and the instancy number is important. The
usual  way  is to  defined  "%  0 "  followed  by  all the  constraint
names. See for  instance file `benchs/random/20_10_50_30.ds' where 101
different    Max-CSP    instancies    have   been    defined    (using
`solaris/random_vcsp' application). In  this example, a complete graph
has  been generated  with 190  constraints defined  and  each instance
contains only 95 constraints randomly chosen.


Simple CSP examples can be found in the `benchs/famous' directory. See
for classic instances,  the 4-queen problem `benchs/famous/queens4.ds'
or the  Zebra problem  `benchs/famous/zebra.ds'. VCSP examples  are in
the  `benchs/random' and  `benchs/celar'  directories.  `benchs/spot5'
contains VVCSP examples (only unary constraints are soft).