5.360. soft_alldifferent_var
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonyms
, , , , .
- Arguments
- Restrictions
- Purpose
is greater than or equal to the minimum number of variables of the collection for which the value needs to be changed in order that all variables of take a distinct value.
- Example
-
Within the collection of the first example, 3 and 2 items are respectively fixed to values 5 and 1. Therefore one must change the values of at least items to get back to 6 distinct values. Consequently, the corresponding constraint holds since its first argument is greater than or equal to 3.
- Typical
- Symmetries
can be increased.
Items of are permutable.
All occurrences of two distinct values of can be swapped; all occurrences of a value of can be renamed to any unused value.
- Arg. properties
Contractible wrt. .
- Usage
- Remark
Since it focus on the soft aspect of the constraint, the original articleΒ [PetitReginBessiere01], which introduce this constraint, describes how to evaluate the minimum value of and how to prune according to the maximum value of .
The constraint is called inΒ [HebrardMarxSullivanRazgon09].
- Algorithm
A first filtering algorithm presented inΒ [PetitReginBessiere01] achieves arc-consistency. A second filtering algorithm also achieving arc-consistency is described inΒ [Cymer12], [CymerPhD13].
- Reformulation
By introducing a variable that gives the number of distinct values used by variables of the collection , the constraint can be expressed as a conjunction of the constraint and of the linear constraint .
- Counting
-
Length () 2 3 4 5 6 7 8 Solutions 24 212 2470 35682 614600 12286024 279472266 Number of solutions for : domains
Length () 2 3 4 5 6 7 8 Total 24 212 2470 35682 614600 12286024 279472266 Parameter value 0 6 24 120 720 5040 40320 362880 1 9 60 480 4320 42840 463680 5443200 2 9 64 620 7320 97440 1404480 21530880 3 - 64 625 7770 116340 1992480 37406880 4 - - 625 7776 117642 2093616 42550704 5 - - - 7776 117649 2097144 43037568 6 - - - - 117649 2097152 43046712 7 - - - - - 2097152 43046721 8 - - - - - - 43046721 Solution count for : domains
- See also
common keyword: , , , , Β (soft constraint).
implied by: , , .
related: , .
- Keywords
characteristic of a constraint: all different, disequality.
constraint type: soft constraint, value constraint, relaxation, variable-based violation measure.
filtering: bipartite matching.
final graph structure: strongly connected component, equivalence.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
We generate a clique with binary equalities constraints between each pairs of vertices (this include an arc between a vertex and itself) and we state that is equal to the difference between the total number of variables and the number of strongly connected components.
PartsΒ (A) andΒ (B) of FigureΒ 5.360.1 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the graph property we show the different strongly connected components of the final graph. Each strongly connected component of the final graph includes all variables that take the same value. Since we have 6 variables and 3 strongly connected components the cost variable is greater than or equal to .
Figure 5.360.1. Initial and final graph of the constraint
(a) (b)