5.359. soft_alldifferent_ctr
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonyms
, , , , , .
- Arguments
- Restrictions
- Purpose
Consider the disequality constraints involving two distinct variables and of the collection . Among the previous set of constraints, is greater than or equal to the number of disequality constraints that do not hold.
- Example
-
Within the collection the first and fifth values, the first and sixth values, the second and fourth values, and the fifth and sixth values are identical. Consequently, the argument is greater than or equal to the number of disequality constraints that do not hold (i.e,Β 4) and the constraint holds.
- 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
The constraint is called or inΒ [HebrardMarxSullivanRazgon09].
- Algorithm
Since it focus on the soft aspect of the constraint, the original articleΒ [PetitReginBessiere01] that introduces this constraint describes how to evaluate the minimum value of and how to prune according to the maximum value of . The corresponding filtering algorithm does not achieve arc-consistency. W.-J.Β vanΒ HoeveΒ [Hoeve04] presents a new filtering algorithm that achieves arc-consistency. This algorithm is based on a reformulation into a minimum-cost flow problem.
- Counting
-
Length () 2 3 4 5 6 7 8 Solutions 15 208 3625 72576 1630279 40632320 1114431777 Number of solutions for : domains
Length () 2 3 4 5 6 7 8 Total 15 208 3625 72576 1630279 40632320 1114431777 Parameter value 0 6 24 120 720 5040 40320 362880 1 9 60 480 4320 42840 463680 5443200 2 - 60 540 6120 80640 1169280 18144000 3 - 64 620 7320 100590 1580880 27881280 4 - - 620 7620 113190 1933680 36666000 5 - - 620 7620 113190 1968960 39206160 6 - - 625 7770 116760 2051280 41111280 7 - - - 7770 117390 2086560 42522480 8 - - - 7770 117390 2086560 42628320 9 - - - 7770 117390 2088520 42769440 10 - - - 7776 117642 2095576 42938784 11 - - - - 117642 2096752 43023456 12 - - - - 117642 2096752 43025976 13 - - - - 117642 2096752 43030008 14 - - - - 117642 2096752 43030008 15 - - - - 117649 2097144 43044120 16 - - - - - 2097144 43046136 17 - - - - - 2097144 43046136 18 - - - - - 2097144 43046136 19 - - - - - 2097144 43046136 20 - - - - - 2097144 43046136 21 - - - - - 2097152 43046712 22 - - - - - - 43046712 23 - - - - - - 43046712 24 - - - - - - 43046712 25 - - - - - - 43046712 26 - - - - - - 43046712 27 - - - - - - 43046712 28 - - - - - - 43046721 Solution count for : domains
- See also
common keyword: , , , Β (soft constraint).
implied by: , .
implies: .
related: .
- Keywords
characteristic of a constraint: all different, disequality.
constraint type: soft constraint, value constraint, relaxation, decomposition-based violation measure.
modelling: degree of diversity of a set of solutions.
modelling exercises: degree of diversity of a set of solutions.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
We generate an initial graph with binary equalities constraints between each vertex and its successors. We use the arc generator in order to avoid counting twice the same equality constraint. The graph property states that is greater than or equal to the number of equalities that hold in the final graph.
PartsΒ (A) andΒ (B) of FigureΒ 5.359.1 respectively show the initial and final graph associated with the Example slot. Since we use the graph property, the arcs of the final graph are stressed in bold. Since four equality constraints remain in the final graph the cost variable is greater than or equal to 4.
Figure 5.359.1. Initial and final graph of the constraint
(a) (b)