Weighted Constraint Satisfaction Problem file format (wcsp)
It is a text format composed of a list of numerical and string terms separated by spaces. Instead of using names for making reference to variables, variable indexes are employed. The same for domain values. All indexes start at zero.
Cost functions can be defined in intention (see below) or in extension, by their list of tuples. A default cost value is defined per function in order to reduce the size of the list. Only tuples with a different cost value should be given (not mandatory). All the cost values must be positive. The arity of a cost function in extension may be equal to zero. In this case, there is no tuples and the default cost value is added to the cost of any solution. This can be used to represent a global lower bound constant of the problem.
The wcsp file format is composed of three parts: a problem header, the list of variable domain sizes, and the list of cost functions.
Header definition for a given problem:
<Problem name>
<Number of variables (N)>
<Maximum domain size>
<Number of cost functions>
<Initial global upper bound of the problem (UB)>
The goal is to find an assignment of all the variables with minimum total cost, strictly lower than UB. Tuples with a cost greater than or equal to UB are forbidden (hard constraint).
Definition of domain sizes
<Domain size of variable with index 0>
...
<Domain size of variable with index N - 1>
Note
domain values range from zero to size-1
a negative domain size is interpreted as a variable with an interval domain in
Warning
variables with interval domains are restricted to arithmetic and disjunctive cost functions in intention (see below)
General definition of cost functions
Definition of a cost function in extension
<Arity of the cost function>
<Index of the first variable in the scope of the cost function>
...
<Index of the last variable in the scope of the cost function>
<Default cost value>
<Number of tuples with a cost different than the default cost>
followed by for every tuple with a cost different than the default cost:
<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>
Note
Shared cost function: A cost function in extension can be shared by several cost functions with the same arity (and same domain sizes) but different scopes. In order to do that, the cost function to be shared must start by a negative scope size. Each shared cost function implicitly receives an occurrence number starting from 1 and incremented at each new shared definition. New cost functions in extension can reuse some previously defined shared cost functions in extension by using a negative number of tuples representing the occurrence number of the desired shared cost function. Note that default costs should be the same in the shared and new cost functions. Here is an example of 4 variables with domain size 4 and one AllDifferent hard constraint decomposed into 6 binary constraints.
Shared CF used inside a small example in wcsp format:
Definition of a cost function in intension by replacing the default cost value by -1 and by giving its keyword name and its K parameters
<Arity of the cost function>
<Index of the first variable in the scope of the cost function>
...
<Index of the last variable in the scope of the cost function>
-1
<keyword>
<parameter1>
...
<parameterK>
Possible keywords of cost functions defined in intension followed by their specific parameters:
>= cstdelta to express soft binary constraint with associated cost function
> cstdelta to express soft binary constraint with associated cost function
<= cstdelta to express soft binary constraint with associated cost function
< cstdelta to express soft binary constraint with associated cost function
= cstdelta to express soft binary constraint with associated cost function
disj cstxcstypenalty to express soft binary disjunctive constraint with associated cost function
sdisj cstxcstyxinftyyinftycostxcosty to express a special disjunctive constraint with three implicit hard constraints and and and an additional cost function
Global cost functions using a dedicated propagator:
clique 1 (nb_values (value)*)* to express a hard clique cut to restrict the number of variables taking their value into a given set of values (per variable) to at most 1 occurrence for all the variables (warning! it assumes also a clique of binary constraints already exists to forbid any two variables using both the restricted values)
knapsack capacity (weight)* to express a reverse knapsack constraint (i.e., a linear constraint on 0/1 variables with >= operator) with capacity and weights are positive or negative integer coefficients (use negative numbers to express a linear constraint with <= operator)
Global cost functions using a flow-based propagator:
salldiff var|dec|decbi cost to express a soft alldifferent constraint with either variable-based (var keyword) or decomposition-based (dec and decbi keywords) cost semantic with a given cost per violation (decbi decomposes into a binary cost function complete network)
sgcc var|dec|wdec costnb_values (valuelower_boundupper_bound (shortage_weightexcess_weight)?)* to express a soft global cardinality constraint with either variable-based (var keyword) or decomposition-based (dec keyword) cost semantic with a given cost per violation and for each value its lower and upper bound (if wdec then violation cost depends on each value shortage or excess weights)
ssame costlist_size1list_size2 (variable_index)* (variable_index)* to express a permutation constraint on two lists of variables of equal size (implicit variable-based cost semantic)
sregular var|edit costnb_statesnb_initial_states (state)* nb_final_states (state)* nb_transitions (start_statesymbol_valueend_state)* to express a soft regular constraint with either variable-based (var keyword) or edit distance-based (edit keyword) cost semantic with a given cost per violation followed by the definition of a deterministic finite automaton with number of states, list of initial and final states, and list of state transitions where symbols are domain values
Global cost functions using a dynamic programming DAG-based propagator:
sregulardp var costnb_statesnb_initial_states (state)* nb_final_states (state)* nb_transitions (start_statesymbol_valueend_state)* to express a soft regular constraint with a variable-based (var keyword) cost semantic with a given cost per violation followed by the definition of a deterministic finite automaton with number of states, list of initial and final states, and list of state transitions where symbols are domain values
sgrammar|sgrammardp var|weight costnb_symbolsnb_valuesstart_symbolnb_rules ((0 terminal_symbolvalue)|(1 nonterminal_innonterminal_out_leftnonterminal_out_right)|(2 terminal_symbolvalueweight)|(3 nonterminal_innonterminal_out_leftnonterminal_out_rightweight))* to express a soft/weighted grammar in Chomsky normal form
samong|samongdp var costlower_boundupper_boundnb_values (value)* to express a soft among constraint to restrict the number of variables taking their value into a given set of values
salldiffdp var cost to express a soft alldifferent constraint with variable-based (var keyword) cost semantic with a given cost per violation (decomposes into samongdp cost functions)
sgccdp var costnb_values (valuelower_boundupper_bound)* to express a soft global cardinality constraint with variable-based (var keyword) cost semantic with a given cost per violation and for each value its lower and upper bound (decomposes into samongdp cost functions)
max|smaxdp defCostnbtuples (variablevaluecost)* to express a weighted max cost function to find the maximum cost over a set of unary cost functions associated to a set of variables (by default, defCost if unspecified)
MST|smstdp to express a spanning tree hard constraint where each variable is assigned to its parent variable index in order to build a spanning tree (the root being assigned to itself)
Global cost functions using a cost function network-based propagator:
wregular nb_statesnb_initial_states (state and cost)* nb_final_states (state and cost)* nb_transitions (start_statesymbol_valueend_statecost)* to express a weighted regular constraint with weights on initial states, final states, and transitions, followed by the definition of a deterministic finite automaton with number of states, list of initial and final states with their costs, and list of weighted state transitions where symbols are domain values
walldiff hard|lin|quad cost to express a soft alldifferent constraint as a set of wamong hard constraint (hard keyword) or decomposition-based (lin and quad keywords) cost semantic with a given cost per violation
wgcc hard|lin|quad costnb_values (valuelower_boundupper_bound)* to express a soft global cardinality constraint as either a hard constraint (hard keyword) or with decomposition-based (lin and quad keyword) cost semantic with a given cost per violation and for each value its lower and upper bound
wsame hard|lin|quad cost to express a permutation constraint on two lists of variables of equal size (implicitly concatenated in the scope) using implicit decomposition-based cost semantic
wsamegcc hard|lin|quad costnb_values (valuelower_boundupper_bound)* to express the combination of a soft global cardinality constraint and a permutation constraint
wamong hard|lin|quad costnb_values (value)* lower_boundupper_bound to express a soft among constraint to restrict the number of variables taking their value into a given set of values
wvaramong hard costnb_values (value)* to express a hard among constraint to restrict the number of variables taking their value into a given set of values to be equal to the last variable in the scope
woverlap hard|lin|quad costcomparatorrighthandside overlaps between two sequences of variables X, Y (i.e. set the fact that Xi and Yi take the same value (not equal to zero))
wsum hard|lin|quad costcomparatorrighthandside to express a soft sum constraint with unit coefficients to test if the sum of a set of variables matches with a given comparator and right-hand-side value
wvarsum hard costcomparator to express a hard sum constraint to restrict the sum to be comparator to the value of the last variable in the scope
Let us note <> the comparator, K the right-hand-side value associated to the comparator, and Sum the result of the sum over the variables. For each comparator, the gap is defined according to the distance as follows:
if <> is == : gap = abs(K - Sum)
if <> is <= : gap = max(0,Sum - K)
if <> is < : gap = max(0,Sum - K - 1)
if <> is != : gap = 1 if Sum != K and gap = 0 otherwise
if <> is > : gap = max(0,K - Sum + 1);
if <> is >= : gap = max(0,K - Sum);
Warning
The decomposition of wsum and wvarsum may use an exponential size (sum of domain sizes).
list_size1 and list_size2 must be equal in ssame.
Cost functions defined in intention cannot be shared.