Modeling a Weighted CSP consists in creating variables and cost functions.
Domains of variables can be of two different types:
- enumerated domain allowing direct access to each value (array) and iteration on current domain in times proportional to the current number of values (double-linked list)
- interval domain represented by a lower value and an upper value only (useful for large domains)
- Warning
- Current implementation of toulbar2 has limited modeling and solving facilities for interval domains. There is no cost functions accepting both interval and enumerated variables for the moment, which means all the variables should have the same type.
Cost functions can be defined in extension (table or maps) or having a specific semantic.
Cost functions in extension depend on their arity:
- unary cost function (directly associated to an enumerated variable)
- binary and ternary cost functions (table of costs)
- n-ary cost functions (n >= 4) defined by a list of tuples with associated costs and a default cost for missing tuples (allows for a compact representation)
Cost functions having a specific semantic (see Weighted Constraint Satisfaction Problem file format (wcsp)) are:
- simple arithmetic and scheduling (temporal disjunction) cost functions on interval variables
- global cost functions (eg soft alldifferent, soft global cardinality constraint, soft same, soft regular, etc) with three different propagator keywords:
- flow propagator based on flow algorithms with "s" prefix in the keyword (salldiff, sgcc, ssame, sregular)
- DAG propagator based on dynamic programming algorithms with "s" prefix and "dp" postfix (samongdp, salldiffdp, sgccdp, sregulardp, sgrammardp, smstdp, smaxdp)
- network propagator based on cost function network decomposition with "w" prefix (wsum, wvarsum, walldiff, wgcc, wsame, wsamegcc, wregular, wamong, wvaramong, woverlap)
- Note
- The default semantics (using var keyword) of monolithic (flow and DAG-based propagators) global cost functions is to count the number of variables to change in order to restore consistency and to multiply it by the basecost. Other particular semantics may be used in conjunction with the flow-based propagator
-
The semantics of the network-based propagator approach is either a hard constraint ("hard" keyword) or a soft constraint by multiplying the number of changes by the basecost ("lin" or "var" keyword) or by multiplying the square value of the number of changes by the basecost ("quad" keyword)
-
A decomposable version exists for each monolithic global cost function, except grammar and MST. The decomposable ones may propagate less than their monolithic counterpart and they introduce extra variables but they can be much faster in practice
- Warning
- Each global cost function may have less than three propagators implemented
-
Current implementation of toulbar2 has limited solving facilities for monolithic global cost functions (no BTD-like methods nor variable elimination)
-
Current implementation of toulbar2 disallows global cost functions with less than or equal to three variables in their scope (use cost functions in extension instead)
-
Before modeling the problem using make and post, call ::tb2init method to initialize toulbar2 global variables
-
After modeling the problem using make and post, call WeightedCSP::sortConstraints method to initialize correctly the model before solving it